组合数学题目及答案.doc

组合数学例1:将8个“车”放在 8×8 的国际象棋棋盘上, 如果它们两两均不能互吃, 那么称 8个“车”处于一个安全状态。问共有多少种不同的安全状态? 解:8个“车”处于安全状态当且仅当它们处于不同的 8 行和 8 列上。用一个排列 a1,a2, …,a8 , 对应于一个安全状态,使 ai 表示第 i 行的 ai 列上放置一个“车”。这种对应显然是一对一的。因此,安全状态的总数等于这 8 个数的全排列总数 8!= 40320 。例4:n 位客人在晚会上每人与他人握手 d 次, d 是奇数。证明 n 偶数。证:由于每一次握手均使握手的两人各增加一次与他人握手的次数,因此 n 位客人与他人握手次数的总和 nd 是偶数—握手次数的 2倍。根据奇偶性质, 已知 d 是奇数, 那么 n 必定是偶数。例4 从1到2n 的正整数中任取 n +1个, 则这 n +1 个数中, 至少有一对数, 其中一个是另一个的倍数。证设n +1 个数是 a 1,a 2, ···, an +1 。每个数去掉一切 2 的因子,直至剩下一个奇数为止。组成序列 r 1,r 2,, ···, rn +1 。这n +1 个数仍在[1,2n]中, 且都是奇数。而[1, 2n] 中只有 n 个奇数, 故必有 ri= rj=r,则 ai=2αir, aj=2αjr。若 ai> aj ,则 ai是 aj 的倍数。例5设a 1,a 2, ···, am 是正整数,则至少存在一对 k和l,0≤ k<l ≤m ,使得和 ak+ 1+ ak +2+ ···+ al是m 的倍数。证设 Sh=, Sh≡ rh mod m,0≤ rh≤m -1, h=1,2, ···,m. 若存在 l, Sl≡0 mod m , 1≤ rh≤m -1 .但 h=1,2, ···,m. 由鸽巢原理,故存在 rk= rl,即 Sk≡ Sl mod m ,不妨设 l>k .则 Sl- Sk= ak+ 1+ ak+ 2+…+ al≡0 mod m 例6设a 1,a 2,a3 是任意三个整数, b1 b2b3为 a1, a2, a3 的任一排列,则 a1- b1, a2- b2 ,a3 - b3 中至少有一个是偶数. 证由鸽巢原理: a1, a2, a3 ,不妨设为 x; 同样 b1, b2, b3 中被2除的余数也至少有2个 x .这样 a1- b1, a2- b2, a3- b3 被2除的余数至少有一个为0. ?? hi ia 1 定义:设 r 为正整数,从 n 个不同的元素的集合 S 中,取 r 个元素按次序排成一行,称为 S 的一个 r- 排列。例 S={a,b,c} ,则 S有 3个 1- 排列: a,b,c6个 2- 排列: ab, ac, ba, bc, ca, cb 6个 3- 排列: abc , acb , bac , bca , cab , cba n 元素集的 r- 排列数记为 P( n,r ) 。若 r>n ,则 P( n,r )=0 。 n 元素集 S的 n- 排列简称为 S 的排列或 n 个元素的排列(全排列) 定义 n!=n × (n-1) ×…×2×1 0!=1 故P( n,r )=n !/( n-r )!P(n ,0)=1 P(