Clarification needed on combinatorics problem

This topic has expert replies
User avatar
Legendary Member
Posts: 504
Joined: Tue Apr 19, 2011 1:40 pm
Thanked: 114 times
Followed by:11 members
In how many ways can 16 different gifts be divided among four children such that each child receives exactly four gifts?

OA [spoiler]16! ÷ (4!)^4[/spoiler]


I already got the answer by doing 16C4 * 12C4 * 8C4 * 4C4

My question is, since the four children are NOT identical, shouldn't the above calculation also have a 4C1*3C1*2C1 in there? Considering the four children are NOT identical, we would need to pick one kid each time we need to assign a kid an assortment of four gifts, don't we?

Detailed explanations would be appreciated. Many thanks in advance.

User avatar
GMAT Instructor
Posts: 15539
Joined: Tue May 25, 2010 12:04 pm
Location: New York, NY
Thanked: 13060 times
Followed by:1906 members
GMAT Score:790

by GMATGuruNY » Fri Nov 21, 2014 10:14 am
knight247 wrote:In how many ways can 16 different gifts be divided among four children such that each child receives exactly four gifts?

I already got the answer by doing 16C4 * 12C4 * 8C4 * 4C4.
Your solution is correct.
Let the four children be Adam, Bobby, Cindy and David.
From 16 gifts, the number of ways to choose 4 to give to Adam = 16C4.
From the remaining 12 gifts, the number of ways to choose 4 to give to Bobby = 12C4.
From the remaining 8 gifts, the number of ways to choose 4 to give to Cindy = 8C4.
From the remaining 4 gifts, the number of ways to choose 4 to give to David = 4C4.
To combine these options, we multiply:
16C4 * 12C4 * 8C4 * 4C4.
Last edited by GMATGuruNY on Thu Oct 15, 2015 11:11 am, edited 1 time in total.
Private tutor exclusively for the GMAT and GRE, with over 20 years of experience.
Followed here and elsewhere by over 1900 test-takers.
I have worked with students based in the US, Australia, Taiwan, China, Tajikistan, Kuwait, Saudi Arabia -- a long list of countries.
My students have been admitted to HBS, CBS, Tuck, Yale, Stern, Fuqua -- a long list of top programs.

As a tutor, I don't simply teach you how I would approach problems.
I unlock the best way for YOU to solve problems.

For more information, please email me (Mitch Hunt) at [email protected].
Student Review #1
Student Review #2
Student Review #3

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 16207
Joined: Mon Dec 08, 2008 6:26 pm
Location: Vancouver, BC
Thanked: 5254 times
Followed by:1268 members
GMAT Score:770

by Brent@GMATPrepNow » Fri Nov 21, 2014 10:17 am
knight247 wrote:In how many ways can 16 different gifts be divided among four children such that each child receives exactly four gifts?


If we take the task of distributing the 16 gifts and break it into stages, we can see that we need not perform the additional calculations you suggest.

Let's say the children are named A, B, C, and D

Stage 1: Select 4 gifts to give to child A
Since the order in which we select the 4 gifts does not matter, we can use combinations.
We can select 4 gifts from 16 gifts in 16C4 ways (= 16!/(4!)(12!))
So, we can complete stage 1 in 16!/(4!)(12!) ways

Stage 2: select 4 gifts to give to child B
There are now 12 gifts remaining
Since the order in which we select the 4 gifts does not matter, we can use combinations.
We can select 4 gifts from 12 gifts in 12C4 ways (= 12!/(4!)(8!))
So, we can complete stage 2 in 12!/(4!)(8!) ways


Stage 3: select 4 gifts to give to child C
There are now 8 gifts remaining
We can select 4 gifts from 8 gifts in 8C4 ways (= 8!/(4!)(4!))
So, we can complete stage 3 in 8!/(4!)(4!) ways

Stage 4: select 4 gifts to give to child C
There are now 4 gifts remaining
NOTE: There's only 1 way to select 4 gifts from 4 gifts, but if we want the answer to look like the official answer, let's do the following:
We can select 4 gifts from 4 gifts in 4C4 ways (= 4!/4!)
So, we can complete stage 4 in 4!/4! ways

