Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics group question?

  1. Sep 16, 2013 #1
    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.
     
  2. jcsd
  3. Sep 17, 2013 #2
    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: Sep 17, 2013
  4. Sep 17, 2013 #3
    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.
     
  5. Sep 17, 2013 #4
    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.
     
  6. Sep 18, 2013 #5
    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]
     
  7. Sep 18, 2013 #6
    Right, that eases the computation. Thanks a lot for the help!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook