A basic tool for the construction of sample description spaces of random phenomena is provided by the notion of an \(n\) -tuple. An \(n\) -tuple \(\left(z_{1}, z_{2}, \ldots, z_{n}\right)\) is an array of \(n\) symbols, \(z_{1}, z_{2}, \ldots, z_{n}\) , which are called, respectively, the first component, the second component, and so on, up to the nth component, of the n-tuple . The order in which the components of an \(n\) -tuple are written is of importance (and consequently one sometimes speaks of ordered \(n\) -tuples). Two \(n\) -tuples \(\left(z_{1}, z_{2}, \ldots, z_{n}\right)\) and \(\left(z_{1}^{\prime}, z_{2}^{\prime}, \ldots, z_{n}^{\prime}\right)\) are said to be identical, or indistinguishable, if and only if they consist of the same components written in the same order; symbolically, \(z_{k}=z_{k}^{\prime}\) for \(k=1,2, \ldots, n\) . The usefulness of \(n\) -tuples derives from the fact that they are convenient devices for reporting the results of a drawing of a sample of size \(n\) .

A basic random phenomenon with whose analysis we are concerned in probability theory is that of sampling . Suppose we have an urn containing \(M\) balls, which are numbered 1 to \(M\) . Suppose we draw balls from the urn one at a time, until \(n\) balls have been drawn; for brevity, we say we have drawn a sample (or an ordered sample) of size \(n\) . Of course, we must also specify whether the sample has been drawn with replacement or without replacement.

The drawing is said to be done with replacement , and the sample is said to be drawn with replacement, if after each draw the number of the ball drawn is recorded, but the ball itself is returned to the urn. The drawing is said to be done without replacement, and the sample is said to be drawn without replacement, if the ball drawn is not returned to the urn after each draw, so that the number of balls available in the urn for the \(k\) th draw is \(M-k+1\) . Consequently, if the drawing is done without replacement , then the size \(n\) of the sample drawn must be less than or equal to \(M\) , the original number of balls in the urn. On the other hand, if the drawing is done with replacement, then \(n\) may be any number.

To report the result of drawing a sample of size \(n\) , an \(n\) -tuple \(\left(z_{1}, z_{2}, \ldots, z_{n}\right)\) is used, in which \(z_{1}\) represents the number of the ball drawn on the first draw, \(z_{2}\) represents the number of the ball drawn on the second draw, and so on, up to \(z_{n}\) , which represents the number of the ball drawn on the \(n\) th draw.

As indicated in section 7 of Chapter 1 , many probability problems defined on finite sample description spaces may be reduced to problems of counting. Consequently, it is useful to know the basic principles of combinatorial analysis by which the size of sets of \(n\) -tuples, which arise in various ways, may be counted. We now state a formula that is basic to the theory of counting sets of \(n\) -tuples and that may be called the basic principle of combinatorial analysis .

Suppose there is a set \(A\) whose members are ordered \(n\) -tuples of objects of some sort. In order to compute the size of \(A\) , first determine the number \(N_{1}\) of objects that may be used as the first component of an \(n\) -tuple in \(A\) . Next determine ( if it exists ¹ ) the number \(N_{2}\) of objects that may be second components of an \(n\) -tuple, of which the first component is known. Then determine (if it exists) the number \(N_{3}\) of objects that may be third components of an n-tuple, of which the first two components are known. Continue in this manner until the number \(N_{n}\) (if it exists) of objects that may be the \(n\) th component of an \(n\) -tuple, of which the first \((n-1)\) components are known, has been determined. The size of the set \(A\) of \(n\) -tuples is then given by the product of the numbers \(N_{1}, N_{2}, \ldots, N_{n}\) ; in symbols. \[N[A]=N_{1} N_{2} \cdots N_{n}. \tag{1.1}\] 

