Samples and n-Tuples

A basic tool for the construction of sample description spaces of random phenomena is provided by the notion of an -tuple. An -tuple is an array of symbols, , 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 -tuple are written is of importance (and consequently one sometimes speaks of ordered -tuples). Two -tuples and are said to be identical, or indistinguishable, if and only if they consist of the same components written in the same order; symbolically, for . The usefulness of -tuples derives from the fact that they are convenient devices for reporting the results of a drawing of a sample of size .

A basic random phenomenon with whose analysis we are concerned in probability theory is that of sampling . Suppose we have an urn containing balls, which are numbered 1 to . Suppose we draw balls from the urn one at a time, until balls have been drawn; for brevity, we say we have drawn a sample (or an ordered sample) of size . 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 th draw is . Consequently, if the drawing is done without replacement , then the size of the sample drawn must be less than or equal to , the original number of balls in the urn. On the other hand, if the drawing is done with replacement, then may be any number.

To report the result of drawing a sample of size , an -tuple is used, in which represents the number of the ball drawn on the first draw, represents the number of the ball drawn on the second draw, and so on, up to , which represents the number of the ball drawn on the 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 -tuples, which arise in various ways, may be counted. We now state a formula that is basic to the theory of counting sets of -tuples and that may be called the basic principle of combinatorial analysis .

Suppose there is a set whose members are ordered -tuples of objects of some sort. In order to compute the size of , first determine the number of objects that may be used as the first component of an -tuple in . Next determine ( if it exists ¹ ) the number of objects that may be second components of an -tuple, of which the first component is known. Then determine (if it exists) the number 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 (if it exists) of objects that may be the th component of an -tuple, of which the first components are known, has been determined. The size of the set of -tuples is then given by the product of the numbers ; in symbols.  

As a first application of this basic principle, suppose that we have different kinds of objects. Suppose that we have objects of the first kind, objects of the second kind, and so on, up to objects of the th kind. We may then form ordered n-tuples containing one element of each kind. 

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

The number of ways in which one can draw a sample of balls from an urn containing distinguishable balls is , if the sampling is done without replacement, and , if the sampling is done with replacement. 

To show the first of these statements, note that there are possible choices of numbers for the first ball drawn, choices of numbers for the second ball drawn, and finally choices of numbers for the th ball drawn. The second statement follows by a similar argument, since for each of the balls in the sample there are choices.

Various notations have been adopted to denote the product . We adopt the notation . We thus define, for any positive integer , and for any integer ,

Another notation with which the reader should be familiar is that of the factorial. Given any positive integer , we define ! (read, factorial) as the product of all the integers, 1 to . Thus We can write in terms of the factorial notation by  

In order that (1.4) may hold for , we define  

In order that (1.4) may hold for , we define  

An important application of the foregoing relations is to the problem of finding the number of subsets of a set . Consider the set , which consists of all integers, 1 to . How many possible subsets of can be formed? In order to solve this problem, we first find for , the number of subsets of of size that can be formed. Let be the number of subsets of of size . We shall prove that satisfies the relationship , so that  

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

We now introduce some notation. We define, for any integer , , and integer , the symbol by  

Equation (1.7) may be restated as follows: the number of subsets of size that may be formed from the members of a set of size is . 

The quantities are generally called binomial coefficients because of the role they play in the binomial theorem, which states that for any two real numbers and and any positive integer \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 and to any positive or negative integer . We define, for , if either or .

We next note the extremely useful relation, holding for , and ,  

This relation may be verified directly from the definition of binomial coefficients. An intuitive justification of (1.11) can be obtained. Given a set , with members, choose an element in . The number of subsets of of size in which is not present is equal to , whereas the number of subsets of of size in which is present is ; the sum of these two quantities is equal to , the total number of subsets of of size .

Equation (1.11) is the algebraic expression of a fact represented in tabular form by Pascal’s triangle: 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 and To prove (1.12) one need note only that each side of the equation is equal to !.

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 one may form. From the binomial theorem (1.9) , with , it follows that  

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 is . For there is one impossible event, events of size events of size events of size events of size , and events of size . There is an alternate way of showing that if has members then it has subsets. Let the members of be numbered 1 to . To describe a subset of , we may write an -tuple , whose th component is equal to 1 or 0, depending on whether the th member of does or does not belong to the subset . Since one can form -tuples, it follows that possesses subsets.

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

We now prove that the number of ways in which one can partition a set of size into ordered subsets so that the first subset has size , the second subset has size , and so on, where , is the product  

To prove (1.14) we proceed as follows. For the first subset of items there are items available, so that there are ways in which the subset of items can be selected. There are items available from which to select the items that go into the second subset; consequently, the second subset, containing items, can be selected in ways. Continuing in this manner, we determine that the th subset, containing items, can be selected in ways. By multiplying these expressions, we obtain the number of ways in which a set of size 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 that Next, one obtains

Continuing in this manner, one finds that (1.14) is equal to  

Quantities of the form of (1.16) arise frequently, and a special notation is introduced to denote them. For any integer , and nonnegative integers whose sum is , we define the multinomial coefficient :

The multinomial coefficients derive their name from the fact that they are the coefficients in the expansion of the th power of the multinomial form in terms of powers of : \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 which sum to .