组合数学（张永刚）吉林大学 3.3 多重集的排列与组合.pptVIP

证明 采用组合分析的方法． 等式右端 是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： 证明组合恒等式的方法： 代数方法：通过代入组合数的值或已知的组合恒等式进行计算或化简，使等式两边相等． 二项式定理：可以比较展开式中xr的系数;可以在展开式中令x和y为某个特定的值;还可以利用幂级数的微商或积分等数学分析的方法来求得所需要的结果． 数学归纳法． 组合分析方法：说明等式两边都是对同一组合问题的计数． §3.4.5 非降路径问题 从（0，0）点到（5，6）点的一条非降路径，规定水平向右走一个单元格用x表示，垂直向上走一个单元格用y表示，则此路经对应于排列xyxxyyyxxyy。反过来，按照以上规则，给定排列xyxxyyyxxyy，就对应了如图所示的非降路径。 (0,0) (5,6) y x 一般地，一条从（0，0）点到（m, n）点的非降路径就是多重集{m?x，n?y}的一个排列。 反之，给定多重集{m?x，n?y}的一个排列就唯一地确定了一条从（0，0）点到（m, n）点的非降路径。 所以从（0，0）点到（m, n）点的非降路径数等于{m?x，n?y}的排列数，即二项 式系数 下面用非降路径的思想证明组合恒等式 C（m+n,m)=C(m+n,n) 由此可见非降路径实质上是二项式系数的一种几何解释。 (0,0) y x (m,n) (n,m) 对称性 例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) 再对k=0,1,…,r求和就得到所有的从(0,0)点到(m+n-r,r)点的非降路径数 所以等式成立 解 先考虑对角线下方的路径． 这种路径都是从(0,0),(1,0), (n,n-1)到达(n,n)点的． 我们可以把它看作是从(1,0)- (n,n-1)点的不接触对角线的非降路径。 例3.4.6 求从(0,0)点到(n,n)点的除端点外不接触直线y＝x的非降路径数． 对其中任意一条接触对角线的路径，我们可以把它从最后离开对角线的点(图中的A点)到(1,0)点之间的部分关于对角线作一个反射，就得到一条从(0,1)点,经过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) y x (0,1) (1,0) (n,n) A 不接触直线y＝x的非降路径数 (n,n-1) (1,0)-(n,n-1) 的路径数