组合数学 2

· · 个人记录

可重集合排列

$$ C_{\sum a_{1\sim n}}^{a_{1}}\cdot C _{\sum a_{2\sim n}}^{a_{2}}\cdot \ldots \cdot C_{a_n}^{a_{n}}=\dfrac{\left( \sum a_{i}\right) !}{a_{1!}\cdot a_{2!}\cdot \ldots\cdot a_{n!}} $$ #### 圆排列 显然地，$(n-1)!

错位排列

将 1\sim n 生成全排列，其中第 1 位不能为 1、第 2 位不能为 2\ldots 第 n 位不能为 n 的方案数被称为错位排列，记为 D_n

  1. 从容斥原理考虑

    D_{n}=\sum ^{n}_{i=0}C_{n}^{i}\left( n-i\right)!\cdot \left( -1\right) ^{i}

    即

    D_{n}=\sum ^{n}_{i=0}\left( -1\right) ^{i}\cdot A_{n}^{i}

  2. 从递推角度考虑

    D_{n}=\left( n-1\right)\cdot \left( D_{n-1}+D_{n-2}\right)

\mathtt{Stirling} 数

第一类斯特林数
dp_{i,j}=dp_{i-1,j-1} +\left( i-1\right) \cdot dp_{i-1,j}
第二类斯特林数
dp_{i,j}=dp_{i-1,j-1}+j\cdot dp_{i-1,j}
可能能用到的
x^{n}=\sum_{i=0}^{n}\begin{Bmatrix}n \\i \end{Bmatrix} x^{\underline{i}}

\mathtt{Catalan} 数

Cat_{n}=C_{2n}^{n}-C_{2n}^{n-1}=\dfrac{C^{n}_{2n}}{n+1}
性质
Cat_n=\sum ^{n}_{l=1}Cat_{l-1}\cdot Cat_{n-l}
证明、应用

懒得写了。挖个坑先。