组合数学ch032.ppt

§3.3 多重集的多重集的排列与组合排列与组合§3.3.1 多重集的排列多重集的排列§3.3.2 多重集的组合多重集的组合吉林大学吉林大学 多重集多重集中可以有重复的元素中可以有重复的元素 多重集合表示为多重集合表示为其中： 互不相同 M中有ki个ai（1≤i≤n）， 称ki为ai的重复度的重复度 ki是正整数，也可以是∞，表示M中有无限多个ai 例子例子• 是一个是一个10个元素的多重集合，个元素的多重集合，• 其中有其中有3个个a，，1个个b，，2个个c，，4个个d. • M表示为表示为  定理定理3.3.1 多重集合多重集合 的的r-排列数是排列数是nr 证明证明 在构造在构造M的一个的一个r-排列时，排列时，排列中的第一个元素有排列中的第一个元素有n种选择，种选择，第二个元素也有第二个元素也有n种选择，种选择，……，，第第r个元素也有个元素也有n种选择由于由于M中的每个元素都是无限次地重复，所以中的每个元素都是无限次地重复，所以r-排排列中的任意一项都有列中的任意一项都有n种选择，而且不依赖于前面种选择，而且不依赖于前面各项的选择，故各项的选择，故M的的r-排列数为排列数为nr §3.3.1 多重集的排列多重集的排列这个问题对应的这个问题对应的分配问题模型分配问题模型是：是：将将r个有区别的球放入个有区别的球放入n个不同的盒个不同的盒子中，且每个盒子的球数不加以限子中，且每个盒子的球数不加以限制，而且同盒的球不分次序，则不制，而且同盒的球不分次序，则不同的放法为同的放法为nr种种 若若M中每个元素的重复度大于等于中每个元素的重复度大于等于r，则，则结论仍然成立。

结论仍然成立 例例3.3.1 用用26个英文字母可以构造出个英文字母可以构造出多少个包含多少个包含2个元音字母（可以相同）个元音字母（可以相同）且长度为且长度为8的的“单词单词”解解 该问题是求是求 的包含的包含2个元音字母的个元音字母的8-排列数在排列数在长度度为8的字符串中，的字符串中，2个元音字母出个元音字母出现的位置的的位置的选取方式有取方式有 种，而每个元音位置可取种，而每个元音位置可取5个元个元音字母中的一个，剩余音字母中的一个，剩余6个个辅音字母的位置音字母的位置可取可取21个个辅音字母中的任一个，因而，音字母中的任一个，因而，满足足题意的意的“单词”有有 ·52·216个个.  证明明 首先把首先把M中所有的中所有的个元素看成是互不相同的，个元素看成是互不相同的，则全排列数全排列数为 但ki个个ai的位置相同，的位置相同，且其他元素排列也相同的排列且其他元素排列也相同的排列实质上是上是同一个排列同一个排列故故M的全排列数的全排列数为 例例3.3.2使用英文字母表中使用英文字母表中26个字母构成个字母构成8个字个字母的单词且母的单词且允许字母重复允许字母重复，如果要求每个单词至，如果要求每个单词至少含有少含有3个元音字母，那么能构成多少个这样单词个元音字母，那么能构成多少个这样单词解解 因为一共有因为一共有5个元音字母，每个单词至个元音字母，每个单词至少含有少含有3个元音字母即包含个元音字母即包含3个，个，4个或者个或者5个元音字母。

则分三种情况，个元音字母则分三种情况，有有3个元音字母的单词有个元音字母的单词有有有4个元音字母的单词有个元音字母的单词有有有5个元音字母的单词有个元音字母的单词有根据加法原理共根据加法原理共例例3.3.3 求多重集求多重集 的的8-排列数排列数解解 可分三种情况可分三种情况计算：算： M-{a}的的8-排列数排列数, 即即为 排列数排列数 为：： M-{b}的的8-排列数排列数,即即为 排列数排列数 为：： M-{c}的的8-排列数排列数,即即为 排列数排列数 为：： 多重集多重集M的的8-排列数排列数为 420+280+560=1260 例例3.3.4 从从4个个a，，4个个b，，4个个c，，4个个d中选中选择字母形成一个择字母形成一个10个字母的序列，如果每个字母的序列，如果每个字母至少出现两次，有多少种方法形成个字母至少出现两次，有多少种方法形成这样的序列这样的序列 解解 这个问题实际上是求这个问题实际上是求 的的10-排列数，但要求每个排列数，但要求每个10排列中包含排列中包含a,b,c,d每个字母至少两个。

