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

A little combinatorics help please

  1. May 20, 2008 #1
    Say you have 5 regular die, how many permutations are possible if permutations such as 1,1,1,1,2 and 1,2,1,1,1 are not unique but considered the same (ordering doesn't matter)? I haven't done any combinatorics work in almost 6 years, so I am completely rusty on counting problems. No this, isn't homework, I graduated 2 years ago, I am just trying to help out a college friend of mine who is a computer programmer.
  2. jcsd
  3. May 20, 2008 #2


    User Avatar
    Homework Helper

    A permutation where ordering doesn't matter is just a 'combination'

    To choose k objects from n, without respect to order, there are

    [tex]_{n}C_k = \frac{n!}{k!(n-k)!}[/tex]

    ways to do it. (Where 'n C k' is just a symbol for the number of combinations)

    See wikipedia for more: http://en.wikipedia.org/wiki/Combination
    Last edited: May 20, 2008
  4. May 20, 2008 #3
    But for a combination, according to wiki, 'the elements of the combination can not be repeated'. This is what makes this problem harder, because you are allowed to have repitition for example 1,1,1,1,1 is one combination as well as 1,1,1,1,2=1,1,1,2,1=1,1,2,1,1=1,2,1,1,1=2,1,1,1,1 etc.

    So I have the set {1,2,3,4,5,6} and must choose 5 times from it. Repetition is allowed and ordering doesn't matter.
  5. May 20, 2008 #4


    User Avatar

    Two sequences are equal if they have the same amount of each number. Consider the rolls
    If we let a star represent each die roll and separate each 1,2,3,4,5,6 by a bar.
    *|*|*|*|*| represents the first roll
    *|*|**|*|| represents the second, and
    |*|*|*|*|* represents the third.

    There are then 10 total spots to arrange the 5 bars and 5 stars.
    _ _ _ _ _ _ _ _ _ _
    If we leave the spots where the we place the bars as blank spots, the problem reduces to the number of ways to arrange 5 bars in 10 spots or C(10,5)
    Last edited: May 20, 2008
  6. May 20, 2008 #5
    Hey that's a pretty neat way of thinking about it! Thanks.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook