第一讲--组合计数.pdf

组合计数 第一部分 常规方法 加法原理与乘法原理，无重复的排列和组合，可重复的排列与组合，圆排列 例 1 证明：如果(a,b) 1 ，那么等差数列a,2a,3a,...,ba 中能被 整除的项的个数等于 b (a,b). 解答：设(a,b) d ，则a dr ,b ds ,(r s, ) 1 。我们用 去除数列中每一个数，得到数列 b r 2r sr (s 1)r 2sr (2s 1)r dsr , ,..., , ,... , ,..., s s s s s s s sr 2sr dsr 由于(r, s) 1 ，所以上述数列中只有 个整数： , ,..., 。这样，原数列中只有 个 d d s s r 数能被 整除 b 例2.在1,2,3,4,5 的排列a , a ,..., a 中满足a a , a a , a a , a a 的排列 1 2 5 1 2 2 3 3 4 4 5 a , a ,..., a 有多少？ 1 2 5 解答：满足要求的排列，5 只能在第二或者第四个位置上，即5 a2 或5 a4 5 a a a , a a a a , a , a 情况 1. 时， 1 2 2 3 ，因此 可以是1,2,3,4，中的任何一个， 是另 2 1 3 4 5 a a , a 外三个数，其中 是最大的， 有两种选法，所以共有 4 3 5 1 1 C C 8 种。 4 2 情况2. 5 a4 ，同样有8 种。 所以一共有16 种。 n a , a ,..., a n 例3. 任给 个互不相同的正数 1 2 n ，用它们可以组成一切可能的和（分别有1 至 n(n 1) 个加数）。证明：在这些和中最少存在 个互不相同的数。 2 解答：不妨设a a ... a 。考察下列各数：