每个字母至少两个我们设我们设 ，则原问题可以分成如下两大类共，则原问题可以分成如下两大类共10种种情况：情况：（一）（一） 的的10-排列数排列数; 的的10-排列数；排列数； 的的10-排列数：排列数：的的10-排列数，排列数，这这4种类情况的种类情况的10-排列数相等，均为排列数相等，均为（二）（二） 的的10-排列数排列数; 的的10-排列数；排列数； 的的10-排列数：排列数：的的10-排列数；排列数； 10-排列数；排列数； 的的10-排列数排列数这这6种类情况的种类情况的10-排列数相等，均为排列数相等，均为•满足条件的方法数为满足条件的方法数为 • 多重集的排列问题小结：多重集的排列问题小结：§3.3.2 多重集的组合多重集的组合• 多重集合的r-组合是指从M中无序地选出r个元素例子例子Ø 如果多重集M有n个元素(包括重复的元素)，则M的n-组合只有一个，就是M本身。

Ø 如果M有n种不同元素，则M的1-组合恰有n个 证明证明1 (1) M的任何一个的任何一个r-组合都具有以下形组合都具有以下形式式其中其中 是非负整数，则有是非负整数，则有反之，若给出方程反之，若给出方程的非负整数解的非负整数解 就是就是M的一个的一个r-组合所以多重集所以多重集M的的r-组合数就等于方程组合数就等于方程的非负整数解的个数的非负整数解的个数（（2）方程）方程 的一个非负整数解可以的一个非负整数解可以表示为表示为{(n-1)•0, r•1}的一个全排列，的一个全排列， 1 1 … 1 1 0 1 1 … 10 …01 1 1 … 011…11， x1个 x2个 xn个反之反之{(n-1)•0, r•1}的一个全排列，在这个排的一个全排列，在这个排列中列中n-1个个0把个把个1分成个组。

分成个组• 从左边数，第一个从左边数，第一个0左边的左边的1的个数为的个数为x1，，第一个第一个0和第二个和第二个0之间的之间的1的个数为的个数为x2 ，依，依此类推，最后一个此类推，最后一个0右边的右边的1的个数为的个数为xn ，则，则 是一组非负整数解是一组非负整数解 • 因此因此 的非负整数解与的非负整数解与集合的全排列之间是一一对应集合的全排列之间是一一对应• 由由(1)(2)知，知，M的的r-组合数等于组合数等于的全排列数，根据定理的全排列数，根据定理3.3.2，多重集，多重集M的的r组合数为组合数为 方法方法2 分析定理的结论， 是(n+r-1)元普通集合的r-组合数，因此我们想办法构造多重集合 的r-组合与某一(n+r-1)元的普通集合S的r组合之间的一一对应，从而证明定理的结论. 证明如下：为表达方便，将证明如下：为表达方便，将中中n种不同元素用数字种不同元素用数字1,2,…,n替换，这样每个替换，这样每个r-组合具有形式组合具有形式 不妨设不妨设令令 ，即，即则则显然显然 与与 一一对应，一一对应，而而 是是(n+r-1)元集合的元集合的r-组合，其数组合，其数量为量为 ，从而原结论成立，从而原结论成立. 定理3.3.4 设多重集设多重集r≥n，则，则M中每个元素至少取一个的中每个元素至少取一个的r-组组合数为合数为证明证明 设设 是满足条件的任一是满足条件的任一r-组合，则有组合，则有令令 则则显然显然 其中的整数解个数等于方其中的整数解个数等于方程程 的非负整数解的个数。

的非负整数解的个数由定理由定理3.3.3，满足定理条件的组合数为，满足定理条件的组合数为例例3.3.5 求集合求集合S={1,2,…,n}的的r-组合数，其组合数，其中要求中要求r-组合中任意两个元素在组合中任意两个元素在S中都不是中都不是相邻的 如当如当n=5，，r=3时，时，S={1,2,3,4,5,6}，，{1,3,5}是满足条件的是满足条件的3-组合，而组合，而{1,2,6}是不满足条是不满足条件的件的3-组合，因为组合，因为1,2在在S中是相邻的中是相邻的解解 考虑考虑S的任意一个的任意一个r-组合组合 ，，不妨设不妨设 我们把我们把1,2,…,n这这n个数按从小到大的顺序排成一个序列，其个数按从小到大的顺序排成一个序列，其中我们只把标识出来，其余数字用中我们只把标识出来，其余数字用“……”表示 在序列中每个在序列中每个ji后面用以竖线后面用以竖线““|””标记，标记，则设第则设第1个竖线前面的数字个数为个竖线前面的数字个数为x1，第，第1个竖线与第个竖线与第2个竖线间的数字个数为个竖线间的数字个数为x2，，…，第，第r个竖线前面的数字个数为个竖线前面的数字个数为xr+1。

根据题意，因为根据题意，因为 中任意两个数中任意两个数都彼此不相邻，所以满足：都彼此不相邻，所以满足：x1≥1，，x2≥2，，…，，xr≥2，，xr+1≥0，，因为一共有因为一共有n个数字，所以个数字，所以x1+x2+x3+…+xr+xr+1=n 这样原问题要求的r-组合数就等价于方程x1+x2+…+xr+xr+1=n满足条件x1≥1，x2≥2，…，xr≥2，xr+1≥0的整数解个数进行代换，令y1=x1-1，y2=x2-2，…，yr=xr-2，yr+1=xr+1，则y1≥0，y2≥0，…，yr≥0，yr+1≥0，且y1+y2+…+yr+yr+1=n-1-2(r-1)根据定理3.3.3的证明：这个方程的非负整数解个数是：因此满足条件不相邻条件的r-组合数为 例例3.3.6 从从4个个a，，4个个b，，4个个c，，4个个d中无中无序选取序选取10个字母，如果每个字母至少包含个字母，如果每个字母至少包含两个，则有多少种取法两个，则有多少种取法解解 这个问题实际上是求多重集的这个问题实际上是求多重集的10-组合数，组合数，且且10-组合中每个字母至少包含两个。

显然，组合中每个字母至少包含两个显然，这个问题等价于方程这个问题等价于方程x1+x2+x3+x4=10，其满，其满足足条件条件x1≥2，，x2≥2，， x3≥2，，x4≥2的整数解个的整数解个数进行代换，令数进行代换，令y1=x1-2，，y2=x2-2，，y3=x3-2，，y4=x4-2，则，则y1≥0，，y2≥0，，y3≥0，，y4≥0，，且且y1+y2+y3+y4=2根据定理根据定理3.3.3，其非负整，其非负整数解数为数解数为 ，因此共有，因此共有10种取法• 多重集的组合问题小结：多重集的组合问题小结：思考：思考：设s={3.a,4.b,5.c,6.d}，求从中分别取得3个、4个和5个元素的组合数例例 将6个蓝色球，5个红色球，3个白色球排成一排，要求白色球不挨着，问有多少种排列方式？§3.4 二项式定理二项式定理 ا3.4.1 和式和式ا3.4.2 二项式定理二项式定理ا3.4.3 二项式定理的推广二项式定理的推广ا3.4.4 组合恒等式组合恒等式ا3.4.5 非降路径问题非降路径问题在组合数学中求和是最基本的运算在组合数学中求和是最基本的运算而表示法的引入给求和问题的表示和运算都而表示法的引入给求和问题的表示和运算都带来了极大的便捷。

