排列组合

排列组合

求组合数

#1

int inv[N], mul[N];
int ksm(int a, int b, int mod) {
    int ans = 1;
    while (b) {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
void init() {
    inv[0] = mul[0] = 1;
    for (int i = 1; i < N; i++)
        mul[i] = mul[i - 1] * i % mod;
    inv[1000001] = ksm(mul[1000001], mod - 2, mod);
    for (int i = 1000000; i > 0; i--)
        inv[i] = inv[i + 1] * (i + 1) % mod;
}
int C(int n, int m) {
    if(n < m) return 0;
    return mul[n] * inv[m] % mod * inv[n - m] % mod;
}

#2

void init() {
    c[0][0] = 1;
    for (int i = 1; i <= 400; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++) {
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
    }
}

多重组合数

有l个物品，给每个人分配c_i个，求有多少种方案:

$\left( \begin{matrix} l\\ c_1c_2…c_k \\ \end{matrix} \right)$

排列组合实际问题总结

不定方程的解

求不定方程$x_1+x_2+…+x_k=n$的解的数量，其中$x_i$为整数，且$x_i \geq 1,(1 \leq i \leq k)$

隔板法：（k-1）块板把n个小球分成n份

若$x_i\geq a_i,x_1+x_2+…+x_k\leq n$

换元：$y_1=x_1-(a_1-1)\geq1,y_2=x_2-(a_2-1)\geq1，…，y_k=x_k-(a_k-1)\geq1$

$y_1+y_2+…+y_k=n-\sum_{i=1}^{k}a_i+k$

此时答案为$\left(\begin{matrix}n-\sum_{i=1}^{k}a_i+k\\k-1 \\\end{matrix}\right)$

网络路径计数

在n*m的网格图上，从(0,0)走到(n,m)，每次只能向右或者向上走，求方案数。

共走n+m步,有m步向上

$\left(\begin{matrix}n+m\\m \\\end{matrix}\right)$

容斥

容斥 $\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1}}\left|\bigcap_{i=1}^mS_{a_i}\right|$

• 求正整数1-n中，既不是2的倍数也不是3的倍数的数的数量

• 求n个元素1-n组成的全排列，满足1与2不相邻，3与4也不相邻的方案数

• 把n件不一样的物品放到三个不同盒子里，满足每个盒子至少要有一个物品的方案数。

• 有2n个元素,$a_1,a_2,…,a_n$和$b_1,b_2，…，b_n$，求有多少个它们的全排列，满足任意的$1\leq i \leq n$，$a_i$和$b_i$都不相邻。

S={全排列}，$A_i={a_i 和b_i相邻}$，有$\sum_{i=0}^n(-1)^i\left(\begin{matrix}n\\i \\\end{matrix}\right)2^i(2n-i)!$种

求不定方程$x_1+x_2+…+x_k=n$的解的数量，其中$x_i$为整数，且$l_i \leq x_i \leq r_i,(1 \leq i \leq k)$

$S={x_1+x_2+…+x_k=n的所有满足x_i\geq l_i的解}$

$A_i=\{x_i \geq r_i+1\}$

那么就转化成了之前在排列组合中提到的问题

错排问题

p是1,2，…，n的一个排列，满足$\forall 1\leq i \leq n，p_i \not= i$，给定n，求满足要求的排列有多少个。

$S={1,2，…,n的全排列}$

$A_i=\{p_i=i \}$

有$\left| S-\bigcup_{i=1}^n A_i \right|=\sum_{i=0}^n(-1)^i\left(\begin{matrix}n\\i \\\end{matrix}\right)(n-i)!$种

容斥原理的符号形式

这样就可以用$N(a_1\dots a_x(1-a_{x+1})\dots(1-a_{x+n}))$求出有些性质有，有些性质没有的方案数

例：求正整数1-n中，既不是2的倍数也不是3的倍数，但是是5的倍数的数的数量。

$a_1:是2的倍数 ，a_2:是3的倍数 ，a_3:是5的倍数$

$N((1-a_1)(1-a_2)a_3)=N(a_3-a_1a_3-a_2a_3+a_1a_2a_3)=\lfloor \frac{n}{5} \rfloor-\lfloor \frac{n}{10} \rfloor-\lfloor \frac{n}{15} \rfloor+\lfloor \frac{n}{30} \rfloor$

p是1,2，…，n的一个排列，满足刚好存在k个$1\leq i \leq n满足p_i \not= i$，给定n，k，求满足要求的排列有多少个。

$A_i=\{p_i=i \}$

$N(a_1a_2\dots a_k(1-a_{k+1})\dots(1-a_n))=\left(\begin{matrix}n\\k\\\end{matrix}\right)\sum_{i=0}^{n-k}(-1)^i\left(\begin{matrix}n-k\\i \\\end{matrix}\right)(n-(k+i))!$

第二类斯特林数

有n个互不相同的球，放到k个互不区分的盒子里，每个盒子里至少要有一个球，求方案数。

#1：dp，f[n][k]表示前n个球放k个盒子，k*f[n-1][k]+f[n-1][k-1]

#2：将盒子从1到k编号，a_i表示第i个盒子没有球。

$N((1-a_i)\dots(1-a_k))=\sum_{i=0}^k(-1)^i\left(\begin{matrix}k\\i\\\end{matrix}\right)(k-i)^n=s_2(n,k)*k!$

故$s_2(n,k)=\frac{1}{k!}\sum_{i=0}^k(-1)^i\left(\begin{matrix}k\\i\\\end{matrix}\right)(k-i)^n$

第二类斯特林数的一些公式

对于图中最后一个公式，可以看成是n个不同的盒子中放m个球，即为n^m，也可以看成每次从n个盒子中取k个盒子，即为

完全错排

//写法1：
int D(int n)
{
    if (n == 0 || n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
        return (n-1) * (D(n-2) + D(n-1));
}

//写法2：
int ans = 1;
for (int i = 1; i <= n; i++) {
        ans = (ans * i % mod + ((i & 1) ? -1 : 1));
}
ans %= mod;