n个球放k个盒子问题归纳

问题描述：有n个球，放进k个盒子，有多少种不同的放法？（球必须全部放在盒子中，不能丢弃）

球可能相同，也可能不同，盒子亦然。另外，盒子可能限定可为空，也可能限定不可为空。这样就有8种可能：

符号注释

1、 C n k C_n^k Cnk​：组合数， C n k = n ! k ! ( n − k ) ! C_n^k=\frac{n!}{k!(n-k)!} Cnk​=k!(n−k)!n!​

2、 d ( n , k ) d(n,k) d(n,k)：划分数，将正整数n划分为k个其它正整数（正整数，当然不能为0）的划分方法数。递推公式： d ( n , k ) = ∑ i = 1 m d ( n − k , i ) ,    m = m i n { m − n , n } d(n,k)=\sum_{i=1}^md(n-k,i),\ \ m=min\{m-n,n\} d(n,k)=∑i=1m​d(n−k,i),  m=min{m−n,n}。特别地， d ( n , 1 ) = d ( n , n ) = 1 d(n,1)=d(n,n)=1 d(n,1)=d(n,n)=1，如果 k > n k>n k>n则 d ( n , k ) = 0 d(n,k)=0 d(n,k)=0。

3、 S ( n , k ) S(n,k) S(n,k)：第二类斯特林数，将n个不同元素划分为k个非空集合的划分方法数。递推公式： S ( n , k ) = S ( n − 1 , k − 1 ) + k ∗ S ( n − 1 , k ) S(n,k)=S(n-1,k-1)+k*S(n-1,k) S(n,k)=S(n−1,k−1)+k∗S(n−1,k)。

4、总划分数 D ( n , k ) D(n,k) D(n,k)是指将正整数n划分为不超过k个正整数的划分总数。显然， D ( n , k ) = ∑ i = 1 k d ( n , i ) D(n,k)=\sum_{i=1}^kd(n,i) D(n,k)=∑i=1k​d(n,i)。特别地，如果 k > n k>n k>n，则 D ( n , k ) = D ( n , n ) D(n,k)=D(n,n) D(n,k)=D(n,n)。但有一个更快的计算方法：由划分数的递推公式可得： D ( n , k ) − D ( n , k − 1 ) = D ( n − k , k ) D(n,k)-D(n,k-1)=D(n-k,k) D(n,k)−D(n,k−1)=D(n−k,k)，也就是 D ( n , k ) = D ( n − k , k ) + D ( n , k − 1 ) D(n,k)=D(n-k,k)+D(n,k-1) D(n,k)=D(n−k,k)+D(n,k−1)。这样，计算 D ( n , k ) D(n,k) D(n,k)就可以在 O ( n k ) O(nk) O(nk)的时间内完成。又 d ( n , k ) = D ( n , k ) − D ( n , k − 1 ) = D ( n − k , k ) d(n,k)=D(n,k)-D(n,k-1)=D(n-k,k) d(n,k)=D(n,k)−D(n,k−1)=D(n−k,k)，则 d ( n , k ) d(n,k) d(n,k)的计算可以在 O ( ( n − k ) k ) O((n-k)k) O((n−k)k)时间内完成。

各种情况详解

1、这个明显就是划分数。划分数的推导：由于每个盒子都不能为空，所以至少能放k个球。假设一个合法的划分已完成，此时从每个盒子中拿出一个球，还剩 n − k n-k n−k个球。如果没有空盒子，相当于把 n − k n-k n−k个球划分成k部分，这样合法的划分有 d ( n − k , k ) d(n-k,k) d(n−k,k)种；如果有一个空盒子，相当于 n − k n-k n−k个球划分为 k − 1 k-1 k−1部分，情况有 d ( n − k , k − 1 ) d(n-k,k-1) d(n−k,k−1)种，以此类推，可得递推公式。

