信息学竞赛中问题求解常见题分析 排列组合问题 一、知识点： 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 个不同的...
