第六章 组合1排列组合.ppt

1.9例题 另一方面任一串与最近的码字的距离不大于2r， 否则此串本身可作为一新的码字，即以2r位半径 的各码字为球心，应当使任一串落入某球内,故 综合上两式,有 例3 从号码1,2,…N中每次取出一个并登记，然后放回，连取n次，得到一个由n个数字组成的数列，问按这种方式能得到 (1)多少个严格递增数列(n = N); (2)多少个不减数列？ 解(1) C(N.n) (2) C(N+n-1,n) 1.9 例题 1.9 例题 例4 凸n边形没有3条对角线交于一点。计算各边及各对角线所组成的互不重叠的多边形区域的个数 1.9 例题 解 令Nk:区域中k边形的个数。 从两种角度计算各区域的顶点数(包含重复计得的数目)首先可以如下计算 其中m是最大多边形的边数。 另一方面，每两条对角线决定一个内部多边 形的顶点，因此(1)式中计算内部的多边形 顶点数所得数值是4C(n,4)(每个内部顶点在(1)式中重复计算4次，因为总是4个区域共一个顶点) 1.9 例题 而(1)中凸多边形的每个顶点重复计数n-2次，故 现在，再从两个角度来计算所有区域的内 角和的总和，首先，它显然是 1.9 例题 * 1.9 例题 例5 试求从1到1000000的整数中，0出现的次数。 解：先将1到999999的整数都看作6位数,例如2就看作是000002，这样从000000到999999。0出现了多少次呢？ 6×105，某一位取0，其它各位任取。 0出现在最前面的次数应该从中去掉 000000到999999中最左1位的0出现了105次， 000000到099999中左数第2位的0出现了104次，　 000000到009999左数第3位的0出现了103次, 000000到000999左数第4位的0出现了102次, 000000到000099左数第5位的0出现了10次, 000000到000009左数第6位的0出现了1次。 * 1.9 例题 因此不合法的0的个数为105+104+103+102+101+1=111111， 不合法的应该去掉，再加整数1000000中的6个0，这样，从1到1000000的整数中0出现的次数为6×105-111111+6=488895。 * 7* 1.9 例题 例6 试证任意r个相邻数的连乘 (n+1)(n+2)...(n+r)=(n+r)!/n!被r!除尽。 证：从n+r个元素中取r个的组合数，C(n+r,r)=(n+r)!/n!r! * * 1.6.4组合的生成 [例27] 在C(10,4)中 4679的序号是首位小于4的组合的个数；首位是4，第2位小于6的组合的个数；前2位是46，第3位小于7的组合的个数；前3位是467，第4位小于9的组合的个数之和。 反之，也可以由序号求组合。 从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？ 1.7 组合意义的解释 非降路径问题 y x (m,n) . . . . . . 0 无论怎样走法,总有：在x方向上总共走m 步，在y 方向上总共走n步。若用一个x表示x方向上的一步, 一个字母y表示y方向上的一步。则(0,0)→(m,n)的 每一条路径可表示为m 个x与n个y的一个可重排列。 设所求方案数为 P(m+n; m, n),则 1.7 组合意义的解释 1.7 组合意义的解释 (c,d) (a,b) 故 P(m+n;m,n) =C(m+n,m) 于是 设c≥a,d≥b,则由(a,b)到(c,d)的非降路径数为 例1 在上例的基础上若设mn，求(0,1)点到(m,n)点不接触对角线x=y的非降路径的数目 (“接触”包括“穿过”)? 1.7 组合意义的解释 对每一条接触x=y 的非降路径，做(0,1)点到第一个 接触点部分关于x=y的对称非降路径，这样得到一 条从(1,0)到(m,n)的非降路径。 从(0,1)点到(m,n)点的非降路径，有的接触x=y，有 的不接触。 容易看出从(0,1)到(m,n)接触x=y的非降路径与 (1,0)到(m,n)的非降路径(必穿过x=y)一一对应. y y=x (m,n) 0 (1,0) x (0,1) . . y x-y=1 (m,n) x (0,0) (1,-1)