信息学竞赛中问题求解常见题分析 排列组合问题 一、知识点: 1. 分类计数原理:做一件事情,完成它可以有n 类办法,在第一类办法中有m1 种不同的方法,在第二类办法中有m2 种不同的方法,……,在第n 类办法中有mn。种不同的方法,那么完成这件事共有N=m1+m2+…+mn。种不同的方法。 2. 分步计数原理:做一件事情,完成它需要分成n 个步骤,做第一步有m1 种不同的方法,做第二步有m2 种不同的方法,……,做第n 步有mn 种不同的方法,那么完成这件事有N=m1*m2*…mn。种不同的方法。 3. 排列的概念:从 n 个不同元素中,任取 m(m≤n)个元素(这里的被取元素各不相同),按照一定的顺序排成一列,叫做从 n 个不同元素中取出 m 个元素的一个排列。 4. 排列数的定义:从 n 个不同元素中,任取 m(m≤n)个元素的所有排列的个数叫做从 n 个元素中取出 m 个元素的排列数,用符号mnA 表示。 5. 排列数公式:mnA =n(n-1)(n-2)…(n-m+1)(m,n∈N,m≤n) 6. 阶乘:n!表示正整数l 到 n 的连乘积,叫做n 的阶乘规定 0!=l。 7. 排列数的另一个计算公式:)!(!mnnAmn 8. 组合的概念 :一般地,从 n 个不同元素中取出 m(m≤n)个元素并成一组,叫做从 n 个不同元素中取出 m 个元素的一个组合. 9. 组合数的概念:从 n 个不同元素中取出 m(m≤n)个元素的所有组合的个数,叫做从 n 个不同元素中取出 m 个元素的组合数.用符号mnC表示. 10. 组合数公式:!)1)...(2)(1(mmnnnnAACmmmnmn,或)!(!!mnmnC mn (n,m∈N,且 m≤n) 11. 组合数的性质 1:mnnmnCC,规定:0nC :=1; 2:11mnmnmnCCC。 1 2 . 圆排列 (1) 由 A{a1,a2,a3..an}的n 个元素中,每次取出 r 个元素排在一个圆环上,叫做一个圆排列(或叫环状排列)。 (2) 圆排列有三个特点:(i)无头无尾;(ii)按照同一方向转换后仍是同一排列;(iii)两个圆排列只有在元素不同或者元素虽然相同,但元素之间的顺序不同时,才是不同的圆排列. (3) 定理:在A={a1,a2,a3..an}的n 个元素中,每次取出 r 个不同的元素进行圆排列,圆排列数为 rP rn 。 13. 可重排列 允许元素重复出现的排列,叫做有重复的排列。 在m 个不同的元素中,每次取出 n 个元素,元素可以重复出现,按照一定的顺序那么第一、第二……第n 位是的选取元素的方法都是 m 种,所以从 m 个不同的...