t********t
发帖数: 62 | 1 把X个不同颜色的球扔到Y个不同的桶里。 要求每个桶里有至少一个球。 问：共有多少
种不同结果？ | c*m
发帖数: 1114 | 2 (X-1)!*X!/[(Y-1)!(X-Y)!]
基本上就是C(X-1,Y-1)*X!的意思。这里当然需要X>=Y
【在 t********t 的大作中提到】
: 把X个不同颜色的球扔到Y个不同的桶里。 要求每个桶里有至少一个球。 问：共有多少
: 种不同结果？
| b******v
发帖数: 1493 | 3 当Y=1时，答案应该是1，但是你的答案是X!
还有Y=2时，答案应该是2^X-2
【在 c*m 的大作中提到】
: (X-1)!*X!/[(Y-1)!(X-Y)!]
: 基本上就是C(X-1,Y-1)*X!的意思。这里当然需要X>=Y
| b******v
发帖数: 1493 | 4 设f(n,k)为把n个不同颜色的球扔到k个不同的桶里，每个桶至少一个球的扔法总数。
k^n = C(k,1)*f(n,1)+C(k,2)*f(n,2)+...+C(k,k-1)*f(n,k-1)+f(n,k)
容易看出f(n,1) = 1
由此可以用数学归纳法得到
f(n,k) = sum_{i=0,...,k-1} (-1)^i*C(k,i)*(k-i)^n
不知道有没有简便一点的解法？
【在 t********t 的大作中提到】
: 把X个不同颜色的球扔到Y个不同的桶里。 要求每个桶里有至少一个球。 问：共有多少
: 种不同结果？
| t********t
发帖数: 62 | 5 佩服佩服。我想了一天，也没有想出一个像你一样的公式来。
我只得到一个递归的公式 f(n,k) = k*f(n-1,k-1) + k*f(n-1,k)
再问一句，我想我能用数学归纳法证明你的结果是正确的。 但是你是如何得到你的结
果呢？
【在 b******v 的大作中提到】
: 设f(n,k)为把n个不同颜色的球扔到k个不同的桶里，每个桶至少一个球的扔法总数。
: k^n = C(k,1)*f(n,1)+C(k,2)*f(n,2)+...+C(k,k-1)*f(n,k-1)+f(n,k)
: 容易看出f(n,1) = 1
: 由此可以用数学归纳法得到
: f(n,k) = sum_{i=0,...,k-1} (-1)^i*C(k,i)*(k-i)^n
: 不知道有没有简便一点的解法？
| t********t
发帖数: 62 | 6 谢谢！
【在 c*m 的大作中提到】
: (X-1)!*X!/[(Y-1)!(X-Y)!]
: 基本上就是C(X-1,Y-1)*X!的意思。这里当然需要X>=Y
| b******v
发帖数: 1493 | 7 哈哈，其实我是用笨办法试了k=1,2,3,4,5，然后总结出一般公式的
希望有牛人出来给出简洁的解法
【在 t********t 的大作中提到】
: 佩服佩服。我想了一天，也没有想出一个像你一样的公式来。
: 我只得到一个递归的公式 f(n,k) = k*f(n-1,k-1) + k*f(n-1,k)
: 再问一句，我想我能用数学归纳法证明你的结果是正确的。 但是你是如何得到你的结
: 果呢？
| t********t
发帖数: 62 | 8 你这个总结厉害啊！ 总结出 (-1)^i, (k-i)^n. 实在是高啊！！！！
【在 b******v 的大作中提到】
: 哈哈，其实我是用笨办法试了k=1,2,3,4,5，然后总结出一般公式的
: 希望有牛人出来给出简洁的解法
| b******v
发帖数: 1493 | 9 多谢
其实写到k=5的时候，就比较显然了，笨人有笨办法 :P
【在 t********t 的大作中提到】
: 你这个总结厉害啊！ 总结出 (-1)^i, (k-i)^n. 实在是高啊！！！！
| d******e
发帖数: 7844 | 10 等价于Y = X1 + X2 + ... + Xk有多少个正整数根。
相当于Y-1个位置，塞K-1个隔断。(Y-1)!/(K-1)!/(Y-K)!
【在 b******v 的大作中提到】
: 哈哈，其实我是用笨办法试了k=1,2,3,4,5，然后总结出一般公式的
: 希望有牛人出来给出简洁的解法
| b******v
发帖数: 1493 | 11 这是球无法区分的情形吧，可是原题中球是不同颜色的
【在 d******e 的大作中提到】
: 等价于Y = X1 + X2 + ... + Xk有多少个正整数根。
: 相当于Y-1个位置，塞K-1个隔断。(Y-1)!/(K-1)!/(Y-K)!
| t********t
发帖数: 62 | 12 对的。 distinguishable objects and distinguishable boxes
【在 b******v 的大作中提到】
: 这是球无法区分的情形吧，可是原题中球是不同颜色的
| D******n
发帖数: 2836 | 13 inclusion exclusion rule....
【在 t********t 的大作中提到】
: 你这个总结厉害啊！ 总结出 (-1)^i, (k-i)^n. 实在是高啊！！！！
|
|