As a first application of this basic principle, suppose that we have \(n\) different kinds of objects. Suppose that we have \(N_{1}\) objects \(a_{1}^{(1)}, \ldots, a_{N_{1}}^{(1)}\) of the first kind, \(N_{2}\) objects \(a_{1}^{(2)}, \ldots, a_{N_{2}}^{(2)}\) of the second kind, and so on, up to \(N_{n}\) objects \(a_{1}^{(n)}, \ldots, a_{N_{n}}^{(n)}\) of the \(n\) th kind. We may then form \(N_{1} N_{2} \ldots N_{n}\) ordered n-tuples \(\left(a_{j_{1}}^{(1)}, a_{j_{2}}^{(2)}, \ldots, a_{j_{n}}^{(n)}\right)\) containing one element of each kind. 

We next apply the basic principle of combinatorial analysis to determine the number of samples of size \(n\) that can be drawn with or without replacement from an urn containing \(M\) distinguishable balls.

The number of ways in which one can draw a sample of \(n\) balls from an urn containing \(M\) distinguishable balls is \(M(M-1) \cdots(M-n+1)\) , if the sampling is done without replacement, and \(M^{n}\) , if the sampling is done with replacement. 

To show the first of these statements, note that there are \(M\) possible choices of numbers for the first ball drawn, \((M-1)\) choices of numbers for the second ball drawn, and finally \(M-n+1=M-(n-1)\) choices of numbers for the \(n\) th ball drawn. The second statement follows by a similar argument, since for each of the \(n\) balls in the sample there are \(M\) choices.

Various notations have been adopted to denote the product \(M(M-1) \ldots\) \((M-n+1)\) . We adopt the notation \((M)_{n}\) . We thus define, for any positive integer \(M=1,2, \ldots\) , and for any integer \(n=1,2, \ldots, M\) ,

\[(M)_{n}=M(M-1) \cdots(M-n+1). \tag{1.2}\] 

Another notation with which the reader should be familiar is that of the factorial. Given any positive integer \(M\) , we define \(M\) ! (read, \(M\) factorial) as the product of all the integers, 1 to \(M\) . Thus \[M !=1 \cdot 2 \cdots(M-1) M. \tag{1.3}\] We can write \((M)_{n}\) in terms of the factorial notation by \[(M)_{n}=\frac{M !}{(M-n) !} \quad n=0,1,2, \ldots, M. \tag{1.4}\] 

In order that (1.4) may hold for \(n=M\) , we define \[0 !=1. \tag{1.5}\] 

In order that (1.4) may hold for \(n=0\) , we define \[(M)_{0}=1. \tag{1.6}\] 

An important application of the foregoing relations is to the problem of finding the number of subsets of a set . Consider the set \(S=\{1,2, \ldots, N\}\) , which consists of all integers, 1 to \(N\) . How many possible subsets of \(S\) can be formed? In order to solve this problem, we first find for \(k=1\) , \(2, \ldots, N\) the number of subsets of \(S\) of size \(k\) that can be formed. Let \(x_{k}\) be the number of subsets of \(S\) of size \(k\) . We shall prove that \(x_{k}\) satisfies the relationship \(x_{k} \cdot k !=(N)_{k}\) , so that \[x_{k}=\frac{(N)_{k}}{k !}. \tag{1.7}\] 

To see this, regard each subset of \(S\) of size \(k\) as an urn (containing \(k\) distinguishable balls) from which samples of size \(k\) are being drawn without replacement; the number of samples that can be drawn in this manner is \(k\) !. On the other hand, the number of samples of size \(k\) , drawn without replacement, that can be drawn from the set \(S\) , regarded as an urn containing \(N\) distinguishable balls, is \((N)_{k}\) . A little reflection will convince the reader that all the samples without replacement of size \(k\) that can be drawn from \(S\) can be obtained by first choosing a subset of \(S\) of size \(k\) from which one then draws all possible samples without replacement of size \(k\) . Consequently, \(x_{k} \cdot k !=(N)_{k}\) , or, in words, the number of subsets of \(S\) of size \(k\) , multiplied by the number of samples that can be drawn without replacement from a subset of size \(k\) , is equal to the number of samples of size \(k\) that can be drawn without replacement from \(S\) itself. 

