g***a
发帖数: 114 | 1 Nine different gifts distributed to four children, how many ways such that
each child has at least one gift.
This answer is easy if the gifts are the same, which is C(9-1, 4-1) = 56.
I am not sure about the case of different gifts.
Here is what I think: total No. of ways is 4^9.
The No. of ways that at most three children has gifts is
C(4,3)3^9.
Therefore, the No. of ways each child has at least gifts is
4^9 - C(4,3)3^9.
However, I saw some answer as
4^9 - C(4,3)3^9 + C(4,2)2^9 - C(4,1)
Any suggestion would be appreciated, thanks! | h**********e
发帖数: 44 | 2 You over count the illegible cases with two children without gift in C(4,3)3
^9, so you need to add it back. This is like the wrong envelop problem. | w**********9
发帖数: 5 | 3 using exclusion and inclusion method.
【在 g***a 的大作中提到】
: Nine different gifts distributed to four children, how many ways such that
: each child has at least one gift.
: This answer is easy if the gifts are the same, which is C(9-1, 4-1) = 56.
: I am not sure about the case of different gifts.
: Here is what I think: total No. of ways is 4^9.
: The No. of ways that at most three children has gifts is
: C(4,3)3^9.
: Therefore, the No. of ways each child has at least gifts is
: 4^9 - C(4,3)3^9.
: However, I saw some answer as
| x**4
发帖数: 19 | 4 My thoughts:
Step 1: select 4 gifts from 9 to ensure that each child will get a gift.
C(9,4)
Step 2: the remaining 5 gifts could be handed out to any child.
4^5
The total should be C(9,4)*4^5.
Please correct me if I am wrong. Thx. | g***a
发帖数: 114 | 5 I am LZ, thanks for all your help.
Now I think I have figured out where I am wrong.
Suppose N1 N2 N3 N4 is the number of ways that 1st, 2nd, 3rd, 4th
children that does not have gifts, then
N1 U N2 U N3 U N4 = C(4,1)3^9 - C(4,2)2^9 + C(4,1)
The total number of ways that each child has at least one gift
is
4^9 - C(4,1)3^9 + C(4,2)2^9 - C(4,1) | g******i
发帖数: 251 | 6
你这个有误，3^9中含3个中有人没有礼物的情况，同理2^9也有这样的情况，所以你的
答案小了。我觉得答案应该是：
C（9，4）4！4^5
★ 发自iPhone App: ChineseWeb 7.5
【在 g***a 的大作中提到】
: I am LZ, thanks for all your help.
: Now I think I have figured out where I am wrong.
: Suppose N1 N2 N3 N4 is the number of ways that 1st, 2nd, 3rd, 4th
: children that does not have gifts, then
: N1 U N2 U N3 U N4 = C(4,1)3^9 - C(4,2)2^9 + C(4,1)
: The total number of ways that each child has at least one gift
: is
: 4^9 - C(4,1)3^9 + C(4,2)2^9 - C(4,1)
| m***w
发帖数: 404 | | m***9
发帖数: 1671 | 8 思路对，可是第一步的时候由于4个礼物不同，应该是A（9,4），也就是C(9,4)*4!
【在 x**4 的大作中提到】
: My thoughts:
: Step 1: select 4 gifts from 9 to ensure that each child will get a gift.
: C(9,4)
: Step 2: the remaining 5 gifts could be handed out to any child.
: 4^5
: The total should be C(9,4)*4^5.
: Please correct me if I am wrong. Thx.
| f*******3
发帖数: 577 | 9 同一个篮子里面多个球会over-counting吧
【在 m***9 的大作中提到】
: 思路对，可是第一步的时候由于4个礼物不同，应该是A（9,4），也就是C(9,4)*4!
|
|
