Question

求解一条简单的NOIP题

将n个不同颜色的球放入k个无标号的盒子中（n≥k，且盒子不允许为空）的方案数为S（n，k），例如：n=4，k=3时，S（n，k）=6，当n=6，k=3时，S（n，k）=______
请给我过程，谢谢
要是不会，帮我解一下这个递归方程就好，我没学过递归方程
S₂(n,k)=kS₂(n-1,k)+S₂(n-1,k-1)

Answer 1

s(n,k)表示将n个不同颜色的球放入k个无标号的盒子中的方案数，
根据分类加法原理，将s(n,k)个方案分为两类，
1），第n个球单独在一个盒子内，则前n-1个球在k-1个盒子内，这类方案数为s（n-1,k-1)；
2），第n个球不单独在一个盒子内，则先将前n-1个球放在k个盒子内，即s（n-1,k),然后将第n个球放在k个盒子的任意一个里，即k*s(n-1,k);
所以，有S(n,k)=kS(n-1,k)+S(n-1,k-1)。
边界情况不解释，具体可看南大版中学高级本教材···

Answer 2

你做的是NOIP的初赛题吧。
你都写出来方程了，然后手工模拟递推一下就可以了。
此类方程的通项公式非常麻烦，需要很多高级知识，一般都是带无理数之类的东西，不会加快你的计算，我不会，NOIP也不要求。

Answer 3

你强
我贝司奏

Answer 4

随便写个记忆化搜索好吧？