1、目录一、组合计数基础二、全排列问题三、递推问题四 、容斥原理加法原理和乘法原理 计数问题 : 满足条件的元素有多少个 ? 加法原理 : 把事情分成 N类，每类有 Ci种做法，则该事情共有 C1+C2+CN 种做法 乘法原理 : 每个元素由 n个独立的部分组成 , 每部分有 ci种方案 加法原理的推广 : 容斥原理基本问题 把 1n的数选 k个排成一排 , 每个数最多选一次 , 有多少种排列方法 ? P(n, k) = n!/(n-k)! 从 1n选出 k个数 , 每个数最多只能选一次 , 有多少种方法 ? C(n, k) = P(n, k) / k! K!的近似公式 (Stirling公式 )
2、: 100!=9.33*10157 6280.5*(100/2.718)100=9.39*10157 C(n, k)基本性质 C(n, 0) = C(n, n) = 1 C(n, k) = C(n, n-k) C(n, k) + C(n, k+1) = C(n+1, k+1). 预处理杨辉三角 二项式系数 第 i+1行是 C(i,1), C(i,2), 利用杨辉三角求出组合了，如何求出排列呢？全排列定义：对于字符集 X，将 X的所有元素的可能排列全部枚举出来，对含有 N个元素的集合 X，共有 N！个可能全排列的生成算法：字典序法、递增进位制法、递减进位制法、临位对换法这里讲解字典序法字典序法生
3、成全排列 求 X=1,2,3,4,5,6,7上排列 P=2639541的下一个排列 Q,首先注意到 Q是由 P的后部变动引起的。 从右到左找出比右边数字小的第一个数，即 3所在的位置，再从右到左找比 3大的第一个数，为 4，将 3与 4对换，得到 2649531， 然后从 4后面的 9531翻转得到 1357，则Q=2641357. 对一般情况，设 P是 1,2,n 的一个全排列 P=a1a2an 。求解 P的下一个排列步骤如下： （ 1）在 P中从右到左寻找左边比右边小的第一个位置 j，即 j=maxi|aiaj （ 3）对换 aj， ak，并将 aj+1之后的翻转。我排第几个 现在有 “a
4、bcdefghijkl”12个字符，将其所有的排列中按字典序排列，给出任意一种排列，说出这个排列在所有的排列中是第几小的？ 输入第一行有一个整数 n（ 0n=10000） ;随后有 n行，每行是一个排列；输出输出一个整数 m，占一行， m表示排列是第几位 样例输入 样例输出 3 abcdefghijkl 1 hgebkflacdji 302715242 gfkedhjblcia 260726926基本问题 由 n个小写字母的串有多少个 ? 每个字母独立 , 都有 26种选择共 26n 重数为 ni的全排列： n!/(n1!n2!n k!)有 ni个相同的元素把这 ni个元素各涂一种颜色以区分 . PIni!所有元素做全排列 . 由于所有元素已经变成全部不同的了 , 答案为 n!由乘法原理 , PIni! * ans = n!例题 : 字母的编号 给两个 a, 一个 b, 一个 c, 所有字符串的编号为aabc1aacb2abac3cbaa12 输入字符串 , 输出它的编号 如输入 acab, 则输出 5