带来了极大的便捷例如，我们求例如，我们求1到到n的正整数的和原来写成的正整数的和原来写成1+2+…+n，有了，有了 表示法，就可以表示成表示法，就可以表示成§3.4.1 和式和式• 一般地，表示法的和式为 ，表示•，读作“k从1到n对ak求和”•这种表示方法可以推广，即把难以表达或者复杂的k的取值范围写到下方和式具有如下的性质 （1） ，其中c为与k无关的常量；（2） （3） 例例3.4.1 求和 解解 令因为0≤k≤n，所以0≤n-k≤n，根据性质3，根据性质2，将S的两个表达式相加，有：根据性质1因此例例3.4.2 对于任意正整数n，给出 关于n的计算公式 方法方法1 我们观察图我们观察图3.3.1中两个方阵，它们中两个方阵，它们是完全相同的，我们采用不同的方式求和是完全相同的，我们采用不同的方式求和12345… n2345… n345… n45… n5… n … …n12345… n2345… n345… n45… n5… n … …n对于图(a)，一列一列看，第1列1个1，第2列2个2，…，第n列n个n，如果按列求和，第1列为12，第2列为22，…，第n列n2，则所有数字的和恰好是对于图(b)，按行求和，第1行为 ，第2行为 ，…，第n行为 ，则所有数字的和恰好是因为图(a)和图(b)中的数字完全相同，所以首先设 方法方法2 首先设 推出 因此 §3.4 二项式定理二项式定理 ا3.4.1 和式和式ا3.4.2 二项式定理二项式定理ا3.4.3 二项式定理的推广二项式定理的推广ا3.4.4 组合恒等式组合恒等式ا3.4.5 非降路径问题非降路径问题§3.4.2 二项式定理二项式定理定理定理3.4.1 (二项式定理二项式定理)设n是正整数,则对任意的x,y有：• 二项式系数二项式系数二项式系数的基本性质二项式系数的基本性质（1）对称关系 （2）递推关系 （3）单峰性n为偶数时，有n为奇数时，有 性质（性质（2）的证明）的证明 利用的组合意义来证。

利用的组合意义来证n元集合元集合 的的k元子集可以分成元子集可以分成两类：两类： 第一类第一类k元子集含元子集含a1; 第二类第二类k元子元子集不含集不含a1•第一类第一类k元子集中的任一个去掉元子集中的任一个去掉a1后，就后，就是是S- {a1}的的k-1元子集；反过来，任给一个元子集；反过来，任给一个的的k-1元子集，添上元子集，添上a1后就是后就是S的的k元子集，元子集，故二者这间有一一对应关系故二者这间有一一对应关系.因而，第一类因而，第一类k元子集共有元子集共有 个个.第二类第二类k元子集就是元子集就是S- {a1}的的k元子集，共有元子集，共有 个个.所以所以• 性质性质2又叫又叫Pascal公式公式,可得杨辉三角可得杨辉三角性质（性质（3）的证明）的证明 证明：证明：设1≤k≤n，考虑 与 之比： 若n为偶数，则 为整数，于是（i）若k≤ ，则 所以（ii）若 ，则 所以定理定理3.4.1 (二项式定理二项式定理)设n是正整数,则对任意的x,y有：证明证明 用组合分析的方法证明。

用组合分析的方法证明等式左边是等式左边是n个（个（x+y）因子相乘，即）因子相乘，即这些因子展开到没有括号为止在展开时，这些因子展开到没有括号为止在展开时，每个因子中均可贡献一个每个因子中均可贡献一个x或一个或一个y由乘法原理，共有原理，共有2n项，这些项都可写成项，这些项都可写成 的形式可以在的形式可以在n个个x+y因子中选出因子中选出k个，从这个，从这k个因子中取个因子中取x，而在另外的，而在另外的n-k个因子中取个因子中取y，如此得到项，所以的系数等于，如此得到项，所以的系数等于n个因子的个因子的k-组合数，即组合数，即 因此二项式定理的几种特殊形式二项式定理的几种特殊形式（1）（2）（3） 推论推论3.4.1 设设n是正整数，对一切是正整数，对一切x有有推论推论3.4.2 对任何正整数对任何正整数n有有推论推论3.4.3 对任何正整数对任何正整数n有有推论推论3.4.3证明证明 在二项式定理中令x=-1, y=1,得 将上式整理一下即得原等式成立。