We now introduce some notation. We define, for any integer \(N=1\) , \(2, \ldots\) , and integer \(k=0,1, \ldots, N\) , the symbol \({N \choose k}\) by \[{N \choose k} = \frac{(N)_{k}}{k!}=\frac{N(N-1) \cdots(N-k+1)}{1 \cdot 2 \cdots k}=\frac{N !}{k !(N-k) !}. \tag{1.8}\] 

Equation (1.7) may be restated as follows: the number of subsets of size \(k\) that may be formed from the members of a set of size \(N\) is \({N \choose k}\) . 

The quantities \({N \choose k}\) are generally called binomial coefficients because of the role they play in the binomial theorem, which states that for any two real numbers \(a\) and \(b\) and any positive integer \(N\) \begin{align} (a+b)^{N} & =\sum_{k=0}^{N} {N \choose k} a^{N-k} b^{k} \tag{1.9} \\ & = {N \choose 0} a^{N} + {N \choose 1} a^{N-1} b+{N \choose 2} a^{N-2} b^{2} \\ & +\cdots+{N \choose k} a^{N-k} b^{k}+\cdots+ {N \choose N-2}a^{2} b^{N-2} \\ & +{N \choose N-1} a b^{N-1} + {N \choose N} b^{N}. \end{align} 

It is convenient to extend the definitions of \({N \choose k}\) and \((N)_{k}\) to any positive or negative integer \(k\) . We define, for \(N=1,2, \ldots\) , \[(N)_{0}= {N \choose 0}=1, \quad (N)_{k}= {N \choose k}=0, \tag{1.10}\] if either \(k<0\) or \(k>N\) .

We next note the extremely useful relation, holding for \(N=1,2, \ldots\) , and \(k=0, \pm 1, \pm 2, \ldots\) , \[{N \choose k-1} + {N \choose k} = {N+1 \choose k}. \tag{1.11}\] 

This relation may be verified directly from the definition of binomial coefficients. An intuitive justification of (1.11) can be obtained. Given a set \(S\) , with \(N+1\) members, choose an element \(t\) in \(S\) . The number of subsets of \(S\) of size \(k\) in which \(t\) is not present is equal to \(\displaystyle {N\choose k}\) , whereas the number of subsets of \(S\) of size \(k\) in which \(t\) is present is \(\left(\begin{array}{c}N \\ k-1\end{array}\right)\) ; the sum of these two quantities is equal to \(\left(\begin{array}{c}N+1 \\ k\end{array}\right)\) , the total number of subsets of \(S\) of size \(k\) .

Equation (1.11) is the algebraic expression of a fact represented in tabular form by Pascal’s triangle: \[\begin{gather} {1\choose 0}=1 \quad{1\choose 1}=1 \\ {2\choose 0}=1 \quad{2\choose 1}=2 \quad{2\choose 2}=1 \\ \left(\begin{array}{l} 3 \\ 0 \end{array}\right)=1 \quad\left(\begin{array}{l} 3 \\ 1 \end{array}\right)=3 \quad\left(\begin{array}{l} 3 \\ 2 \end{array}\right)=3 \quad\left(\begin{array}{l} 3 \\ 3 \end{array}\right)=1 \\ \left(\begin{array}{l} 4 \\ 0 \end{array}\right)=1 \quad\left(\begin{array}{l} 4 \\ 1 \end{array}\right)=4 \quad\left(\begin{array}{l} 4 \\ 2 \end{array}\right)=6 \quad\left(\begin{array}{l} 4 \\ 3 \end{array}\right)=4 \quad\left(\begin{array}{l} 4 \\ 4 \end{array}\right)=1 \\ \left(\begin{array}{l} 5 \\ 0 \end{array}\right)=1 \quad\left(\begin{array}{l} 5 \\ 1 \end{array}\right)=5 \quad\left(\begin{array}{l} 5 \\ 2 \end{array}\right)=10 \quad\left(\begin{array}{l} 5 \\ 3 \end{array}\right)=10 \quad\left(\begin{array}{l} 5 \\ 4 \end{array}\right)=5 \quad\left(\begin{array}{l} 5 \\ 5 \end{array}\right)=1, \\ \end{gather}\] and so on. Equation (1.11) expresses the fact that each term in Pascal’s triangle is the sum of the two terms above it.

