CHAPTER1 Combinatorial Analysis 1.1 INTRODUCTION PERMUTATIONS ICIPLE OF COUNTING 1.4 COMBINATIONS 1.1 INTRODUCTION Here is a typical problem of interest involving probability:A communication system then boabe to re oult that cXactly m of the n sonal?For instance.in the special case where4 and sSibnct 0110 0101 1100 rsthat the nt orking and that it is defcctive Because n the 3 arrangements and not fu the functional in a similar fashion.That is,we could count the number of configurations thsystem's being functional and then divide by the total number of a omhepreceiscuesethtt oul bev method for counting the number of ways that things can occur.In fact,many prob. counting is formally 1.2 THE BASIC PRINCIPLE OF COUNTING The basic principle of counting will be fundamental to all our work.Loosely put,it CHAPTER 1 Combinatorial Analysis 1.1 INTRODUCTION 1.2 THE BASIC PRINCIPLE OF COUNTING 1.3 PERMUTATIONS 1.4 COMBINATIONS 1.5 MULTINOMIAL COEFFICIENTS 1.6 THE NUMBER OF INTEGER SOLUTIONS OF EQUATIONS 1.1 INTRODUCTION Here is a typical problem of interest involving probability: A communication system is to consist of n seemingly identical antennas that are to be lined up in a linear order. The resulting system will then be able to receive all incoming signals—and will be called functional—as long as no two consecutive antennas are defective. If it turns out that exactly m of the n antennas are defective, what is the probability that the resulting system will be functional? For instance, in the special case where n = 4 and m = 2, there are 6 possible system configurations, namely, 0110 0101 1010 0011 1001 1100 where 1 means that the antenna is working and 0 that it is defective. Because the resulting system will be functional in the first 3 arrangements and not functional in the remaining 3, it seems reasonable to take 3 6 = 1 2 as the desired probability. In the case of general n and m, we could compute the probability that the system is functional in a similar fashion. That is, we could count the number of configurations that result in the system’s being functional and then divide by the total number of all possible configurations. From the preceding discussion, we see that it would be useful to have an effective method for counting the number of ways that things can occur. In fact, many prob￾lems in probability theory can be solved simply by counting the number of different ways that a certain event can occur. The mathematical theory of counting is formally known as combinatorial analysis. 1.2 THE BASIC PRINCIPLE OF COUNTING The basic principle of counting will be fundamental to all our work. Loosely put, it states that if one experiment can result in any of m possible outcomes and if another experiment can result in any of n possible outcomes, then there are mn possible out￾comes of the two experiments. 1