Combinatorics group question?

  • Thread starter Gridvvk
  • Start date
  • #1
56
1

Main Question or Discussion Point

Let's say you have a group of 22 people, which you would like to break into 5 different groups -- 3 groups of 4 and 2 groups of 5. How many distinct ways can you form such groups?

I don't want to double count groups. Let's say I number the people from A - V. The group ABCDE and ACDBE should be considered the same group since they have the same elements.

I imagine the numerator is
[(22 choose 4)(18 choose 4)(14 choose 4)(10 choose 5)(5 choose 5) ]

I'm not sure what to divide by to get rid of counting extras.
 

Answers and Replies

  • #2
pbuk
Science Advisor
Gold Member
1,373
372
Order the 5 bins, and order each position in each bin; there are then clearly 22! permutations. The items in the first 3 bins can be ordered 4! different ways and the items in the last 2 bins can be ordered 5! different ways, so there are a total of 4!4!4!5!5! orderings within bins.

It is not clear whether {ABCD, EFGH, ...} and {EFGH, ABCD, ...} are to be considered the same: if so, you need to reduce further by a factor of 3!2!.
 
Last edited:
  • #3
pbuk
Science Advisor
Gold Member
1,373
372
Observe that the familiar forumula for combinations ## \frac{n!}{k!(n-k)!} ## is derived in the same way where there are n objects and 2 bins containing k and n-k objects respectively, but when we use this we are not generally interested in the contents of the second bin.
 
  • #4
56
1
Thank you. I wanted combinations not permutations though. So my first term would be [(22 choose 4)(18 choose 4)(14 choose 4)(10 choose 5)(5 choose 5) ]. If I understand correctly, then the inner ordering within the groups is already taken care of by the combination formula (dividing by k!). I did want to consider {ABCD, EFGH, ...} and {EFGH, ABCD, ...} to be the same, so I would divide by a factor of 3! 2! because I have 3 groups of size 4 and 2 groups of size 5. The 3! and 2! term are coming from the number of groups, not the sizes.

So the question:
How many ways to divide group of 22 people into 3 groups of 4 people and 2 groups of 5 people?

has the answer:
[(22 choose 4)(18 choose 4)(14 choose 4)(10 choose 5)(5 choose 5) ] / (3! * 2!) =
470531961900.
 
  • #5
pbuk
Science Advisor
Gold Member
1,373
372
Thank you. I wanted combinations not permutations though. So my first term would be [(22 choose 4)(18 choose 4)(14 choose 4)(10 choose 5)(5 choose 5) ]. If I understand correctly, then the inner ordering within the groups is already taken care of by the combination formula (dividing by k!). I did want to consider {ABCD, EFGH, ...} and {EFGH, ABCD, ...} to be the same, so I would divide by a factor of 3! 2! because I have 3 groups of size 4 and 2 groups of size 5. The 3! and 2! term are coming from the number of groups, not the sizes.

So the question:
How many ways to divide group of 22 people into 3 groups of 4 people and 2 groups of 5 people?

has the answer:
[(22 choose 4)(18 choose 4)(14 choose 4)(10 choose 5)(5 choose 5) ] / (3! * 2!) =
470531961900.
I have given you combinations, we get the same answer.

Note that a number of terms can be cancelled from the expression you gave to arrive at the expression I gave: [tex]\frac{22!}{4!18!}.\frac{18!}{4!14!}.\frac{14!}{4!10!}.\frac{10!}{5!5!}.\frac{5!}{5!0!}.\frac{1}{3!2!} = \frac{22!}{4!^35!^2}.\frac{1}{3!2!}[/tex]
 
  • Like
Likes 1 person
  • #6
56
1
Right, that eases the computation. Thanks a lot for the help!
 

Related Threads on Combinatorics group question?

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
Replies
22
Views
1K
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
4
Views
773
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
3
Views
2K
Top