球和盒子的组合数学问题

组合数学问题"/>

球和盒子的组合数学问题

n个球装入m个盒子的8中情况。
第二类stirling数S[n,m]=S[n-1,m-1]+m*S[n-1,m]
1：n个球相同，m个盒子不同，盒子不可空。ans=C(n-1,m-1)
2：n个球相同，m个盒子不同，盒子可空。ans=C(n+m-1,m-1)

3：n个球相同，m个盒子相同，盒子不可空。(数的拆分)ans=dp[n][m]=dp[n-1][m-1]+dp[n-m][m];
4：n个球相同，m个盒子相同，盒子可空。ans=dp[n][1]+...+dp[n][min(n,m)]

5：n个不同的球，m个盒子相同，盒子不可空。ans=S[n,m]
6：n个不同的球，m个盒子相同，盒子可空。ans=S[n,1]+S[n,2]+...+S[n,min(n,m)]

7：n个不同的球，m个不同的盒子，盒子不可空。ans=S[n,m]*m!
8：n个不同的球，m个不同的盒子，盒子可空。ans=m^n