z*****n
发帖数: 7639 | 1 m个不同颜色的球放入n个不同颜色的篮子，
至少有一个篮子里面有且只有一个球的情况
有多少种？
我的想法是：先取一个球，放入某个篮子，共有 m x n
种可能。其余的 m-1 个球 放入 n-1 个篮子，共有
(n-1)^(m-1) 种可能。
可是这样 m x n x (n-1)^(m-1) 大于 n^m 了。
各位帮忙看看问题在哪? |
q*****g
发帖数: 1568 | 2 你们都错了，都错在重复计算了一些组合。好比你最开始的那个例子，首先
如果第一个瓶子只有一个（任意的）球的组合是 x, 那么你不能简单的把它
乘以n，因为在第一个瓶子只有一个球的这种情况里照样包含了第二个瓶子里
只有一个球的可能性。
等我想想有什么简单的方法。
【在 z*****n 的大作中提到】
: m个不同颜色的球放入n个不同颜色的篮子，
: 至少有一个篮子里面有且只有一个球的情况
: 有多少种？
: 我的想法是：先取一个球，放入某个篮子，共有 m x n
: 种可能。其余的 m-1 个球 放入 n-1 个篮子，共有
: (n-1)^(m-1) 种可能。
: 可是这样 m x n x (n-1)^(m-1) 大于 n^m 了。
: 各位帮忙看看问题在哪?
|
A***o
发帖数: 2783 | 3 又看了看，这个也不对，这个说的是n个球都1-1放篮子了。
应该再加上放n-1，n-2个的情况。。。
n-1的情况是：
m! x n |
q*****g
发帖数: 1568 | 4 刚才我想了半天也没想出个可行的解。（求和号套两层的那个叫cheating，呵呵）
做这种排列组合的题我学的那些什么测度论泛函分析实在没有用武之地。。。。。
这么说吧，我想老莫有一点是对的，就是我们应当首先忘掉m个球的排列问题，
首先考虑这么一个问题：
有L1, L2, ... Ln个非负整数满足：L1 + L2 + ... + Ln = m，那么有多少种组合
方式有大于等于一个L正好等于1？记这个数字为X。
显然，这些L指的是某个瓶子里的球的个数。最后的答案当然是X * m!。
我现在知道怎么求所有没有限制的那些整数组合：m+n-1 choose n-1.
我还知道怎么算这样的组合数：
所有的L都必须大于一 m-1 choose n-1
或者
所有的L都必须大于2 m-n-1 choose n-1
不过你那个玩意还不能用简单的减法来实现。。。。。:(
【在 A***o 的大作中提到】
: 又看了看，这个也不对，这个说的是n个球都1-1放篮子了。
: 应该再加上放n-1，n-2个的情况。。。
:
: n-1的情况是：
: m! x n
|
z*****n
发帖数: 7639 | 5 不一样，4 个球放2 个篮子和2个球放4个篮子的结果
不同。
【在 A***o 的大作中提到】
: 又看了看，这个也不对，这个说的是n个球都1-1放篮子了。
: 应该再加上放n-1，n-2个的情况。。。
:
: n-1的情况是：
: m! x n
|
q*****g
发帖数: 1568 | 6
如果问题是：至少有一个篮子的球的个数是零，那倒是容易得紧，可以直接
做减法：
(m+n-1 choose n-1) - (m-1 choose n-1)
如果问题是: 至少有一个篮子的球的个数是零或者一也好办,还是减法:
(m+n-1 choose n-1) - (m-n-1 choose n-1)
但怎么把这两个东西分离我还没想出来简单办法
【在 q*****g 的大作中提到】
: 刚才我想了半天也没想出个可行的解。（求和号套两层的那个叫cheating，呵呵）
: 做这种排列组合的题我学的那些什么测度论泛函分析实在没有用武之地。。。。。
: 这么说吧，我想老莫有一点是对的，就是我们应当首先忘掉m个球的排列问题，
: 首先考虑这么一个问题：
: 有L1, L2, ... Ln个非负整数满足：L1 + L2 + ... + Ln = m，那么有多少种组合
: 方式有大于等于一个L正好等于1？记这个数字为X。
: 显然，这些L指的是某个瓶子里的球的个数。最后的答案当然是X * m!。
: 我现在知道怎么求所有没有限制的那些整数组合：m+n-1 choose n-1.
: 我还知道怎么算这样的组合数：
: 所有的L都必须大于一 m-1 choose n-1
|
z*****n
发帖数: 7639 | 7 我想还是应该从确定某个篮子只放一个
球入手，
另外，全部可能性的数目是 n^m。这是一个string问题。
【在 q*****g 的大作中提到】
:
: 如果问题是：至少有一个篮子的球的个数是零，那倒是容易得紧，可以直接
: 做减法：
: (m+n-1 choose n-1) - (m-1 choose n-1)
: 如果问题是: 至少有一个篮子的球的个数是零或者一也好办,还是减法:
: (m+n-1 choose n-1) - (m-n-1 choose n-1)
: 但怎么把这两个东西分离我还没想出来简单办法
|
q*c
发帖数: 9453 | 8 m*n 那个特别的一个篮子一个球.
m-1 个球随便放 n-1 个篮子, 考虑到根本不放, 增加一个额外"漏斗篮子".
(m-1)^n 种方法,
一共是 m*n * (m-1)^n
【在 q*****g 的大作中提到】
: 刚才我想了半天也没想出个可行的解。（求和号套两层的那个叫cheating，呵呵）
: 做这种排列组合的题我学的那些什么测度论泛函分析实在没有用武之地。。。。。
: 这么说吧，我想老莫有一点是对的，就是我们应当首先忘掉m个球的排列问题，
: 首先考虑这么一个问题：
: 有L1, L2, ... Ln个非负整数满足：L1 + L2 + ... + Ln = m，那么有多少种组合
: 方式有大于等于一个L正好等于1？记这个数字为X。
: 显然，这些L指的是某个瓶子里的球的个数。最后的答案当然是X * m!。
: 我现在知道怎么求所有没有限制的那些整数组合：m+n-1 choose n-1.
: 我还知道怎么算这样的组合数：
: 所有的L都必须大于一 m-1 choose n-1
|
