《组合数学组合意义解释和应用举例》由会员分享，可在线阅读，更多相关《组合数学组合意义解释和应用举例（30页珍藏版）》请在金锄头文库上搜索。
1、1 3 组合意义的解释与应用举例 1 非降路径问题 2 组合意义的解释 3 应用举例 从 0 0 点出发沿x轴或y轴的正方向每步走一个单 位 最终走到 m n 点 有多少条路径 y x m n 0 1 非降路径问题 因此若记所求方案数为 P m n m n 则 无论怎样走法 总有 在x方向上总共走m 步 在y 方向上总共走n步 若用一个x表示x方向上的一步 一个字母y表示y方 向上的一步 则 0 0 m n 的每一条路径可表示为 m 个相同的x与n个相同的y的一个排列 这相当于从m n个位置中选出m个位置放x 剩下的 位置自然放置y c d a b 或记为 设c a d b 则由 a b 到
2、c d 的 非降路径数为 对每一条接触x y 的非降 路径 做 0 1 点到第一个 接触点部分关于x y的对 称非降路径 这样得到一 条从 1 0 到 m n 的非降路 径 从 0 1 点到 m n 点的非降路径 有的接触x y 有 的不接触 在原模型的基础上若设mm 用一个m n维的向量来表示一个排队状态 其中每 个分量只能取x或y 这里取值y表示这个位置的顾客 持有50元的钞票 取值x表示只有100元的钞票 因此这等价于一个从 0 0 到 m n 点的非降路径 且 满足y x 即可以接触但不能穿过对角线 因此所求排队方法即为上页讨论的答案结果 2 组合意义的解释 它主要有以下三个重要意义
3、1 组合意义 n元集中k元子集的个数 2 显式表示 C n k n n 1 n k 1 k 3 二项展开式的系数 即有恒等式 二项式系数 C n k 是组合数学中无处不在的一个 角色 1 对称性 C n r C n n r 2 递推关系 C n r C n 1 r C n 1 r 1 从 1 n 去掉一个r子集 剩下一个 n r 子集 由此 建立C n r 与C n n r 的一个一一对应 共有C n 1 r C n 1 r 1 种方案 a1 1 有C n 1 r 1 种方案 a1 1 有C n 1 r 种方案 解释1 从 1 n 取a1 a2 ar 设1 a1 a2 ar n 对取法分类 0
4、 0 m n 0 0 m n 1 0 0 m 1 n 解释2 利用非降路径 C m n m C m n 1 m C m n 1 m 1 也可看做按含1不含1 含2不含2 含r不含r的不 断分类 解释1 可从上个结论推论 也可做一下组合证明 从 1 n r 1 取a1a2 anan 1 设a1 a2 an an 1 可按a1的取值分类 a1 1 2 3 r r 1 若a1 k 则a2 an 1取自 k 1 n r 1 有C n r 1 k n 种取法 这里k从1变到r 1 r n 1 r 0 0 n n 1 故有 解释2 右边表示从 0 0 到 n 1 r 的非降路径数 这些路径一定过且仅过一条
5、带箭头的边 而过这 些边的路径有 从下到上 按不含1 含1个1 含2个1 含r个1分类 其个数相应为 从 1 n 2 中取r个的可重组合模型 解释3 利用可重组合 其个数为 两种选法都无遗漏 无重复地给出可能的方案 应 该相等 左边是从n个元素中取k个组合 再从这k个取r个的 组合数 这相当于直接从n个元素中取r个 但是要计算重数 C n r k r 因为这相当于取定r个后 再从剩下n r 个元素中取k r个与之前的r个组合 5 C m n 2 C m 2 C n 2 mn 等式右边可以看作是m个男生n个女生 一男一女 的组合数 易知为mn 等式左端是从m n个人中取2人的组合减去纯从男 生中
6、取2人的组合和纯从女生中取2人的组合 余 下的即为一男一女的组合 在 中令x y 1即得 左边表示可以有0 子集 空集 1 子集 m 子集 解释1 右边即m个元素的所有选取方案 每一子 集都可取或不取 这样有 2m 种方案 解释2 从 0 0 走m步有2m 种走法 都落在直线 x y m上 而到 m 0 m 1 1 m 2 2 2 m 2 1 m 1 0 m 各点的走法各有C m 0 C m 1 C m 2 C m m 2 C m m 1 C m m 种 7 C m 0 C m 1 1 mC m m 0 在 中令x y 1即得 在任一含1组合及与之对应的不含1组合中 必有一 奇数个元的组合与一
7、偶数个元的组合 将含奇数个 元的组合做成集合 将含偶数个元的组合做成另一 集合 这两个集合的元素个数相等 在所有组合中 含1的组合 不含1的组合 P m r r m n r r m r k r k k 0 1 2 r Q m 0 解释1 从m个互异红球和n个互异蓝球中取r个球 按r个球中红球的个数分类 解释2 0 0 到 m n r r 点的路径 C m r k C n k 0 0 m r k r k m n r r 在8 中令r m n 再将换成即得 例1 从号码1 2 N中每次取出一个并登记 然后放 回 连取n次 得到一个由n个数字组成的数列 问 按这种方式能得到 1 多少个严格递增数列
8、n N 2 多少个不减数列 2 可重组合 C N n 1 n 3 应用举例 1 无重组合 C N n 1 每 人至少缺 把钥匙 且每 人所缺钥匙 不同 故至少共有C 7 3 35把不同的钥匙 2 任一人对于其他 人中的每 人 都至少有 把 钥匙与之相配才能开锁 故每人至少持C 6 3 20 把不同的钥匙 例2 某保密装置须同时使用若干把不同的钥匙才能 打开 现有 个人 每人持若干把钥匙 须 人到 场 所备钥匙才能开锁 问 1 至少有多少把不同的钥匙 2 每人至少持几把钥匙 2 若能级为kE0的质点可有2 k2 1 种状态 而且 服从Fermi Dirac分布 即不允许同能级的两个质 点有相同状
9、态 问系统有几种不同状态 或图像 例3 有4个相同质点 总能量为4E0 E0是常数 每 个质点所具能量为kE0 k 0 1 2 3 4 1 若能级为kE0的质点可有k2 1种状态 而且服从 Bose Einstein分布 即同能级的质点可以处于相同的 状态 问系统有几种不同的状态 或图像 能量分布 0 0 0 4 0 0 1 3 0 0 2 2 1 1 1 1 17 1 1 2 10 1 1 C 5 2 2 C 2 3 34 C 2 2 4 20 C 2 2 C 10 2 能量分布 0 1 1 2 1 1 1 1 1 1 C 2 2 5 C 2 4 72 2 2 C 4 2 10 C 4 4
10、246 能级k 0 1 2 3 4 1 k2 1 1 2 5 10 17 2 2 k2 1 2 4 10 20 34 状态数 例4 设n位长能纠r个错的码字的个数为M 则 n位长的0 1字符串共有2n 个 但不能每个串都设为 码字 否则失去纠错能力 设a a1a2 an b b1b2 bn是n位数串 则a b的 Hamming距离定义为 即对应位不同的位的个数 Hamming距离满足三角不等式 a r 右图表示以a为球心 r为半径的 球体中的串都作为a处理 由汉明不等式 只要两个码字a b满足d a b 2r 1 则不至于产生一个码字c 使得它与ab的汉明距离 都小于r 而无法判定是a还是b的
11、错 纠错处理 能纠正传输过程中产生的r个错是指 若规定a是码字 收到a 有d a a r 则将a 当作a 处理 发生最多r个错误 每一码字r邻域内的n位二进制数串的数目为 于是 因此各码字的r 邻域必须互不相交 综合上两式 有 另一方面任一串与最近的码字的距离不大于2r 否 则这个串本身可作为一新的码字 这表明在以所有码字为球心以2r为半径的球中 应 当使任一串落入某球内 故 例5 凸n边形没有3条对角线交于一点 计算各边及 各对角线所组成的互不重叠的多边形区域的个数 首先 它显然是 再从两个角度来计算所有区域的内角的总和 其次可以按各顶点对内角和的贡献来计算内角总和 为 因此所有多边形区域的总和为