By the Fundamental Counting Principle (FCP), we can complete all 4 stages (and thus distribute all 16 gifts) in [16!/(4!)(12!)][12!/(4!)(8!)][8!/(4!)(4!)][4!/4!] ways

A BUNCH of terms cancel out to give us ([spoiler]= 16!/(4!)�[/spoiler])

--------------------------

Note: the FCP can be used to solve the MAJORITY of counting questions on the GMAT. For more information about the FCP, watch our free video: https://www.gmatprepnow.com/module/gmat-counting?id=775

Then you can try solving the following questions:

EASY
- https://www.beatthegmat.com/what-should- ... 67256.html
- https://www.beatthegmat.com/counting-pro ... 44302.html
- https://www.beatthegmat.com/picking-a-5- ... 73110.html
- https://www.beatthegmat.com/permutation- ... 57412.html
- https://www.beatthegmat.com/simple-one-t270061.html
- https://www.beatthegmat.com/mouse-pellets-t274303.html


MEDIUM
- https://www.beatthegmat.com/combinatoric ... 73194.html
- https://www.beatthegmat.com/arabian-hors ... 50703.html
- https://www.beatthegmat.com/sub-sets-pro ... 73337.html
- https://www.beatthegmat.com/combinatoric ... 73180.html
- https://www.beatthegmat.com/digits-numbers-t270127.html
- https://www.beatthegmat.com/doubt-on-sep ... 71047.html
- https://www.beatthegmat.com/combinatoric ... 67079.html


DIFFICULT
- https://www.beatthegmat.com/wonderful-p- ... 71001.html
- https://www.beatthegmat.com/ps-counting-t273659.html
- https://www.beatthegmat.com/permutation- ... 73915.html
- https://www.beatthegmat.com/please-solve ... 71499.html
- https://www.beatthegmat.com/no-two-ladie ... 75661.html
- https://www.beatthegmat.com/laniera-s-co ... 15764.html

Cheers,
Brent
Brent Hanneson - Creator of GMATPrepNow.com
Image

Senior | Next Rank: 100 Posts
Posts: 64
Joined: Wed Dec 08, 2010 10:55 pm
Thanked: 1 times

by prada » Thu Oct 15, 2015 11:01 am
GMATGuruNY wrote:
knight247 wrote:In how many ways can 16 different gifts be divided among four children such that each child receives exactly four gifts?

I already got the answer by doing 16C4 * 12C4 * 8C4 * 4C4.
Your solution is correct.
Let the four children be Adam, Bobby, Cindy and David.
From 16 gifts, the number of ways to choose 4 to give to Adam = 16C4.
From the remaining 12 gifts, the number of ways to choose 4 to give to Bobby = 12C4.
From the remaining 8 gifts, the number of ways to choose 4 to give to Cindy = 8C4.
From the remaining 4 gifts, the number of ways to choose 4 to give to David = 4C4.
To combine these options, we multiply:
16C4 * 12C5 * 8C4 * 4C4.
Hey Mitch on your last line I believe you mean 12C4 and not 12C5?

User avatar
GMAT Instructor
Posts: 15539
Joined: Tue May 25, 2010 12:04 pm
Location: New York, NY
Thanked: 13060 times
Followed by:1906 members
GMAT Score:790

by GMATGuruNY » Thu Oct 15, 2015 11:14 am
prada wrote: Hey Mitch on your last line I believe you mean 12C4 and not 12C5?
Thanks for pointing out the typo.
I've amended my solution accordingly.
Private tutor exclusively for the GMAT and GRE, with over 20 years of experience.
Followed here and elsewhere by over 1900 test-takers.
I have worked with students based in the US, Australia, Taiwan, China, Tajikistan, Kuwait, Saudi Arabia -- a long list of countries.
My students have been admitted to HBS, CBS, Tuck, Yale, Stern, Fuqua -- a long list of top programs.

As a tutor, I don't simply teach you how I would approach problems.
I unlock the best way for YOU to solve problems.

For more information, please email me (Mitch Hunt) at [email protected].
Student Review #1
Student Review #2
Student Review #3

User avatar
Newbie | Next Rank: 10 Posts
Posts: 2
Joined: Sun Jan 31, 2016 10:32 pm

by Dutta » Mon Feb 08, 2016 9:54 am
Hey Brent,

