求一道排列组合题目

这个只能用递推做。这个题目就是：
把9个球划分为一个个非空子集，并且这些子集排列，有多少种方法。
比如：2个球，一共有：
{1} {2}
{2} {1}
{1,2}
这么3种划分＋排列的方法。

设S(n,k) 是：n个球，划分为k个非空子集，并且将这些子集排列的总方法数。
我们最后要求的就是：S(9,1)+S(9,2)+...+S(9,9)

下面我们找S(n,k)的递推公式。
不妨设这n个球是编号1、2、...、n。我们考察第n个球。
有两种可能：
(1) 第n个球自成一个集合，
(2) 第n个球与其它某些球组成一个集合。

如果是第(1)种情形，我们把{n}这个第n个球自己组成的集合拿掉，那么剩下的就是n-1个球组成的k-1个子集的排列，这个个数是：S(n-1,k-1)。
再把第n个球自己的那个集合放进来，有k个位置可以放，所以，这第(1)种情形的个数是：
k S(n-1,k-1)

如果是第(2)种情形，我们依旧把第n个球拿掉，剩下的是n-1个球组成的k个子集的排列，这个个数是：S(n-1,k)。
再把第n个球放进来，一共有k个集合可供第n个球选择，所以，这第(2)种情形的个数是：
k S(n-1,k)

所以，S(n,k)的递推公式是：
S(n,k) = k S(n-1,k-1) + k S(n-1,k)

利用这个递推公式，一个一个算就可以了。
初始值：当k=1时，S(n,1)=1；当k>n时，S(n,k)=0

举个例子，3个球：
S(1,1) = 1
S(2,1) = 1, S(2,2) = 2S(1,1) + 2S(1,2) = 2
S(3,1) = 1, S(3,2) = 2S(2,1) + 2S(2,2) = 6, S(3,3) = 3S(2,2) + 3S(2,3) = 6
所以，3个球的方法有：1+6+6 = 13种追问

不要过程，要答案

(1,1)=1
(2,1)=1 (2,2)=2
(3,1)=1 (3,2)=6 (3,3)=6
(4,1)=1 (4,2)=14 (4,3)=36 (4,4)=24
(5,1)=1 (5,2)=30 (5,3)=150 (5,4)=240 (5,5)=120
(6,1)=1 (6,2)=62 (6,3)=540 (6,4)=1560 (6,5)=1800 (6,6)=720
(7,1)=1 (7,2)=126 (7,3)=1806 (7,4)=8400 (7,5)=16800 (7,6)=15120 (7,7)=5040
(8,1)=1 (8,2)=254 (8,3)=5796 (8,4)=40824 (8,5)=126000 (8,6)=191520 (8,7)=141120 (8,8)=40320
(9,1)=1 (9,2)=510 (9,3)=18150 (9,4)=186480 (9,5)=834120 (9,6)=1905120 (9,7)=2328480 (9,8)=1451520 (9,9)=362880

总共有(9,1)+(9,2)+(9,3)+(9,4)+(9,5)+(9,6)+(9,7)+(9,8)+(9,9)=1+510+18150+186480+834120 +1905120+2328480+1451520+362880=7087261
行吗？

扔法=2的九次方=512种（包括一个球不扔）追问

3个一起扔有13种，你2的3次方只有8种

追答

你设三个球A，B，C，仍法
A
B
C
AB
AC
BC
ABC
一个球都不扔8种

追问

ABC
ACB
BAC
BCA
CAB
CBA
AB ，C
C ，AB
AC ，B
B ，AC
BC ，A
A ，BC
ABC
这才对，如果那么容易就不会提高到200分了

可以把题目在详细点么？
1、不管怎么仍，都要把这9个球都扔完么？
2、每次扔球的个数可以是随便几个么？（1到9个都可以是吧）
3、扔的顺序不同算不同的扔法，对么？追问

1肯定要扔完
2对，每次可以随便扔 ，扔9次8 7 6 5 4 3 2 1次扔完都可以
3，对

追答

没想到好的办法，
关键在于对9分解的方式太多了
比如
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 2
1 1 1 1 1 1 3
....
还是等大神来解答吧