One also notices in Pascal’s triangle that the entries on each line are symmetric about the middle entry (or entries). More precisely, the binomial coefficients have the property that for any positive integer \(N\) and \(k=0,1,2, \ldots, N\) \[\left(\begin{array}{c} N \tag{1.12} \\ N-k \end{array}\right)=\left(\begin{array}{l} N \\ k \end{array}\right).\] To prove (1.12) one need note only that each side of the equation is equal to \(N ! / k !(N-k)\) !.

It should be noted that with (1.11) and the aid of the principle of mathematical induction one may prove the binomial theorem.

The mathematical facts are now at hand to determine how many subsets of a set of size \(N\) one may form. From the binomial theorem (1.9) , with \(a=b=1\) , it follows that \[1+\left(\begin{array}{c} N \tag{1.13} \\ 1 \end{array}\right)+\left(\begin{array}{c} N \\ 2 \end{array}\right)+\cdots+\left(\begin{array}{c} N \\ N-1 \end{array}\right)+\left(\begin{array}{l} N \\ N \end{array}\right)=2^{N}.\] 

From (1.13) it follows that the number of events (including the impossible event) that can be formed on a sample description space of size \(N\) is \(2^{N}\) . For there is one impossible event, \(\left(\begin{array}{l}N \\ 1\end{array}\right)\) events of size \(1,\left(\begin{array}{l}N \\ 2\end{array}\right)\) events of size \(2, \ldots,\left(\begin{array}{l}N \\ k\end{array}\right)\) events of size \(k, \ldots,\left(\begin{array}{c}N \\ N-1\end{array}\right)\) events of size \(N-1\) , and \(\left(\begin{array}{l}N \\ N\end{array}\right)\) events of size \(N\) . There is an alternate way of showing that if \(S\) has \(N\) members then it has \(2^{N}\) subsets. Let the members of \(S\) be numbered 1 to \(N\) . To describe a subset \(A\) of \(S\) , we may write an \(N\) -tuple \(\left(t_{1}, t_{2}, \ldots, t_{N}\right)\) , whose \(j\) th component \(t_{j}\) is equal to 1 or 0, depending on whether the \(j\) th member of \(S\) does or does not belong to the subset \(A\) . Since one can form \(2^{N} N\) -tuples, it follows that \(S\) possesses \(2^{N}\) subsets.

Another counting problem whose solution we shall need is that of finding the number of partitions of a set of size \(N\) and, in particular, of the set \(S=\{1,2, \ldots, N\}\) . Let \(r\) be a positive integer and let \(k_{1}, k_{2}, \ldots, k_{r}\) be positive integers such that \(k_{1}+k_{2}+\cdots+k_{r}=N\) . By a partition of \(S\) , with respect to \(r\) and \(k_{1}, k_{2}, \ldots, k_{r}\) , we mean a division of \(S\) into \(r\) subsets (ordered so that one may speak of a first subset, a second subset, etc.) such that the first subset has size \(k_{1}\) , the second subset has size \(k_{2}\) , and so on, up to the \(r\) th subset, which has size \(k_{r}\) .

