排列组合

排列组合

求组合数

#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个，求有多少种方案:

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

排列组合实际问题总结

不定方程的解

求不定方程x1+x2+…+xk=nx_1+x_2+…+x_k=n的解的数量，其中xix_i为整数，且xi≥1,(1≤i≤k)x_i \geq 1,(1 \leq i \leq k)

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

若xi≥ai,x1+x2+…+xk≤nx_i\geq a_i,x_1+x_2+…+x_k\leq n

换元：y1=x1−(a1−1)≥1,y2=x2−(a2−1)≥1，…，yk=xk−(ak−1)≥1y_1=x_1-(a_1-1)\geq1,y_2=x_2-(a_2-1)\geq1，…，y_k=x_k-(a_k-1)\geq1

y1+y2+…+yk=n−∑i=1kai+ky_1+y_2+…+y_k=n-\sum_{i=1}^{k}a_i+k

此时答案为(n−∑i=1kai+kk−1)\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步向上

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

容斥

容斥 ∣⋃i=1nSi∣=∑m=1n(−1)m−1∑ai<ai+1∣⋂i=1mSai∣\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个元素,a1,a2,…,ana_1,a_2,…,a_n和b1,b2，…，bnb_1,b_2，…，b_n，求有多少个它们的全排列，满足任意的1≤i≤n1\leq i \leq n，aia_i和bib_i都不相邻。

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

求不定方程x1+x2+…+xk=nx_1+x_2+…+x_k=n的解的数量，其中xix_i为整数，且li≤xi≤ri,(1≤i≤k)l_i \leq x_i \leq r_i,(1 \leq i \leq k)

S=x1+x2+…+xk=n的所有满足xi≥li的解S={x_1+x_2+…+x_k=n的所有满足x_i\geq l_i的解}

Ai={xi≥ri+1}A_i=\{x_i \geq r_i+1\}

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

错排问题

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

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

Ai={pi=i}A_i=\{p_i=i \}

有∣S−⋃i=1nAi∣=∑i=0n(−1)i(ni)(n−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(a1…ax(1−ax+1)…(1−ax+n))N(a_1\dots a_x(1-a_{x+1})\dots(1-a_{x+n}))求出有些性质有，有些性质没有的方案数

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

a1:是2的倍数，a2:是3的倍数，a3:是5的倍数a_1:是2的倍数 ，a_2:是3的倍数 ，a_3:是5的倍数

N((1−a1)(1−a2)a3)=N(a3−a1a3−a2a3+a1a2a3)=⌊n5⌋−⌊n10⌋−⌊n15⌋+⌊n30⌋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≤i≤n满足pi≠i 1\leq i \leq n满足p_i \not= i，给定n，k，求满足要求的排列有多少个。

Ai={pi=i}A_i=\{p_i=i \}

N(a1a2…ak(1−ak+1)…(1−an))=(nk)∑i=0n−k(−1)i(n−ki)(n−(k+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−ai)…(1−ak))=∑i=0k(−1)i(ki)(k−i)n=s2(n,k)∗k!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!

故s2(n,k)=1k!∑i=0k(−1)i(ki)(k−i)ns_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;

Last updated