§3.4.3 二项式定理的推广二项式定理的推广 (1) 牛顿二项式定理牛顿二项式定理(2)多项式定理多项式定理(1) 牛顿二项式定理牛顿二项式定理v 定义定义 对于任何实数对于任何实数a和整数和整数k，，有有定理定理3.4.2 (牛顿二项式定理牛顿二项式定理) 设设a是一个实数，则对一切是一个实数，则对一切x和和y，，满足满足有有其中其中 1,当当a=n(正整数正整数)时，如果时，如果k＞＞n，，则则这时牛顿二项式定理就变成下面的形式这时牛顿二项式定理就变成下面的形式这就是这就是二项式定理二项式定理，，所以二项式定理所以二项式定理是牛顿二项式定理的特例是牛顿二项式定理的特例 2, 当当a=-n(负整数负整数)时，有时，有3, 当当a=-1时，有时，有4, 当当a=1/2时，有时，有v 定理定理3.4.3 (多项式定理多项式定理) 设设n是正整数，则是正整数，则其中其中称为多项式系数称为多项式系数，并且是对所有满足，并且是对所有满足n1+n2+…nt=n 的非负整数解的非负整数解 n1,n2,…,nt求求和2) 多项式定理多项式定理 证明证明 (1) 先将先将(x1+…+xt)n写成写成n个个(x1+…+xt)因子的乘积：因子的乘积：将其展开，直到没有括号为止。

因为每个将其展开，直到没有括号为止因为每个因子中都可取因子中都可取x1, x2, …,xt中的任一个，所中的任一个，所以展开式共有以展开式共有tn项，且每项都可以写成项，且每项都可以写成 的形式的形式.要得到这一项，我们应要得到这一项，我们应该在该在n个因子中的个因子中的n1个里面取个里面取x1，有，有 种取种取法；在剩下的法；在剩下的n-n1个因子中的个因子中的n2个里面取个里面取x2，有，有 种取法；种取法；……；；最后，在最后，在个因子里面取个因子里面取xt，有，有种取法种取法.由乘法原理知，由乘法原理知， 前的系数前的系数为为v 在多项式定理中如果取在多项式定理中如果取t＝＝2，，就得到普就得到普通的二项式定理通的二项式定理.v 多项式系数组合意义如下：多项式系数组合意义如下：是多项式是多项式(x1+…+xt)n中中项的系数项的系数v 是多重集是多重集S={n1.a1,n2.a2,…,nt.at}的排列数的排列数v 如果我们把如果我们把n个不同的球放到个不同的球放到t个不同个不同的盒子里的盒子里,并且使得第一个盒子里有并且使得第一个盒子里有n1个个球，第二个盒子里有球，第二个盒子里有n2个球个球,…,第第t个盒子个盒子里有里有nt个个球，那么放球的方案数是球，那么放球的方案数是例例3.4.3 展开的系数为 Ø 例例 求求(2x1-3x2+5x3)6中中 项的系数项的系数解解: 推论推论3.4.4 (x1+…+xt)n的展开式在合并同的展开式在合并同类项以后不同的数目是类项以后不同的数目是 证明证明 (x1+…+xt)n的展开式中任何一项对应的展开式中任何一项对应于方程于方程 n1+n2+…nt=n的一组非负整数解，的一组非负整数解，所以合并同类项后不同的项数等于这个方所以合并同类项后不同的项数等于这个方程的非负整数解的个数程的非负整数解的个数 推论推论3.4.5其中求和是对方程其中求和是对方程n1+n2+…nt=n 的一切的一切非负整数解来求。

非负整数解来求证明证明: 在多项式定理中令在多项式定理中令x1=x2=…=xt=1即可即可.§3.4.4 组合恒等式组合恒等式证明证明 对等式对等式两边微分得两边微分得然后令然后令x=1得得等式成立等式成立证明证明 对等式对等式两边积分得两边积分得然后令然后令x=-1得得成立成立即即 证明证明 采用采用组合分析组合分析的方法．的方法．等式右端等式右端 是是n+1元集合元集合S={a1,a2,…,an+1}的的k+1元子集的个数，这些子集可以分成如元子集的个数，这些子集可以分成如下下n+1类：类：第第(0)类：类：k+1元子集中含元子集中含 a1，这相当于，这相当于S-{a1} 的的k元子集再加上元子集再加上 a1构成构成S的的k+1元子集，元子集，共共 个个第第(1)类：不含类：不含a1但含但含a2的的k+1元子集，元子集， 共有共有 个个……；；第第(n)类：不含类：不含a1,a2,…, an但含但含an+1的的k+1元子元子集，共有集，共有 个个.由加法原理知由加法原理知所以等式成立所以等式成立证明证明 采用组合分析的方法。

