样本与n元组

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 $(z_{1}, z_{2}, \dots, z_{n})$ is an array of $n$ symbols, $z_{1}, z_{2}, \dots, 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 $(z_{1}, z_{2}, \dots, z_{n})$ 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 $k = 1, 2, \dots, 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 $(z_{1}, z_{2}, \dots, z_{n})$ 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.

Example 1A . All possible samples of size 3 from an urn containing four balls . Let us consider an urn which contains four balls, numbered 1 to 4, and let a sample of size 3 be drawn. If the sampling is done without replacement, then the possible samples that can be drawn are

$(1, 2, 3)$ ,	$(2, 3, 1)$ ,	$(3, 4, 1)$ ,	$(4, 1, 2)$
$(1, 2, 4)$ ,	$(2, 3, 4)$ ,	$(3, 4, 2)$ ,	$(4, 1, 3)$
$(1, 3, 2)$ ,	$(2, 4, 1)$ ,	$(3, 1, 2)$ ,	$(4, 2, 3)$
$(1, 3, 4)$ ,	$(2, 4, 3)$ ,	$(3, 1, 4)$ ,	$(4, 2, 1)$
$(1, 4, 2)$ ,	$(2, 1, 3)$ ,	$(3, 2, 1)$ ,	$(4, 3, 1)$
$(1, 4, 3)$ ,	$(2, 1, 4)$ ,	$(3, 2, 4)$ ,	$(4, 3, 2)$

If the sampling is done with replacement, then the possible samples that can be drawn are

$(1, 1, 1)$ ,	$(2, 1, 1)$ ,	$(3, 1, 1)$ ,	$(4, 1, 1)$
$(1, 1, 2)$ ,	$(2, 1, 2)$ ,	$(3, 1, 2)$ ,	$(4, 1, 2)$
$(1, 1, 3)$ ,	$(2, 1, 3)$ ,	$(3, 1, 3)$ ,	$(4, 1, 3)$
$(1, 1, 4)$ ,	$(2, 1, 4)$ ,	$(3, 1, 4)$ ,	$(4, 1, 4)$
$(1, 2, 1)$ ,	$(2, 2, 1)$ ,	$(3, 2, 1)$ ,	$(4, 2, 1)$
$(1, 2, 2)$ ,	$(2, 2, 2)$ ,	$(3, 2, 2)$ ,	$(4, 2, 2)$

$(1, 2, 3)$ ,	$(2, 2, 3)$ ,	$(3, 2, 3)$ ,	$(4, 2, 3)$
$(1, 2, 4)$ ,	$(2, 2, 4)$ ,	$(3, 2, 4)$ ,	$(4, 2, 4)$
$(1, 3, 1)$ ,	$(2, 3, 1)$ ,	$(3, 3, 1)$ ,	$(4, 3, 1)$
$(1, 3, 2)$ ,	$(2, 3, 2)$ ,	$(3, 3, 2)$ ,	$(4, 3, 2)$
$(1, 3, 3)$ ,	$(2, 3, 3)$ ,	$(3, 3, 3)$ ,	$(4, 3, 3)$
$(1, 3, 4)$ ,	$(2, 3, 4)$ ,	$(3, 3, 4)$ ,	$(4, 3, 4)$
$(1, 4, 1)$ ,	$(2, 4, 1)$ ,	$(3, 4, 1)$ ,	$(4, 4, 1)$
$(1, 4, 2)$ ,	$(2, 4, 2)$ ,	$(3, 4, 2)$ ,	$(4, 4, 2)$
$(1, 4, 3)$ ,	$(2, 4, 3)$ ,	$(3, 4, 3)$ ,	$(4, 4, 3)$
$(1, 4, 4)$ ,	$(2, 4, 4)$ ,	$(3, 4, 4)$ ,	$(4, 4, 4)$

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}, \dots, N_{n}$ ; in symbols.

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)}, \dots, a_{N_{1}}^{(1)}$ of the first kind, $N_{2}$ objects $a_{1}^{(2)}, \dots, a_{N_{2}}^{(2)}$ of the second kind, and so on, up to $N_{n}$ objects $a_{1}^{(n)}, \dots, a_{N_{n}}^{(n)}$ of the $n$ th kind. We may then form $N_{1} N_{2} \dots N_{n}$ ordered n-tuples $(a_{j_{1}}^{(1)}, a_{j_{2}}^{(2)}, \dots, a_{j_{n}}^{(n)})$ containing one element of each kind.

