Description
现有r个互不相同的盒子和n个互不相同的球，要将这n个球放入r个盒子中，且不允许有空盒子。则有多少种放法？
Input
n, r(0 <= n, r <= 10)。
Output
有多少种放法。
Sample Input
3 2
Sample Output
6
知识点：
1 . 全排列：
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
2 . 循环排列：
五个元素的循环全排列中的一种，变成直线排列则有5种，设循环排列有x种，则直线排列有5x种，但五个元素的直线全排列有5！种，所以得到
显然，推广到m个相异元素，它的循环全排列的种数（设为x），仍可仿此得到，即
从m个元素里选出n个元素的 循环 排列，可以按组合选出n个元素，然后将选出的n个元素进行循环全排列。设它的全排列种数为x，因为n个元素的循环全排列种数为（n-1）！，所以得到
3 . 斯特林数概念：
Stirling数出现在许多组合枚举问题中。对第一类Stirling数 
第二类Stirling数
，同时可记为
[与第一类的表示有大小写的区别]。其表示将n个不同的元素分成m个集合的方案数。
，同时可记为 [与第一类的表示有大小写的区别]。其表示将n个不同的元素分成m个集合的方案数。 4 . 第一类斯特林数
递推式
无符号第一类Stirling数的递推式可以从其定义来推导：
考虑其定义如果要将n+1元素构成m个圆排列，考虑第n+1个元素：
（1）如果n个元素构成了m-1个圆排列，那么第n+1个元素独自构成一个圆排列。方案数： 
（2）如果n个元素构成了m个圆排列，将第n+1个元素插入到任意元素的左边。方案数：
综合两种情况得：
而有符号的第一类Stirling数可以从其表示的降阶函数归纳证明（简单写如下）：
依次把
在左右两边的系数提取出来得：
在左右两边的系数提取出来得： 5 . 第二类斯特林数
递推式
第二类Stirling数的推导和第一类Stirling数类似，可以从定义出发考虑第n+1个元素的情况，假设要把n+1个元素分成m个集合则分析如下：
（1）如果n个元素构成了m-1个集合，那么第n+1个元素单独构成一个集合。方案数
。
。 （2）如果n个元素已经构成了m个集合，将第n+1个元素插入到任意一个集合。方案数 m*S(n,m) 。
综合两种情况得：
6 . 应用举例(很重要）
第二类Stirling数主要是用于解决组合数学中的几类放球模型。主要是针对于球之前有区别的放球模型：
（1）n个不同的球，放入m个无区别的盒子，不允许盒子为空。
方案数：
。这个跟第二类Stirling数的定义一致。
。这个跟第二类Stirling数的定义一致。 （2）n个不同的球，放入m个有区别的盒子，不允许盒子为空。
方案数：
。因盒子有区别，乘上盒子的排列即可。
。因盒子有区别，乘上盒子的排列即可。 （3）n个不同的球，放入m个无区别的盒子，允许盒子为空。
方案数：
。枚举非空盒的数目便可。
。枚举非空盒的数目便可。 （4）n个不同的球，放入m个有区别的盒子，允许盒子为空。
①方案数：
。同样可以枚举非空盒的数目，注意到盒子有区别，乘上一个排列系数。
。同样可以枚举非空盒的数目，注意到盒子有区别，乘上一个排列系数。 ②既然允许盒子为空，且盒子间有区别，那么对于每个球有m种选择，每个球相互独立。有方案数：
。
。 不妨设这N个小球为a1 ， a2 ，…，an .首先把a1 放进盒子里，因为M个盒子是不同的，所以有M种放法，同理，a2 ，…，an放进盒子里都有M种放法，依乘法原则知不同的方案数 N = M*M*。。。M（共N个)=M^N
上述式子可以应用于第二类Stirling数通项的求解。
两类Stirling数之间的关系
两类Stirling数之间的递推式和实际含义很类似，事实上他们之间存在一个互为转置的转化关系：
类似于矩阵的对称转置关系。
第一类斯特林函数：将 n 个不同元素构成m个圆排列，如果要将n + 1个元素构成m个圆排列，考虑第n + 1个元素：
（1）如果n个元素构成m - 1个圆排列，则第n + 1个元素独自构成一个圆排列：s(n, m - 1)；
（2）如果n个元素构成m个圆排列，则第n + 1个元素插入任意元素的左边：n * s(n, m)；
总和s(n + 1, m) = s(n, m - 1) + n * s(n, m)。
（1）如果n个元素构成m - 1个集合，则第n + 1个元素就构成单独一个集合：s(n, m - 1);
（2）如果n个元素构成m个集合，则第n + 1个元素就查到任意一个集合：m * s(n, m);
总和s(n + 1, m) = s(n, m - 1) + m * s(n, m)。
递推公式： a[i][j] = a[i-1][j-1] + a[i-1][j] * j;
#include <cstdio>
#include <iostream>
using namespace std;
int jiecheng (int n)
{
int sum=1;
for (int i=1;i<=n;i++)
{
sum=sum*i;
}
return sum;
}
int main ()
{
int m,n,i,j;
cin >> m >> n;
long long s[11][11]={0};
for (int i=1;i<=m;i++)
{
s[i][i]=1;
}
for (i=1;i<=n;i++)
{
for (j=i+1;j<=m;j++)
{
s[j][i]=s[j-1][i-1]+s[j-1][i]*i;
}
}
cout << s[m][n]*jiecheng(n) << endl;
return 0;
}
京公网安备 11010502036488号