组合数几种典型解法
一、
在n个小球中选t个(无先后顺序) C(n)t
二、
1、 【隔板法】将n个小球放入t个盒子里(保证每个盒子至少1个小球) C(n-1)t-1
2、 【隔板法】【映射】将n个小球放入t个盒子里(盒子可以为空) C(n+t-1)t-1
三、
1、多重集的组合数(无限制)：
条件1、有n种不同颜色的小球;条件2、n种颜色小球无数个(或者都大于要选择的小球个数t);条件3、选择t个小球
【隔板法】【映射】C（n+t-1)n-1
2、多重集的组合数（有限制）：
条件1、有n种不同颜色的小球;条件2、每种颜色小球可选个数不同a1、a2…an; 条件3、选择t个小球
解:
设p1 = 选<=a1个1号色小球的方案......pn = 选<=an个n号色小球的方案
方案数为：p1 n p2 n p3…n pn (n为交集符号)
【容斥原理】总-（!p1 U !p2 U … U !pn）
【映射】【隔板法】!p1为选择>a1个1号色小球的方案 C(n+t-1-(a1+1))t-1 | !p1 U !p2 : C(n+t-1-(a1+1)-(a2+1))t-1 …
【容斥原理】方案数为:C(n+t-1)t-1[总]奇减偶加
四、
1、组合数中不等关系问题
1）严格单调递增（递减）关系
说法1：在L到R 之间选择n个数且的严格单调的序列数量
说法2：统计长度在 1 到 N 之间，元素大小都在 L 到 R 之间的单调（增）降序列的数量
条件、L<=a1<a2<a3<a4....<an<=R（L，R为常数L<=R）
解：相当于从L到R中选择n个数
C(R-L+1)n
2) 单调不增（不减）关系
说法1：在L到R 之间选择n个数且的单调的序列数量
说法2：统计长度在 1 到 N 之间，元素大小都在 L 到 R 之间的单调不降序列的数量
条件、L<=a1<=a2<=a3<=a4....<=an<=R（L，R为常数L<=R）
解：【映射】a1 = a1; a2 = a2+1.....an = an+n-1; R = R+n-1
映射为：L<a1<a2<a3…<an<=R+n-1
C(R+n-1-L+1)n 即 C(R-L+n)n
2、组合数中不等式问题
1)将不超过n个小球放到t个盒子里（盒子至少为有1个小球）
条件、0<=a1+a2+a3+at<=n （正整数ai不能为0）
解：【映射】因为不超过n个小球，所以多放一个盒子,相当于n个小球放到t+1个盒子中
【隔板法】
需要注意的是，这里的条件是不等式，对于等式而言，我们用 k−1 个隔板将所有小球分为 k 部分即可；对于不等式，我们考虑用 k 个隔板，将所有小球分为 k+1 部分，其中最后一部分被舍弃（即不选用），当然最后一部分的个数在本题可以为零。如下示意图：
⚪···⚪|⚪···⚪|···|⚪···⚪|⚪···⚪
⚪···⚪|⚪···⚪|···|⚪···⚪|这里没有球
n 个球，有 n−1 个缝隙，还需要加上最右边的一个“缝隙”，共 n 个缝隙，插入 k 个隔板
C(n)k
2)将不超过n个小球放到t个盒子里（盒子可以为空）
条件、0<=a1+a2+a3+at<=n （正整数ai可以为0）
【映射】因为不超过n个小球，所以多放一个盒子（该盒子也可以为空）,相当于n个小球放到t+1个盒子中
【再映射】盒子可以为空，每个盒子先加1个小球n+t+1
【隔板法】C(n+t+1-1)t+1-1 即 C(n+t)t
