Some basic principles of combinatorial analysis组合分析的一些基本原则Many problems in probability theory and in other branches of mathematics can be reduced to problems on counting the number of elements in a finite set. 许多概率论和其他一些数学分支上的问题,都可以简化成基于计算有限集合中元素数量的问题。Systematic methods for studying such problems form part of a mathematical discipline known as combinatorial analysis.研究这些问题的系统方法,是一个数学学科--组合分析的一部分。 In this section we digress briefly to discuss some basic ideas in combinatorial analysis that are useful in analyzing some of the more complicated problems of probability theory. 在本节,我们将离题简要地讨论一些组合分析的基本概念,它对于分析概率论中一些更复杂的问题是十分有用的。If all the elements of a finite set are displayed before us, there is usually no difficulty in counting their total number. 如果一个有限集合的所有元素都展示在我们面前,通常不会难以计算其元素的总数。More often than not, however, a set is described in a way that makes it impossible or undesirable to display all its elements. 然而,更多的往往是一些不能够描述或者不能够展示其所有元素的集合。For example, we might ask for the total number of distinct bridge hands that can be dealt. 例如,我们会问打桥牌时手牌的有多少种不同的组合。Each player is dealt 13 cards from a 52-card deck. 每个玩家处理从52张牌中发的13张牌。The number of possible distinct hands is the same as the number of different subsets of 13 elements that can be formed from a set of 52 elements.可能的不同手牌组合数相当于从含有52个元素的集合在中选出13个元素组成不同的子集的子集的个数。Since this number exceeds 635 billion, a direct enumeration of all the possibilities is clearly not the best way to attack this problem; 因为这个数字超过了635亿,直接枚举所有的可能性显然不是解决这个问题的最好方式。however, it can readily be solved by combinatorial analysis.然而,它可以很容易地用组合分析来解决。This problem is a special case of the more general problem of counting the number of distinct subsets of k elements that may be formed from a set of n elements (When we say that a set has n elements,we mean that it has n distinct elements.Such a set is sometimes called an n-element set.), where n >=k. Let us denote this number by f(n,k). 这个问题是一个更普遍的问题的一种特殊情况,一个含有n个元素的集合有多少个含有k个元素的子集,这里n大于等于k。 It has long been known that ,(12.1)我们用来表示,众所周知(12.1)where, as usual denotes the binomial coefficient,这里,像通常一样表示一个二项式In the problem of bridge hands we have different hands that a player can be dealt.在这个问题里面,每个玩家的可能手牌有种不同的情况。There are many methods known for proving(12.1). 有许多已知的方法可以证明(12.1)。A straightforward approach is to form each subset of k elements by choosing the elements one at a time. 一种直接的方法是,每次从原来的集合中取一个元素,共取k次构成一个含有k个元素的集合。There are n possibilities for the first choice, 1n possibilities for the second choice, and possibilities for the kth.第一次选择元素有n种可能,第二次有n-1种可能,依次类推,第k次有种可能n-(k-1)。If we make all possible choices in this manner we obtain a total ofsubsets of k elements.如果我们用这种方式做出所有可能的选择,那么一共有个k元素子集。Of course, these subsets are not all distinct. 当然,这些子集并不是都不相同。For example, if k =3 the six subsets{a,b,c},{b,c,a},{c,a,b},{a,c,b},{c,b,a},{b,a,c}are all equal.举个例子,如果k=3,这6个子集{a,b,c},{b,c,a},{c,a,b},{a,c,b},{c,b,a},{b,a,c}是相同的。In general, this method of enumeration counts each k-element subset exactly times. 在一般情况下,这种统计方式把每个k元素子集统计了k!次。Therefore we must divide the number by to obtain . This gives us, as asserted.因此,我们必须把除以k!来得到。以上确切的告诉我们。