组合数学
加法原理和乘法原理
分类相加 分步相乘
排列数
讲顺序
[A_{n}^{m}=frac{n!}{(n-m)!}\,\,\,\,\,\,\, (mleq n,m与n均为自然数)
]
组合数
不讲顺序
[dbinom{n}{m}=C_{n}^{m}=frac{A_n^m}{m!}=frac{n!}{m!(n-m)!}
]
显然的公式：
[sum_{k=0}^ndbinom{n}{k}=2^n
]
[dbinom{n}{k}=dbinom{n-1}{k}+dbinom{n-1}{k-1}
]
[dbinom{n}{m}=dbinom{n}{m-1}
]
[dbinom{n}{k}=frac{n}{k}dbinom{n-1}{k-1}
]
[dbinom{n}{m}=dbinom{n-1}{m}+dbinom{n-1}{m-1}
]
[sum_{i=0}^n(-1)^idbinom{m}{m-i}=dbinom{m+n}{m}\,\,\,(ngeq m)
]
[sum_{i=0}^mdbinom{n}{i}^2=dbinom{2n}{n}
]
[sum_{i=0}^nidbinom{n}{i}=n2^{n-1}
]
[sum_{i=0}^ni^2dbinom{n}{i}=n(n+1)2^{n-2}
]
[sum_{l=0}^ndbinom{l}{k}=dbinom{n+1}{k+1}
]
[dbinom{n}{r}dbinom{r}{k}=dbinom{n}{k}dbinom{n-k}{r-k}
]
[F_n表示斐波那契数列第n项:\,\,\,\,\,sum_{i=0}^ndbinom{n-i}{i}=F_{n+1}
]
二项式定理
[(a+b)^n=sum_{i=0}^ndbinom{n}{i}a^{n-i}b^{i}
]
范德蒙德卷积
[dbinom{n+m}{k}=sum_{i=0}^kdbinom{n}{i}dbinom{m}{k-i}
]
多重集合的排列
将(n)个物品划分为(k)个集合，且每个集合的大小分别为(c_1,c_2,…c_k)，且(sum c_i=n)。则其方案数为(frac{n!}{prod c_i!})
现在有若干种相同的物品，每种的个数为(c_i)，现在将这些物品排成一排，其方案数为(frac{(sum c_i )!}{prod c_i!})
容斥原理
盒子与球
常用方法
插板法
就是在 (n) 个物品之间插上 (m) 个板，将其分为 (m+1) 组。
捆绑法
在解决对于某几个元素要求相邻的问题时，先整体考虑，将相邻元素视作一个大元素进行排序，然后再考虑大元素内部各元素间顺序的解题策略就是捆绑法。
球相同，盒子不同，不能有空盒
实质是n 个小球分为 m 组（不能空）
插板法解决
[ans=C_{n-1}^{m-1}
]
球相同，盒子不同，可以有空盒
转化为上面的问题，先在每个盒子里装一个球，最后再拿出来
[ans=C_{n+m-1}^{m-1}
]
球不同，盒子不同，可以有空盒
[ans=m^n
]
球不同，盒子相同，不能有空盒
第二类斯特林数（简称S2）的定义为将(n)个物体划分成k个非空的没有区别的集合的方法数，大致就是把(n)个不同的小球放入(m)个相同的盒子中（且盒子不能为空）的方案数。
递推公式为（(S2[i][j])表示前 (i)个小球放到前 (j) 个盒子里的方案数）：
[S2[i][j]=S2[i−1][j]∗j+S2[i−1][j−1]
]
还有一个公式（容斥原理可以证明）：
[S2(n,m)=frac{1}{m!}*sum_{k=0}^m(-1)^kdbinom{m}{k}*(m-k)^n
]
球不同，盒子不同，不能有空盒
就是算S2再消除球的有序性就行了
[ans=m!*S2[n][m]
]
球不同，盒子相同，可以有空盒
由第二类斯特林数得
[ans=sum_{i=1}^{m}S2[n][i]
]
贝尔数（Bell数）：第n个Bell数表示集合{1,2,3,...,n}的划分方案数
[B_{n+1}=sum_{k=0}^ndbinom{n}{k}B_k
]
[B_n=sum_{k=1}^nS2(n,k)
]
球相同，盒子相同，可以有空盒
设(f[n][m])为(n)个球放到(m)个盒子里的方案数
如果只有一个盘子或者没有小球，方案数自然为(1)
如果小球比盒子要少，小球肯定是放不满盒子的，由于盒子相同，可以得到转移(f[i][j]=f[i][i])
如果小球比盒子要多，就分为将盘子放满和没放满两种情况，即(f[i][j]=f[i-j][j]+f[i][j-1])
球相同，盒子相同，不能有空盒
和上面一种有联系，先在每个盒子里放一个球，最后再拿出来
[ans=f[n-m][m]
]