发信人: although (.....but), 信区: BrainTeaser
标 题: 问个排列组合的问题
发信站: BBS 未名空间站 (Fri Nov 21 00:12:15 2008)

高中的表弟问我的，我想不出来呀。。。

有d 个球（球是有编号的），d'个箱子 （d' <= d），将球随机扔到箱子里，要求每个
箱子里至少有一个球，这样的组合一共有多少个？
--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 128.197.]

发信人: pcasnik (pcasnik), 信区: BrainTeaser
标 题: Re: 问个排列组合的问题
发信站: BBS 未名空间站 (Fri Nov 21 01:31:56 2008)

i don't know if there is a closed-form expression, but here is what i got from inclusion-exclusion principle:

\sum_{i=0}^{d'} (-1)^i*C(d',i)*(d'-i)^d

where C(m,n)=m!/[n!(m-n)!] is the binomial coefficient.

----- ----- ----- ----- -----
the sum could be simplified as d'!*S(d,d'), where S(n,k) is the Stirling number of the second kind:
http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html
Eq.(10)
--
※ 修改:·pcasnik 於 Feb 17 13:43:48 2009 修改本文·[FROM: 75.34.]

发信人: although (.....but), 信区: BrainTeaser
标 题: Re: 问个排列组合的问题
发信站: BBS 未名空间站 (Fri Nov 21 01:48:27 2008)

thanks, how do you get that? I cant follow...

