j******n
发帖数: 91 | 1 经典问题：k个identical球放入n个非identical的盒子中，问总共有几种放法。
我的思路是：把该问题转化为一个排列问题。一共有n+k个位子，把球和盒子放入其中
，每人占一个坑。第一个位子必须是盒子，有n种取法。剩下的n+k-1个位子，方法总共
有(n+k-1)!/k!，因为k个球是identical的。那么总共有n*(n+k-1)!/k种方法。
但这题的正确答案分明就是C(n+k-1, k)。也就是说我的想法多了n!。那么简单的问题
，脑子短路了，大家来纠错啊 |
g*****o
发帖数: 812 | 2 你多考虑了盒子里面球的顺序吧
【在 j******n 的大作中提到】
: 经典问题：k个identical球放入n个非identical的盒子中，问总共有几种放法。
: 我的思路是：把该问题转化为一个排列问题。一共有n+k个位子，把球和盒子放入其中
: ，每人占一个坑。第一个位子必须是盒子，有n种取法。剩下的n+k-1个位子，方法总共
: 有(n+k-1)!/k!，因为k个球是identical的。那么总共有n*(n+k-1)!/k种方法。
: 但这题的正确答案分明就是C(n+k-1, k)。也就是说我的想法多了n!。那么简单的问题
: ，脑子短路了，大家来纠错啊
|
j******n
发帖数: 91 | 3 好像没有啊。举例来说，3个盒子2个球，（O表示盒子，*表示球）O**OO就表示第一个
盒子里有2个球而后两个盒子中没球；同理OO*O*表示第2和第三个盒子中分别有一个球。
除以k!就已经把盒子里球的顺序排除了。
【在 g*****o 的大作中提到】
: 你多考虑了盒子里面球的顺序吧
|
f****l
发帖数: 66 | 4 你的思路是基本正确的，但是问题本身不care箱子的排序，只care每个箱子中的球数，
所以你的方法重复数了箱子的n!的排列。可以考虑箱子按照一定顺序放好了，然后球也
放好了，这样结果数就是球的位置可能数，也就是C(n+k-1,n) |
m*******e
发帖数: 90 | 5 插板法
n个盒子，只需要n-1块板将其分隔，再加上k个球，一共n+K-1个位置。
从中选出k个位置放球，所以是C(n+k-1, k)
【在 j******n 的大作中提到】
: 经典问题：k个identical球放入n个非identical的盒子中，问总共有几种放法。
: 我的思路是：把该问题转化为一个排列问题。一共有n+k个位子，把球和盒子放入其中
: ，每人占一个坑。第一个位子必须是盒子，有n种取法。剩下的n+k-1个位子，方法总共
: 有(n+k-1)!/k!，因为k个球是identical的。那么总共有n*(n+k-1)!/k种方法。
: 但这题的正确答案分明就是C(n+k-1, k)。也就是说我的想法多了n!。那么简单的问题
: ，脑子短路了，大家来纠错啊
|
j******n
发帖数: 91 | 6 谢谢！不过我还是不明白，既然箱子是non-identical的，这种non-identical就只能通
过“排序”反映出来。为什么要除以k!？因为球是identical的，所以不考虑“排序”
；现在我再除以n!，那不就意味着箱子也是identical的了吗？箱子的non-identical如
何体现呢？
这是我疑惑的地方，请指点。
【在 f****l 的大作中提到】
: 你的思路是基本正确的，但是问题本身不care箱子的排序，只care每个箱子中的球数，
: 所以你的方法重复数了箱子的n!的排列。可以考虑箱子按照一定顺序放好了，然后球也
: 放好了，这样结果数就是球的位置可能数，也就是C(n+k-1,n)
|
j******n
发帖数: 91 | |
j******n
发帖数: 91 | 8 抱歉啊，我越想越觉得这个思路的前提是认为这n个盒子是identical的。。。
【在 m*******e 的大作中提到】
: 插板法
: n个盒子，只需要n-1块板将其分隔，再加上k个球，一共n+K-1个位置。
: 从中选出k个位置放球，所以是C(n+k-1, k)
|
f*****s
发帖数: 84 | 9 这个不对吧，如果都是一样的球和盒子的话，第一个球放进去的时候只有一种情况，不
是n种情况吧
【在 j******n 的大作中提到】
: 有n^k种。
|
j******n
发帖数: 91 | 10 我日，我看错了，看成了两个都是inidentical。
【在 f*****s 的大作中提到】
: 这个不对吧，如果都是一样的球和盒子的话，第一个球放进去的时候只有一种情况，不
: 是n种情况吧
|
i******y
发帖数: 13 | 11 楼上说的没错
你把球和板看成都是空的位置共n+k-1
这个位置是有序号的
即你说的的不identical
从中间选出k个位置
所以是c(n+k-1,k)
【在 j******n 的大作中提到】
: 抱歉啊，我越想越觉得这个思路的前提是认为这n个盒子是identical的。。。
|
f****l
发帖数: 66 | 12 箱子不是identical的，但是箱子的所谓“排序”是一种重复。比如有两个箱子AB，三
个球ooo.
AoBoo和BooAo,在你的方法中是不一样的，但事实上是一样的结果（A箱子中一个球，B
箱子中两个球）。因此你的结果需要除以箱子的排序数k!（这个例子中是2！）
【在 j******n 的大作中提到】
: 谢谢！不过我还是不明白，既然箱子是non-identical的，这种non-identical就只能通
: 过“排序”反映出来。为什么要除以k!？因为球是identical的，所以不考虑“排序”
: ；现在我再除以n!，那不就意味着箱子也是identical的了吗？箱子的non-identical如
: 何体现呢？
: 这是我疑惑的地方，请指点。
|
j******n
发帖数: 91 | 13 NICE! 哈哈，谢谢你解答了我的疑惑！
B
【在 f****l 的大作中提到】
: 箱子不是identical的，但是箱子的所谓“排序”是一种重复。比如有两个箱子AB，三
: 个球ooo.
: AoBoo和BooAo,在你的方法中是不一样的，但事实上是一样的结果（A箱子中一个球，B
: 箱子中两个球）。因此你的结果需要除以箱子的排序数k!（这个例子中是2！）
|
s*********h
发帖数: 6288 | 14 爱因斯坦挡板法
【在 j******n 的大作中提到】
: 经典问题：k个identical球放入n个非identical的盒子中，问总共有几种放法。
: 我的思路是：把该问题转化为一个排列问题。一共有n+k个位子，把球和盒子放入其中
: ，每人占一个坑。第一个位子必须是盒子，有n种取法。剩下的n+k-1个位子，方法总共
: 有(n+k-1)!/k!，因为k个球是identical的。那么总共有n*(n+k-1)!/k种方法。
: 但这题的正确答案分明就是C(n+k-1, k)。也就是说我的想法多了n!。那么简单的问题
: ，脑子短路了，大家来纠错啊
|