采用组合分析的方法 是是2n元集合元集合S的的n-组合数，把集合组合数，把集合S分成两个集合分成两个集合S1和和S2，使，使 ，则，则S的的n元子集可以分成如下元子集可以分成如下n+1类：类：•从从S1中选取中选取i（（0≤≤i≤≤n）个元素，）个元素，•从从S2中选取中选取n-i个元素，个元素，•将将S1的的i个元素与个元素与S2的的n-i个元素并到一起构成个元素并到一起构成S的第的第i类类n元子集•而第而第i类子集的个数为类子集的个数为 由加法原理，有由加法原理，有 即原等式成立即原等式成立 证明证明此恒等式是恒等式（此恒等式是恒等式（4）的推广，）的推广， 被称为被称为Vandermonde恒等式恒等式. 由二项式定理有由二项式定理有比较等式两边比较等式两边xr的系数，左边是的系数，左边是右边是右边是证明证明 方法方法1：：由二项式定理有由二项式定理有对上式两边对对上式两边对x微分得微分得等式两边乘以等式两边乘以x得得等式两边对等式两边对x微分得：微分得：令令x=1则：则：即：即： 方法方法2：：§3.4.5 非降路径问题非降路径问题一一条非降路径，条非降路径，规定规定•水水平向右平向右走一个单元格用走一个单元格用x表示表示•垂垂直向上直向上走一个单元格用走一个单元格用y表示表示(0,0)(5,6)yx•一条从（一条从（0，，0）点到（）点到（m, n）点的非降路）点的非降路径就是多重集径就是多重集{m•x，，n•y}的一个排列。

的一个排列• 反之，反之，给定多重集定多重集{m•x，，n•y}的一个排列的一个排列就唯一地确定了一条从（就唯一地确定了一条从（0，，0）点到（）点到（m, n）点的非降路径点的非降路径• 所以从（所以从（0，，0）点到（）点到（m, n）点的非降）点的非降路径数等于路径数等于{m•x，，n•y}的排列数，即二的排列数，即二项式系数式系数 或或 •下面用非降路径的思想证明组合恒等式下面用非降路径的思想证明组合恒等式•由此可由此可见非降路径非降路径实质上是二上是二项式系式系数的一种几何解数的一种几何解释例例3.4.4 证明：证明：证明：证明： 是从是从(0,0)点到点到(m,n)点的非降点的非降路径数这些路径可以分成两类：路径数这些路径可以分成两类：• 一类由（一类由（0,0）点经由（）点经由（m-1, n）点到）点到达（达（m, n）点，共有）点，共有 条；条；•另一类经由（另一类经由（m, n-1）点到达（）点到达（m, n））点，共有点，共有 条，条，•根据加法原理，等式成立。

根据加法原理，等式成立例例3.4.5 证明证明证明证明: 等式右端等式右端表示从表示从(0,0)点到点到(m+n-r,r)点的非点的非降路径数任何降路径数任何一条这样的非降一条这样的非降路径一定经过图路径一定经过图中斜线上的点，中斜线上的点，按所经过点的不按所经过点的不同将路径分类同将路径分类• 从从(0,0)点到点到(m-k,k)点的非降路径是点的非降路径是 条条•从从(m-k,k)点到点到(m+n-r,r) 非降路径是非降路径是 条条•由乘法原理，可知从由乘法原理，可知从(0,0)点经过点经过(m-k,k)点点的非降路径是的非降路径是 条条•再对再对k=0,1,…,r求和就得到所有的从求和就得到所有的从(0,0)点点到到(m+n-r,r)点的非降路径数点的非降路径数•所以等式成立所以等式成立解解 先考虑对角线下方的路径．先考虑对角线下方的路径．这种路径都是从这种路径都是从(0,0)点出发经过点出发经过(1,0)点及点及(n,n-1)点到达点到达(n,n)点的．我们可点的．我们可以把它看作是从以把它看作是从(1,0)点出发到达点出发到达(n,n-1)点的不接触对角线的非降路径。