Example 1B . A man has five suits, three pairs of shoes, and two hats. How many different combinations of attire can he wear?

Solution

A combination of attire is a 3-tuple $(a^{(1)}, a^{(2)}, a^{(3)})$ , in which $a^{(1)}, a^{(2)}, a^{(3)}$ denote, respectively, the suit, shoes, and hat worn. By the basic principle of combinatorial analysis there are $5 \cdot 3 \cdot 2 = 30$ combinations of attire.

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) \dots (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) \dots$ $(M - n + 1)$ . We adopt the notation $(M)_{n}$ . We thus define, for any positive integer $M = 1, 2, \dots$ , and for any integer $n = 1, 2, \dots, M$ ,

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 We can write $(M)_{n}$ in terms of the factorial notation by

In order that (1.4) may hold for $n = M$ , we define

In order that (1.4) may hold for $n = 0$ , we define

Example 1C . $(4)_{0} = 1, (4)_{1} = 4, (4)_{2} = 12, (4)_{3} = 24, (4)_{4} = 4! = 24$ . Note that $(4)_{5}$ is undefined at present. It is later defined as having value 0.

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, \dots, 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, \dots, 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

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, \dots$ , and integer $k = 0, 1, \dots, N$ , the symbol $(\binom{N}{k})$ by

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 $(\binom{N}{k})$ .

Example 1D . The subsets of size 3 of a set of size 4. Consider the set ${1, 2, 3, 4}$ . There are $(\binom{4}{3}) = 4$ subsets of size 3 that can be formed, namely, ${1, 2, 3}$ , ${1, 2, 4}$ , ${1, 3, 4}$ , ${2, 3, 4}$ . Notice that from each of these subsets one may draw without replacement six possible samples, so that there are twenty-four possible samples of size 3 to be drawn without replacement from an urn containing four balls.

The quantities $(\binom{N}{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$

It is convenient to extend the definitions of $(\binom{N}{k})$ and $(N)_{k}$ to any positive or negative integer $k$ . We define, for $N = 1, 2, \dots$ , if either $k < 0$ or $k > N$ .

We next note the extremely useful relation, holding for $N = 1, 2, \dots$ , and $k = 0, \pm 1, \pm 2, \dots$ ,

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 $(\binom{N}{k})$ , whereas the number of subsets of $S$ of size $k$ in which $t$ is present is $(\begin{matrix} N \\ k - 1 \end{matrix})$ ; the sum of these two quantities is equal to $(\begin{matrix} N + 1 \\ k \end{matrix})$ , 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: 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, \dots, N$ 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

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, $(\begin{array}{l} N \\ 1 \end{array})$ events of size $1, (\begin{array}{l} N \\ 2 \end{array})$ events of size $2, \dots, (\begin{array}{l} N \\ k \end{array})$ events of size $k, \dots, (\begin{matrix} N \\ N - 1 \end{matrix})$ events of size $N - 1$ , and $(\begin{array}{l} N \\ N \end{array})$ 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 $(t_{1}, t_{2}, \dots, t_{N})$ , 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, \dots, N}$ . Let $r$ be a positive integer and let $k_{1}, k_{2}, \dots, k_{r}$ be positive integers such that $k_{1} + k_{2} + \dots + k_{r} = N$ . By a partition of $S$ , with respect to $r$ and $k_{1}, k_{2}, \dots, 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}$ .

Example 1E . Partitions of a set of size 4 . The possible partitions of the set ${1, 2, 3, 4}$ into three subsets, the first subset of size 1, the second subset of size 2, and the third subset of size 1, may be listed as follows:

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} + \dots + k_{r} = N$ , is the product

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 $(\begin{array}{l} N \\ k_{1} \end{array})$ 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 $(\begin{matrix} N - k_{1} \\ k_{2} \end{matrix})$ ways. Continuing in this manner, we determine that the $r$ th subset, containing $k_{r}$ items, can be selected in $(\begin{matrix} N - k_{1} - \dots - k_{r - 1} \\ k_{r} \end{matrix})$ 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 $(\begin{array}{l} N \\ k \end{array})$ that Next, one obtains $(\begin{array}{l} N \\ k_{1} \end{array}) (\begin{matrix} N - k_{1} \\ k_{2} \end{matrix}) (\begin{matrix} N - k_{1} - k_{2} \\ k_{3} \end{matrix}) = \frac{N!}{k_{1}! k_{2}! k_{3}! (N - k_{1} - k_{2} - k_{3})!} .$

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 $N$ , and $r$ nonnegative integers $k_{1}, k_{2}, \dots, k_{r}$ whose sum is $N$ , we define the multinomial coefficient :

