排列组合与盒子放球问题

@[TOC]

排列组合

定义

排列（ $Arrangement/Permutation$ ）定义：**从 $n$ 个不同元素中取出 $m(m≤n)$ 个元素，按照一定的顺序排成一列，叫做从 $n$ 个元素中取出 $m$ 个元素的一个排列**。
从 $n$ 个不同元素中取出 $m$ 个不同元素，所有不同排列的个数称为排列种数或称排列数，记为 $A_n^{m}$ （排列数旧版记作 $P_n^m$ ，都一样）。 $A_n^m=n\times(n-1)\times(n-2)\times(n-3)\times...\times(n-m+1)=\tfrac{n!}{(n-m)!}$

组合（ $Combination$ ）定义：**从 $n$ 个不同的元素中，任取 $m(m≤n)$ 个元素为一组，叫作从 $n$ 个不同元素中取出 $m$ 个元素的一个组合。**
从 $n$ 个元素中不重复地选取 $m$ 个元素的一个组合。所有这样的组合的总数称为组合数，记作或 $C_n^m$ 。 $C_n^m=\tfrac{n!}{m!(n-m)!},C_n^0=1$

组合公式

1.证明 $C_n^m=C_n^{n-m}$

$C_n^m=C_n^{n-m}$
$\Rightarrow \tfrac{n!}{m!(n-m)!}=\tfrac{n!}{(n-m)!(n-n+m)!}$
$\Rightarrow\tfrac{n!}{m!(n-m)!}=\tfrac{n!}{m!(n-m)!}$

2.证明 $C_n^mC_m^k=C_n^kC_{n-k}^{m-k}$

$C_n^mC_m^k=C_n^kC_{n-k}^{m-k}$
$\Rightarrow\tfrac{n!}{m!(n-m)!}\times\tfrac{m!}{k!(m-k)!}=\tfrac{n!}{k!(n-k)!}\times\tfrac{(n-k)!}{(m-k)!(n-m)!}$
$\Rightarrow\tfrac{n!}{k!(n-m)!(m-k)!}=\tfrac{n!}{k!(n-m)!(m-k)!}$

3.证明 $\sum_{i=0}^nC_n^i=2^n$

这里我们需要使用二项式展开式。
我们知道： $(a+b)^n=C_n^0a^n+C_n^1a^{n-1}b+C_n^2a^{n-2}b^2+...+C_n^nb^n=\sum_{i=0}^nC_n^ia^{n-i}b^i$

我们令 $a=b=1$
则 $2^n=\sum_{i=0}^nC_n^i$ ，得证。

4.证明 $C_{n+m}^k=\sum_{i=0}^kC_n^i\times C_{m}^{k-i}$

我们令： $(1+x)^{n+m}=(1+x)^m\times(1+x)^n$
由上一个定理知： $\Rightarrow\sum_{k=0}^{n+m}C_{n+m}^kx^k=\sum_{i=0}^nC_n^ix^i\times\sum_{j=0}^mC_m^jx^j$
因为左右相等，所以我们 $x^k$ 要对应 $x^i*x^{k-i}$ 才行啊。
又因为 $x^i*x^{k-i}$ 有 $k$ 项。
所以： $C_{n+m}^kx^k=\sum_{i=0}^kC_n^ix^i\times C_{m}^{k-i}x^{k-i}$
$C_{n+m}^kx^k=\sum_{i=0}^kC_n^i\times C_{m}^{k-i}x^k$
两边约掉 $x^{k}$ 后得证。

盒子放求问题

1.球相同，盒不同，无空盒

我们使用隔板法。
这种问题就相当于是：在 $n-1$ 个球缝隙之间插入 $m-1$ 个隔板，将球分成 $n$ 份。
所以 $ans=C_{n-1}^{m-1}$ 。
代码

#include <bits/stdc++.h>
using namespace std;
int n,m;

int Factorial(int x) {
    int ans=1;
    for(int i=2;i<=x;i++) ans*=i;
    return ans;
}

int Combination(int n,int m) { return Factorial(n)/Factorial(m)/Factorial(n-m); }

int main() {
    scanf("%d %d",&n,&m);
    printf("%d",Combination(n-1,m-1));
    return 0;
}

2.球相同，盒不同，可以空盒

我们就预先在 $m$ 个盒中加一个虚拟球，然后问题就转换成了第一个问题。 $ans=C_{n+m-1}^{m-1}$ 。
代码

#include <bits/stdc++.h>
using namespace std;
int n,m;

int Factorial(int x) {
    int ans=1;
    for(int i=2;i<=x;i++) ans*=i;
    return ans;
}

int Combination(int n,int m) { return Factorial(n)/Factorial(m)/Factorial(n-m); }