2、与1同理。另外一种思考角度：考虑 D ( n , k ) D(n,k) D(n,k)，如果至少一个盒子不放球，就有 D ( n , k − 1 ) D(n,k-1) D(n,k−1)种方法；如果所有盒子都放球，那么从每个盒子中拿出一个球，剩余 n − k n-k n−k个球，相当于把这 n − k n-k n−k个球放到k个盒子中， D ( n − k , k ) D(n-k,k) D(n−k,k)。可得递推公式 D ( n , k ) = D ( n , k − 1 ) + D ( n − k , k ) D(n,k)=D(n,k-1)+D(n-k,k) D(n,k)=D(n,k−1)+D(n−k,k)。

3、刚好符合第二类斯特林数的定义。第二类斯特林数的推导：考虑前n-1个元素的划分结果。现在要把第n个元素插进去。如果前n-1个元素已经形成 k k k个集合，则可以将第n个元素放入任意一个集合中， k S ( n − 1 , k ) kS(n-1,k) kS(n−1,k)。如果前n-1个元素已经形成 k − 1 k-1 k−1个集合，则必须将第n个元素独立成一个集合， S ( n − 1 , k − 1 ) S(n-1,k-1) S(n−1,k−1)。如果前n-1个元素形成少于 k − 1 k-1 k−1个集合，则无论如何放置第k个元素，都无法形成k个集合。因此得到递推公式 S ( n , k ) = S ( n − 1 , k − 1 ) + k S ( n − 1 , k ) S(n,k)=S(n-1,k-1)+kS(n-1,k) S(n,k)=S(n−1,k−1)+kS(n−1,k)。

4、显然，就是第3种情况的扩展，k个盒子，允许空盒子，相当于1~k个盒子，且不允许空盒子的结果之和。

5、隔板法。n个相同球划分成k个不同的非空部分，相当于用k-1个隔板将其隔开。这k-1个隔板可以插入n个球中间的n-1个缝隙中，也就是组合数 C n − 1 k − 1 C_{n-1}^{k-1} Cn−1k−1​。

6、依然是隔板法。这次每个部分可以为空，这样就相当于k-1个隔板可以和这n个球任意排列，也就是组合数 C n + k − 1 k − 1 C_{n+k-1}^{k-1} Cn+k−1k−1​。

7、盒子不同，相当于在盒子相同的情况下给盒子编号，这样共有 A k k = k ! A_k^k=k! Akk​=k!种编号方法，答案为 k ! S ( n , k ) k!S(n,k) k!S(n,k)。

8、（这个最简单，自己思考吧）

补充

1、贝尔数 B ( n ) B(n) B(n)：将n个不同元素划分为若干非空集合的划分方法数。集合个数可以为1、2、…、n。显然， B ( n ) = ∑ i = 1 n S ( n , k ) B(n)=\sum_{i=1}^nS(n,k) B(n)=∑i=1n​S(n,k)。特别地， B ( 0 ) = 1 B(0)=1 B(0)=1。

贝尔数符合递推公式 B ( n + 1 ) = ∑ i = 0 n C n k B ( k ) B(n+1)=\sum_{i=0}^nC_n^kB(k) B(n+1)=∑i=0n​Cnk​B(k)。

2、情况7，也就是球不同，盒子不同，且不可以为空的情况，还有一种思考角度，容斥原理。首先考虑k个盒子自由选择的情况， f ( 0 ) = k n f(0)=k^n f(0)=kn。然后，考虑至少1个盒子不放的情况，有 C k 1 ( k − 1 ) n C_k^1(k-1)^n Ck1​(k−1)n，这其中又包括至少2个盒子不放的情况，为 C k 2 ( k − 2 ) n C_k^2(k-2)^n Ck2​(k−2)n，以此类推，可得最终结果为 ∑ i = 0 k ( − 1 ) i ( k − i ) n \sum_{i=0}^k(-1)^i(k-i)^n ∑i=0k​(−1)i(k−i)n。实现的复杂度：计算 0 − k 0-k 0−k的n次幂需要 O ( k n ) O(kn) O(kn)（通过快速幂可以达到 O ( k l o g n ) O(klogn) O(klogn)），求和需要 O ( k ) O(k) O(k)，最终总时间最好可达 O ( k l o g n ) O(klogn) O(klogn)。