多项式系数得名于这样一个事实：它们是多项式形式 $a_{1} + a_{2} + \dots + a_{r}$ 的 $N$ 次幂展开式中，关于 $a_{1}, a_{2}, \dots, a_{r}$ 的幂的系数：

需要注意的是，(1.18) 中的求和是对所有和为 $N$ 的非负整数 $k_{1}, k_{2}, \dots, k_{r}$ 进行的。

例 1F . 桥牌手牌 . 桥牌游戏中，一位玩家可能获得的不同手牌数为 $(\binom{52}{13}) = 635, 013, 559, 600 ≐ (6.35), 10^{11}$ 因为一手桥牌由从52张牌中选出的13张牌组成。将一副桥牌分发给四家（按惯例标记为北、西、南、东）的方法数为

本书中使用符号 $≐$ 表示近似相等。需要注意的是，阶乘表和对数阶乘表是可用的，可以用来计算诸如 (1.20) 中的表达式。

习题

1.1 . 一家餐厅的菜单上有3种汤、10种肉菜、5种甜点和3种饮料。一份餐（包括汤、肉菜、甜点和饮料）有多少种点法？

答案

$450$ .

1.2 . 求下列各式的值：(i) $(5)_{3}$ , (ii) $(5)^{3}$ , (iii) 5! (iv) $(\binom{5}{3})$ .

1.3 . 一个大小为5的集合有多少个大小为3的子集？一个大小为5的集合有多少个子集？

答案

$10$ , $32$ .

1.4 . 将一副桥牌分成4手，每手13张，有多少种分法？

答案

$10$ .

1.5 . 五位政客在一次聚会上相遇。如果每位政客与其他每位政客都握手一次且仅一次，总共会进行多少次握手？

答案

(i) $70$ ; (ii) $2$ .

1.6 . 考虑一位大学教授，他每年在他的课上恰好讲3个笑话。如果他的原则是绝不在任何一年重复他在其他任何一年讲过的相同的3个笑话，那么他在35年里最少需要讲多少个笑话？如果他的原则是绝不重复讲同一个笑话，那么他在35年里最少需要讲多少个笑话？

1.7 . 一名学生参加一场8道题的是非判断题考试，如果 (i) 他将一半的题目标记为对，一半标记为错，(ii) 他不让任何两个连续答案相同，那么他有多少种答题方式？

答案

(i) $70$ ; (ii) $2$ .

1.8 . 通过观察，写出下式的值： $3^{4} + 4 \cdot 3^{3} + \frac{4 \cdot 3}{1 \cdot 2} \cdot 3^{2} + \frac{4 \cdot 3 \cdot 2}{1 \cdot 2 \cdot 3} \cdot 3 + 1.$

1.9 . 若 $(\binom{n}{11}) = (\binom{n}{7})$ ，求 $n$ 。若 $(\binom{18}{r}) = (\binom{18}{r - 2})$ ，求 $r$ 。

答案

$n = 18$ , $r = 10$ .

1.10 . 求下列各式的值：(i) $(\binom{5}{212})$ , (ii) $(\binom{5}{221})$ , (iii) $(\binom{5}{500})$ , (iv) $(\binom{5}{320})$ 。解释为什么 $(\binom{5}{320}) = (\binom{5}{3})$ 。

1.11 . 计算下列和式： $\sum_{k = 1}^{8} k^{2}, \sum_{i = 1}^{3} \sum_{j = 2}^{4} i j, \sum_{i = 1}^{3} \sum_{j = i + 1}^{4} i^{j}, \sum_{i = 1}^{3} \sum_{j = i + 1}^{4} j^{i} .$

答案

$204$ , $54$ , $108$ , $98$ .

1.12 . 给定一个包含 $n$ 个符号的字母表，可以组成多少个恰好由 $k$ 个符号构成的单词？据此，求英语中可以组成的3字母单词的可能数量。

1.13 . 求英语中可以组成的、首尾字母为辅音、中间字母为元音的3字母单词的数量。

答案

$2205$ .

1.14 . 使用 (1.11) 和数学归纳法原理来证明二项式定理，该定理由 (1.9) 陈述。

如果在一个 $n$ 元组中，当第一个分量已知时，可能出现的第二个分量的数量不依赖于已出现的第一个分量，则数 $N_{2}$ 存在。↩︎