【 在 pcasnik (pcasnik) 的大作中提到: 】
: i don't know if there is a closed-form expression, but here is what i got
from inclusion-exclusion principle:
: \sum_{i=0}^{d'} (-1)^i*C(d',i)*(d'-i)^d
: where C(m,n)=m!/[n!(m-n)!] is the binomial coefficient.




--
※ 修改:·although 於 Nov 21 02:05:39 2008 修改本文·[FROM: 128.197.]

发信人: pcasnik (pcasnik), 信区: BrainTeaser
标 题: Re: 问个排列组合的问题
发信站: BBS 未名空间站 (Fri Nov 21 02:33:38 2008)

sure.

we first calculate the number of combinations with at least one box is empty.

apply inclusion-exclusion principle:
http://en.wikipedia.org/wiki/Inclusion-exclusion_principle
with set A_i indicating i-th box is empty. i will follow the wikipedia notation.

for |A_i|, i-th box is empty, so each ball has the other (d'-1) boxes to go into, which gives (d'-1)^d combination. there are total of C(d',1) terms, hence the first sum is C(d',1)*(d'-1)^d;

now |intersection of A_i and A_j|: C(d',2) terms, and each term is (d'-2)^d, cause each ball has (d-2) boxes to go;

so on and so forth to get all the sums...

now sum up these sums(:P, of course with the (-1)^i factor) and you need to subtract it from the total number of combinations without the constraint that every box has to contain one ball. since the total is (d')^d combination (because each ball has d' boxes to go into), this gives the sum i wrote above.

the problem would be much easier if the balls are not labeled, but that's not what we get here...


--
※ 修改:·pcasnik 於 Nov 21 02:54:37 2008 修改本文·[FROM: 75.34.]

发信人: although (.....but), 信区: BrainTeaser
标 题: Re: 问个排列组合的问题
发信站: BBS 未名空间站 (Fri Nov 21 02:53:27 2008)

Got it. Thank you so much^_^

【 在 pcasnik (pcasnik) 的大作中提到: 】
: sure.
: we first calculate the number of combinations with at least one box is
empty.
: apply inclusion-exclusion principle:
: http://en.wikipedia.org/wiki/Inclusion-exclusion_principle
: with set A_i indicating i-th box is empty. i will follow the wikipedia
notation.
: for |A_i|, i-th box is empty, so each ball has the other (d'-1) boxes to
go into, which gives (d'-1)^d combination. there are total of C(d',1) terms,
hence the first sum is C(d',1)*(d'-1)^d;
: now |intersection of A_i and A_j|: C(d',2) terms, and each term is (d'-2)^
d, cause each ball has (d-2) boxes to go;
: so on and so forth to get all the sums...
: now sum up these sums:P and you need to subtract it from the total number
of combinations without the constraint that every box has to contain one
ball. since the total is (d')^d combination (because each ball has d' boxes
to go into), this gives the sum i wrote above.
: the problem would be much easier if the balls are not labeled, but that's
not what we get here...



--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 24.91.]

发信人: hero080 (APM=080), 信区: BrainTeaser
标 题: Re: 问个排列组合的问题
发信站: BBS 未名空间站 (Fri Nov 21 23:20:11 2008), 转信

d个球有d+1个间隙，从中间选出d'个，为：
{d+1 \choose d'}

【 在 although (.....but) 的大作中提到: 】
: 高中的表弟问我的，我想不出来呀。。。
: 有d 个球（球是有编号的），d'个箱子 （d' <= d），将球随机扔到箱子里，要求每个
: 箱子里至少有一个球，这样的组合一共有多少个？


--
╱╲
╠┃║﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍
瞳凝秋水剑流星，裁诗为骨玉为神? ╱╤╤╝┃ _____________________________╲
翩翩白衣云端客，生死为谁一掷轻? ╲╧╧╗┃ ╱
╠┃║﹉﹉﹉﹉﹉﹉﹉﹉﹉﹉﹉﹉﹉﹉﹉
╲╱



※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 76.254.]

发信人: SuperString (阳阳加油), 信区: BrainTeaser
标 题: Re: 问个排列组合的问题
发信站: BBS 未名空间站 (Fri Nov 21 23:27:17 2008), 转信


球有编号

【 在 hero080 (APM=080) 的大作中提到: 】
: d个球有d+1个间隙，从中间选出d'个，为：
: {d+1 \choose d'}



--

※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 69.143.]

发信人: hero080 (APM=080), 信区: BrainTeaser
标 题: Re: 问个排列组合的问题
发信站: BBS 未名空间站 (Sat Nov 22 02:13:45 2008), 转信

好吧……
【 在 SuperString (阳阳加油) 的大作中提到: 】
: 球有编号


--
╱╲
╠┃║﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍
瞳凝秋水剑流星，裁诗为骨玉为神? ╱╤╤╝┃ _____________________________╲
翩翩白衣云端客，生死为谁一掷轻? ╲╧╧╗┃ ╱
╠┃║﹉﹉﹉﹉﹉﹉﹉﹉﹉﹉﹉﹉﹉﹉﹉
╲╱



※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 76.254.]

发信人: sceptre (sceptre), 信区: BrainTeaser
标 题: Re: 问个排列组合的问题
发信站: BBS 未名空间站 (Thu Nov 27 19:31:39 2008)

Let me propose my answer:

P(d,d') * d' ^ (d-d')

first, choose d' from d to fill all the boxes. it's P(d,d')=d!/(d-d')!.

second, throw the rest (d-d') to the d' boxes randomly.


--
※ 修改:·sceptre 於 Nov 27 19:31:59 2008 修改本文·[FROM: 136.142.]

发信人: SuperString (阳阳加油), 信区: BrainTeaser
标 题: Re: 问个排列组合的问题
发信站: BBS 未名空间站 (Thu Nov 27 23:19:29 2008), 转信


this will overcount.

For instance:

1)
a is among the first d' balls and put in box c
b is among the remaining (d-d') balls and put in box c

or
2)
b is among the first d' balls and put in box c
a is among the remaining (d-d') balls and put in box c

1) and 2) lead to the same result and should be counted as 1.
In your solution, they are counted twice.

【 在 sceptre (sceptre) 的大作中提到: 】
: Let me propose my answer:
: P(d,d') * d' ^ (d-d')
: first, choose d' from d to fill all the boxes. it's P(d,d')=d!/(d-d')!.
: second, throw the rest (d-d') to the d' boxes randomly.


--



好春光，不如梦一场
梦里青草香。



※ 修改:·SuperString 于 Nov 27 23:20:39 修改本文·[FROM: 69.143.]
※ 来源:·BBS 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 69.143.]

发信人: sceptre (sceptre), 信区: BrainTeaser
标 题: Re: 问个排列组合的问题
发信站: BBS 未名空间站 (Thu Nov 27 23:35:37 2008)

这可如何是好啊

【 在 SuperString (阳阳加油) 的大作中提到: 】
: this will overcount.
: For instance:
: 1)
: a is among the first d' balls and put in box c
: b is among the remaining (d-d') balls and put in box c
: or
: 2)
: b is among the first d' balls and put in box c
: a is among the remaining (d-d') balls and put in box c
: 1) and 2) lead to the same result and should be counted as 1.
: ...................




--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 136.142.]

发信人: jackyOxy (jackyOxy), 信区: BrainTeaser
标 题: Re: 问个排列组合的问题
发信站: BBS 未名空间站 (Thu Jan 8 15:08:32 2009)

我的答案： d-1个空，随便选出d'-1个空

--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 128.210.]

发信人: pcasnik (pcasnik), 信区: BrainTeaser
标 题: Re: 问个排列组合的问题
发信站: BBS 未名空间站 (Sun Jan 11 14:00:56 2009)

【 在 jackyOxy (jackyOxy) 的大作中提到: 】
: 我的答案： d-1个空，随便选出d'-1个空

consider the simple case when d=d'. you answer results 1, which is not correct.
e.g., two boxes with two balls, there are two ways.
--
※ 修改:·pcasnik 於 Jan 11 14:01:26 2009 修改本文·[FROM: 75.34.]