Since the 4 kids are not identical should we not consider selecting as to who receives the 1st set of 4 gifts and who the 2nd and so on. So shouldn't the ans be multiplied by a 4!?

Brent@GMATPrepNow wrote:
knight247 wrote:In how many ways can 16 different gifts be divided among four children such that each child receives exactly four gifts?


If we take the task of distributing the 16 gifts and break it into stages, we can see that we need not perform the additional calculations you suggest.

Let's say the children are named A, B, C, and D

Stage 1: Select 4 gifts to give to child A
Since the order in which we select the 4 gifts does not matter, we can use combinations.
We can select 4 gifts from 16 gifts in 16C4 ways (= 16!/(4!)(12!))
So, we can complete stage 1 in 16!/(4!)(12!) ways

Stage 2: select 4 gifts to give to child B
There are now 12 gifts remaining
Since the order in which we select the 4 gifts does not matter, we can use combinations.
We can select 4 gifts from 12 gifts in 12C4 ways (= 12!/(4!)(8!))
So, we can complete stage 2 in 12!/(4!)(8!) ways


Stage 3: select 4 gifts to give to child C
There are now 8 gifts remaining
We can select 4 gifts from 8 gifts in 8C4 ways (= 8!/(4!)(4!))
So, we can complete stage 3 in 8!/(4!)(4!) ways

Stage 4: select 4 gifts to give to child C
There are now 4 gifts remaining
NOTE: There's only 1 way to select 4 gifts from 4 gifts, but if we want the answer to look like the official answer, let's do the following:
We can select 4 gifts from 4 gifts in 4C4 ways (= 4!/4!)
So, we can complete stage 4 in 4!/4! ways

By the Fundamental Counting Principle (FCP), we can complete all 4 stages (and thus distribute all 16 gifts) in [16!/(4!)(12!)][12!/(4!)(8!)][8!/(4!)(4!)][4!/4!] ways

A BUNCH of terms cancel out to give us ([spoiler]= 16!/(4!)�[/spoiler])

--------------------------

Note: the FCP can be used to solve the MAJORITY of counting questions on the GMAT. For more information about the FCP, watch our free video: https://www.gmatprepnow.com/module/gmat-counting?id=775

Then you can try solving the following questions:

EASY
- https://www.beatthegmat.com/what-should- ... 67256.html
- https://www.beatthegmat.com/counting-pro ... 44302.html
- https://www.beatthegmat.com/picking-a-5- ... 73110.html
- https://www.beatthegmat.com/permutation- ... 57412.html
- https://www.beatthegmat.com/simple-one-t270061.html
- https://www.beatthegmat.com/mouse-pellets-t274303.html


MEDIUM
- https://www.beatthegmat.com/combinatoric ... 73194.html
- https://www.beatthegmat.com/arabian-hors ... 50703.html
- https://www.beatthegmat.com/sub-sets-pro ... 73337.html
- https://www.beatthegmat.com/combinatoric ... 73180.html
- https://www.beatthegmat.com/digits-numbers-t270127.html
- https://www.beatthegmat.com/doubt-on-sep ... 71047.html
- https://www.beatthegmat.com/combinatoric ... 67079.html


DIFFICULT
- https://www.beatthegmat.com/wonderful-p- ... 71001.html
- https://www.beatthegmat.com/ps-counting-t273659.html
- https://www.beatthegmat.com/permutation- ... 73915.html
- https://www.beatthegmat.com/please-solve ... 71499.html
- https://www.beatthegmat.com/no-two-ladie ... 75661.html
- https://www.beatthegmat.com/laniera-s-co ... 15764.html

Cheers,
Brent

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 16207
Joined: Mon Dec 08, 2008 6:26 pm
Location: Vancouver, BC
Thanked: 5254 times
Followed by:1268 members
GMAT Score:770

by Brent@GMATPrepNow » Mon Feb 08, 2016 1:50 pm
Dutta wrote:Hey Brent,

Since the 4 kids are not identical should we not consider selecting as to who receives the 1st set of 4 gifts and who the 2nd and so on. So shouldn't the ans be multiplied by a 4!?
We have already accounted for the children being non-identical.
At each stage, we give gifts to a particular child (child A, B, C and D)

Cheers,
Brent
Brent Hanneson - Creator of GMATPrepNow.com
Image