We now prove that the number of ways in which one can partition a set of size \(N\) into \(r\) ordered subsets so that the first subset has size \(k_{1}\) , the second subset has size \(k_{2}\) , and so on, where \(k_{1}+k_{2}+\cdots+k_{r}=N\) , is the product \[\left(\begin{array}{c} N \tag{1.14} \\ k_{1} \end{array}\right)\left(\begin{array}{c} N-k_{1} \\ k_{2} \end{array}\right)\left(\begin{array}{c} N-k_{1}-k_{2} \\ k_{3} \end{array}\right) \cdots\left(\begin{array}{c} N-k_{1}-k_{2}-\cdots-k_{r-1} \\ k_{r} \end{array}\right).\] 

To prove (1.14) we proceed as follows. For the first subset of \(k_{1}\) items there are \(N\) items available, so that there are \(\left(\begin{array}{l}N \\ k_{1}\end{array}\right)\) ways in which the subset of \(k_{1}\) items can be selected. There are \(N-k_{1}\) items available from which to select the \(k_{2}\) items that go into the second subset; consequently, the second subset, containing \(k_{2}\) items, can be selected in \(\left(\begin{array}{c}N-k_{1} \\ k_{2}\end{array}\right)\) ways. Continuing in this manner, we determine that the \(r\) th subset, containing \(k_{r}\) items, can be selected in \(\left(\begin{array}{c}N-k_{1}-\cdots-k_{r-1} \\ k_{r}\end{array}\right)\) ways. By multiplying these expressions, we obtain the number of ways in which a set of size \(N\) can be partitioned in the manner described.

The expression (1.14) may be written in a more convenient form. It is clear by use of the definition of \(\left(\begin{array}{l}N \\ k\end{array}\right)\) that \[\left(\begin{array}{l} N \tag{1.15} \\ k_{1} \end{array}\right)\left(\begin{array}{c} N-k_{1} \\ k_{2} \end{array}\right)=\frac{N !}{k_{1} ! k_{2} !\left(N-k_{1}-k_{2}\right) !}.\] Next, one obtains \[\left(\begin{array}{l} N \\ k_{1} \end{array}\right)\left(\begin{array}{c} N-k_{1} \\ k_{2} \end{array}\right)\left(\begin{array}{c} N-k_{1}-k_{2} \\ k_{3} \end{array}\right)=\frac{N !}{k_{1} ! k_{2} ! k_{3} !\left(N-k_{1}-k_{2}-k_{3}\right) !}.\] 

Continuing in this manner, one finds that (1.14) is equal to \[\frac{N !}{k_{1} ! k_{2} ! \cdots k_{r} !}. \tag{1.16}\] 

Quantities of the form of (1.16) arise frequently, and a special notation is introduced to denote them. For any integer \(N\) , and \(r\) nonnegative integers \(k_{1}, k_{2}, \ldots, k_{r}\) whose sum is \(N\) , we define the multinomial coefficient : \[\left(\begin{array}{c} N \tag{1.17} \\ k_{1} k_{2} \cdots k_{r} \end{array}\right)=\frac{N !}{k_{1} ! k_{2} ! \cdots k_{r} !}.\] 

The multinomial coefficients derive their name from the fact that they are the coefficients in the expansion of the \(N\) th power of the multinomial form \(a_{1}+a_{2}+\cdots+a_{r}\) in terms of powers of \(a_{1}, a_{2}, \ldots, a_{r}\) : \begin{align} \left(a_1\right. & \left.+a_2+\cdots+a_r\right)^N \tag{1.18} \\ & =\underset{k_1+k_2+\cdots+k_r=N}{\sum_{k_1=0}^N \sum_{ k_2=0}^N \cdots \sum_{k_r=0}^N}\left(\begin{array}{c} N \\ k_1 k_2 \cdots k_r \end{array}\right) a_1^{k_1} a_2^{k_2} \cdots a_r^{k_r}. \end{align} 

It should be noted that the summation in (1.18) is over all nonnegative integers \(k_{1}, k_{2}, \ldots, k_{r}\) which sum to \(N\) .

The symbol \(\doteq\) is used in this book to denote approximate equality. It should be noted that tables of factorials and logarithms of factorials are available and may be used to evaluate expressions such as those in (1.20) .

Exercises