组合数学中相邻与不邻问题的几种一般性的解法.pdf

收稿日期 2009 05 30 作者简介 闫淑芳 1964 女 河北威县人 毕业于河北师范大学 副教授 主要从事数学教学与研究 电话 0319 7300840 组合数学中相邻与不邻问题的几种一般性的解法 闫淑芳 邢台学院数学系 河北邢台 054001 摘 要 相邻与不邻是经常遇到的问题 常规问题容易解决 一般性的问题求解困难 这里给出一些复杂场合下的相邻 与不邻问题的几种解法 关键词 相邻 不邻 容斥原理 一一映射 反演 中图分类号 O157 文献标识码 A 文章编号 1672 4658 2009 04 0101 03 大家知道 在排列组合有关的计算问题中 相邻与不邻 是一个很重要的方面 比较基础的方法是 捆绑法 与 插 空法 但有些问题仅仅有这两种方法是不够的 下面就这 一问题做更多的分析 1 相邻问题 捆绑法 例 1 6个同学站成一排甲 乙相邻有多少种站法 解 先把甲乙两个同学看成一个人捆绑在一起再和其 它 4个同学一起排有 5 种方法 甲乙之间还可以交换顺 序 所以用 捆绑法 有 A 5 5 2 240种方法 2 不邻问题 插空法 例 2 6个同学站成一排甲 乙不相邻有多少种站法 解 因为甲 乙不相邻 中间有隔挡 可用 插空法 第一步先让甲 乙以外的 4个人站排 有 A 4 4 24种方法 第二步将甲 乙二人排在四人形成的空挡 含两端 共有 A 4 4 A 2 5 480种方法 上面的情况比较单一 容易解决 问题稍微综合就难以 解决 有时即使可以解决也是很麻烦且容易出错 看下面的 问题 例 3 求有 n n 4 个相异元 a1 a2 an作成的 a1与 a2不相邻 a3与 a4也不相邻的全排列的个数 这个问题表面上看是一个简单的不相邻的问题 如果 用 插空法 会得到如下解法 有 A n 4 n 4 A 2 n 3 A 2 n 1种 但 这 里 少 计 算 了 如 a1a3a2a4 的情况 需要更一般的方法 3 排列中的相邻与不邻综合问题 容斥原理法 上例正解如下 设所求为 N 以 S表示有 a1 a2 an作成的全排列之 集 则S n 以 A B分表示 a1与 a2相邻 a3与 a4相邻 的全排列所成之集 则A B 2 n 1 A B 4 n 2 由容斥原理得 N S A 得取出 6个 不同的数在原排列中至少间隔一个元素的取法数为 44 6 所以所求为 49 6 44 6 5 错位排列问题 反演公式法 类型 4 设 s1 s2 sr是 r个给定的非负整数 又设对任 意的 r个非负整数 n1 n2 nr ni si i 1 2 r f n1 n2 nr 及 g n1 n2 nr 都是实数 且 f n1 n2 nr si ki ni i 1 2 r r i 1 ni ki g k1 k2 kr 则对任意 r个非负整数有 n1 n2 nr ni si i 1 2 r g n1 n2 nr si ki ni i 1 2 r r i 1 1 ni ki ni ki f k1 k2 kr 证明 见参考文献 1 例 6 以 f n1 n2 nr 表示由 n1个 a1 n2 nr个 ar作 成的没有两个相邻元素相同的全排列的个数 则 f n1 n2 nr 1 ti ni i 1 2 r r i 1 1 ni ti ni 1 ti 1 t1 t2 tr t1 t2 tr 证明 以 A 表示由 n1个 a1 n2个 a2 nr个 ar作成的全 排列之集 则A n1 n2 nr n1 n2 tnr 设 A 若在排列 中 ni 1 i r 个 ai被其他元素分隔成 ti 1 ti ni i 1 2 r 段 则称 是A的一个型为 t1 t2 tr 的元素 因为把长 度为 ni 1 i r 的线段切割成长度均为正整数的有序的 ti 段的方法数 等于不定方程 x1 x2 xti ni的正整数解的 个数 为 ni 1 ti 1 所以 A 中型为 t1 t2 tr 的排列的个数为 r i 1 ni 1 ti 1 f t1 t2 tr 由加法原理 有 n1 n2 nr n1 n2 tnr 1 ti ni i 1 2 r r i 1 ni 1 ti 1 f t1 t2 tr 所以 n1n2 nr n1 n2 nr n1 n2 tn r 1 ti ni i 1 2 r r i 1 ni ti t1t2 trf t1 t2 tr 由上面的反演公式得 n1 n2 nr f n1 n2 nr 1 ti ni i 1 2 r r i 1 1 ni ti ni ti t1t2 tr t1 t2 tr t1 t2 tr 所以 f n1 n2 nr 1 ti ni i 1 2 r r i 1 1 ni ti ni 1 ti 1 t1 t2 tr t1 t2 tr 例 7 有 6张卡片 上面分别写有 1 1 2 2 3 3 现随 机放到桌面上 排成一排组成一个 6位数 则相同数字不相 邻的 6位数的概率是多少 解 由上例 f 2 2 2 下转第 105页 102 闫淑芳 组合数学中相邻与不邻问题的几种一般性的解法 2 2 中国古代数学的算法化与实用性倾向 在筹算开平方和开立方的基础上 我国从 11世纪开 始 逐渐摸索到数值解高次方程的一般规律 北宋数学家 贾宪 在前人的基础上 发明了开任意高次幂的 增乘开方 法 它是我国古代数学史上一项杰出创造 是一个非常有 效和高度机械化的算法 公元 1819年英国数学家霍纳才得 出同样的算法 贾宪的 增乘开方法 不仅适用于开任意 高次方 而且能得出高次方程的数值解法 只是贾宪没有意 识到这点 经过 200多年的不断改善 到 13世纪上半叶 由秦九韶最后完成完整的体系 秦九韶求实根法 即解 高次方程的 正负开方术 其方程的各系数可正可负 可 以是整数或小数 开方得到无理根时 秦九韶发挥了刘徵首 创的计算 微数 的思想 用十进小数作无理根的近似值 这一时期 数学人才辈出 有北宋的沈括 贾宪和刘益 南宋 的秦九韶 杨辉 元代的李冶 朱世杰 郭守敬等 使宋元时 期的数学达到了中国古代数学的顶峰 尤其在代数领域达 到了西方望尘莫及的水平 在代数 几何 三角 解析几何 和微积分等学科的发现和创立过程中 中国传统数学起到 了重要作用 中国古代数学的构造性 机械化的算法体系完全有别 于以古希腊为代表的西方数学的逻辑风格和演绎体系 为 什么会出现这两种不同风格的数学体系 数学思想 数学 文化史的研究表明 在人类文化发展过程中 每一种文化系 统都有其特定的数学发展和构造模式 数学既是在某个文 化系统中发生发展的必然产物 又是文化系统中一种文化 的特定表现形式 不同的文化传统会形成不同形式的数学 与科学技术的结构形式 可以说 中西文化传统的差异造 成中西古代数学思想以及数学结构形式的差异 换句话 说 文化传统往往规定了数学的思维方式 进而导致数学发 展的必然取向 从中西古代数学文化史的比较意义上分 析 形成中西古代数学的两种倾向 逻辑演绎倾向和机械化 算法倾向 其作用与构造差异主要是由文化系统赋予的文 化层次及其价值取向的差异造成的 这两种风格不同的数 学思想方法 在世界数学发展史上 起着互相补充互相促进 的作用 对数学科学的发展 都作出了伟大的贡献 参考文献 1 美 M 克莱茵 古今数学思想 第一册 M 上海 上海科 学技术出版社 1979 2 李迪 试论中国古代的开方式 J 自然辩证法通讯 2003 25 2 7 71 3 李文林 数学史概论 第二版 M 北京 高等教育出版 社 2000 上接第 102页 1 ti 2 i 1 2 3 3