从点的不接触对角线的非降路径从(1,0)点到点到(n,n-1)点的所有的非降路径点的所有的非降路径数是数是 例例3.4.6 求从求从(0,0)点到点到(n,n)点的除端点点的除端点外不接触直线外不接触直线y＝＝x的非降路径数．的非降路径数．对其中任意一条接触对角线的路径，我们对其中任意一条接触对角线的路径，我们可以把它从最后离开对角线的点可以把它从最后离开对角线的点(图中的图中的A点点)到到(1,0)点之间的部分关于对角线作一点之间的部分关于对角线作一个反射，就得到一条从个反射，就得到一条从(0,2)点出发经过点出发经过A点到达点到达(n,n-1)点的非降路径．点的非降路径．反之，任何一条从反之，任何一条从(0,1)点出发（必穿过）点出发（必穿过）直线直线y=x而到达而到达 (n,n-1)点的非降路径，也点的非降路径，也可以通过这样的对称变换得到一条从可以通过这样的对称变换得到一条从(1,0)点出发接触到对角线而到达点出发接触到对角线而到达(n,n-1)点的非点的非降路径．降路径．从而在直线从而在直线y=x下方不接触直线下方不接触直线y=x的路的路径数是径数是由对称性可知，所求的路径数是由对称性可知，所求的路径数是从从(0,1)点到达点到达(n,n-1)点的非降路径数是点的非降路径数是(0,0)yx(0,1)(1,0)(n,n)A解解 首先考虑直线首先考虑直线y=x下不穿过直线下不穿过直线y=x的路径，这种路径都是的路径，这种路径都是(1,0)经过经过(n,n-1)点到达点到达(n,n)点的，其路径数为点的，其路径数为 根据非降路径的定义，任意一条从根据非降路径的定义，任意一条从(1,0)点并经过点并经过(n,n-1)点到达点到达 (n,n)点点的穿过直线的穿过直线y=x的非降路径都对应接触的非降路径都对应接触直线直线y=x+1的非降路径。

的非降路径例例3.4.7 求从求从(0,0)点到点到 (n,n)点的除端点点的除端点外不穿过直线外不穿过直线 的非降路径数的非降路径数• 设从设从(1,0)点到点到(n,n-1)点接触直线点接触直线y=x+1的非降路径最后一次离开直线的非降路径最后一次离开直线y=x+1的点为的点为B，将，将(1,0)点和点和B点之间的部分关于直线点之间的部分关于直线y=x+1作对称图形，则得到从作对称图形，则得到从 (-1,2)点到达点到达(n,n-1)点的穿过直线点的穿过直线y=x+1的非降路径的非降路径•反之，任何一条从反之，任何一条从(-1,2) 点出发穿过直线点出发穿过直线y=x+1而到达而到达(n,n-1)点的非降路径，也可以点的非降路径，也可以通过这样的对称变换得到一条从通过这样的对称变换得到一条从(1,0)点出点出发接触直线发接触直线y=x+1而到达而到达 (n,n-1)点的非降点的非降路径路径• 路径数为路径数为 • 由对称性可知，所求的路径数是由对称性可知，所求的路径数是B例例3.4.8 一场演唱会门票为50元一张，排队买票的歌迷中有m个人手持50元纸币，n个人手持100元纸币。

若售票处没有准备零钱，求有多少种排队方法能使购票顺利进行，而不出现找不出钱的状态假定每个人只能购票1张，而且m>n. 解解 根据题意，要满足总是能找出零钱，就意味着对于队列中每个歌迷而言，她前面的人（包括她在内）中持50元的人不少于持100元的人显然是求从（0，0）到（m,n）不穿过直线y=x且在y=x下方的非降路径数，根据例3.4.7，为(1,0 )点到(m,n)点非降路径数—(-1,2 )点到(m,n)点非降路径数，即： 。