int main() {
    scanf("%d %d",&n,&m);
    printf("%d",Combination(n+m-1,m-1));
    return 0;
}

3.球不同，盒相同，无空盒

这就是第二类斯特林数：
我们定义 $f[i][j]$ 为前 $i$ 个球放入 $j$ 个盒子的方案数。
我们把这个球放在前 $j$ 个盒子中，就有 $m\times f[i-1][j]$ 种方案。
我们把这个球放在第 $j$ 个新盒子中，就有 $f[i-1][j-1]$ 种方案。
所以状态转移方程式为：

f[i][j]=j*f[i-1][j]+f[i-1][j-1];

我们的初始化为：

f[0][0]=1;

代码

#include <bits/stdc++.h>
using namespace std;
int n,m,f[15][15];

int main() {
    scanf("%d %d",&n,&m);
    f[0][0]=1;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=m;j++)
            f[i][j]=j*f[i-1][j]+f[i-1][j-1];
    }
    printf("%d",f[n][m]);
    return 0;
}

4.球不同，盒相同，可以空盒

这道题与第三道很像。
状态转移方程式：

for(int i=1;i<=m;i++) ans+=f[n][i];

我们就分别把 $n$ 个球放进前 $1$ 个盒子，把 $n$ 个球放进前 $2$ 个盒子...把 $n$ 个球放进前 $m$ 个盒子。
代码

#include <bits/stdc++.h>
using namespace std;
int n,m,f[15][15],ans;

int main() {
    scanf("%d %d",&n,&m);
    f[0][0]=1;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=m;j++)
            f[i][j]=j*f[i-1][j]+f[i-1][j-1];
    }
    for(int i=1;i<=m;i++) ans+=f[n][i];
    printf("%d",ans);
    return 0;
}

5.球不同，盒不同，无空盒

我们可以看做第三个问题。只是因为盒子不同，所以我们需要将盒子排个序，共有： $A_m^m=\tfrac{m!}{(m-m)!}=m!$
所以 $ans=m!\times f[n][m]$
代码

#include <bits/stdc++.h>
using namespace std;
int n,m,f[15][15],ans=1;

int main() {
    scanf("%d %d",&n,&m);
    f[0][0]=1;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=m;j++)
            f[i][j]=j*f[i-1][j]+f[i-1][j-1];
    }
    for(int i=2;i<=m;i++) ans*=i;
    printf("%d",ans*f[n][m]);
    return 0;
}

6.球不同，盒不同，可以空盒

每个球都可以选任意盒子，每个球有 $m$ 种选法，所以 $n$ 个球就有： $ans=m^n$ 。
代码

#include <bits/stdc++.h>
using namespace std;
int n,m;

int Quick_Power(int a,int b) {
    int ans=1;
    while(b) {
        if(b&1) ans=ans*a;
        b>>=1,a=a*a;
    }
    return ans;
}

int main() {
    scanf("%d %d",&n,&m);
    printf("%d",Quick_Power(m,n));
    return 0;
}

7.球相同，盒相同，无空盒

我们定义 $f[n][m]$ 为 $n$ 个球 $m$ 个盒子的方案数。
则：

for(int k=1;k<=j;k++)
    f[i][j]=(f[i][j]+f[i-j][k])%MOD;

我们先铺 $m$ 个球分别到 $m$ 个盒子，然后剩下 $n-m$ 个球随便放。
代码

#include <bits/stdc++.h>
using namespace std;
const int MOD=12345;
int n,m,f[1005][1005];

int main() {
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) f[i][1]=f[i][i]=f[i][i-1]=1;

    for(int i=1;i<=n;i++) {
        for(int j=2;j<=min(m,i-2);j++) {
            for(int k=1;k<=j;k++) 
                f[i][j]=(f[i][j]+f[i-j][k])%MOD;
        }
    }
    printf("%d",f[n][m]);
    return 0;
}

8.球相同，盒相同，可以空盒

我们就放 $m$ 个虚拟球分别到 $m$ 个盒子，然后 $n$ 个球随便放。
代码

#include <bits/stdc++.h>
using namespace std;
const int MOD=12345;
int n,m,f[2005][1005];

int main() {
    scanf("%d %d",&n,&m);
    n+=m;
    for(int i=1;i<=n;i++) f[i][1]=f[i][i]=f[i][i-1]=1;

    for(int i=1;i<=n;i++) {
        for(int j=2;j<=min(m,i-2);j++) {
            for(int k=1;k<=j;k++) 
                f[i][j]=(f[i][j]+f[i-j][k])%MOD;
        }
    }
    printf("%d",f[n][m]);
    return 0;
}