Combinations - order doesn't matter, repetitions allowed

  1. I'm trying to figure out the formula I need...


    ok, say that r=5, so there are 5 items {A,B,C,D,E}
    And we want to chose 5 of those
    Order doesn't matter, repitions allowed


    so for example {A,A,A,B,B} is a feasible solution
    {A,B,C,D,E} is feasible

    so on

    But the formula (n+r-1)!/r!(n-1)! doesn't work because here n=r so it becomes (2n-1)!/(2n-1)! = 1.



    Also, what happens when I want to put certain restrictions. Like for example, say I want an example of the above format with the exception that A and B can only be chosen if C is chosen. I know I would just find all those infeasible solutions and subtract them but I have a hard time finding those infeasibles. I mean, that situation seems obviosu but what if it has to do with ranking. Like say, A chosen --> B,C,D,E, are chosen. B chosen --> C,D,E chosen. D chosen --> E chosen. So what if there are n such rules. Do I make a case for each individually?


    I suck at these stupid things
     
  2. jcsd
  3. Simon Bridge

    Simon Bridge 14,924
    Science Advisor
    Homework Helper
    Gold Member

    You want John Allen Paulos: Innumeracy ... no really: he has a good guide to handling these things using a simple multiplication rule.
    It'll be in a library near you.

    You have 5 slots, which can each have one of 5 possible entries.
    Thats 5x5x5x5x5 possible combinations.

    For the restrictions, you do pretty much have to work out the possible combinations with the forbidden configuration and subtract them off. Just go systematically. It takes practise.
     
    Last edited: Nov 14, 2011

  4. Sorry about that... complete brain fail on my part!!


    sorry but i'm confused about how it would be 5X5X5X5X5


    I'm talking about a situation where the order is irrelevant and permutations can occur


    thanks for the reply btw
     
  5. Stephen Tashi

    Stephen Tashi 4,342
    Science Advisor
    2014 Award

    I don't think "permutations can occur" is the right phrase.

    I think an example of what you are asking is this:

    If we multiply out the expression [itex] (A + B + C + D + E)^5 [/itex] and combine like terms, how many distinct types of terms will there be? For example [itex] AB^2C^2 [/itex] and [itex] C^2A B^2 [/itex] are like terms. [itex] AB^2C^2 [/itex] and [itex] A^2B^2C [/itex] are unlike terms.

    So you are asking about the number of different types of terms, not about the numerical coefficients of the various types of terms.
     
  6. I apologize, I completely misspoke. I meant to say "repetitions can occur" I mix up similar sounding words like that all the time and don't realize it.


    THe only reason I was confused about the 5X5X5X5X5 thing was because that formula (n+r-1)!/r!(n-1)! I thought was specifically used for that situation (given n items, you want to chose r so that repetitions can occur and order is irrelevant)
     
  7. Simon Bridge

    Simon Bridge 14,924
    Science Advisor
    Homework Helper
    Gold Member

    Imagine it was only 2 slots.
    You can do that right?
    Order doesn't matter, and repititions are allowed, so {AB, AA, BA} is three combinations.
    You get a total of 5x5=25 possible combinations.

    If you could not get doubles, then it would be 5x4=20 combinations - since whichever of the 5 get the first slot will leave only 4 for the second.

    Now extrapolate to 5 slots.
     
  8. i see what you are saying, but it seems like by that logic order should matter.


    The example you were giving with 2 slots, it seemed like the goal is: there are 5 objects {A,B,C,D,E} and 2 slots.


    So you were saying there are 5X5 possibilities. But then that would include for example both AB and BA, but I'm talking about order being irrelevant so only one could be included
     
  9. micromass

    micromass 18,700
    Staff Emeritus
    Science Advisor
    Education Advisor

    This is one of more difficult combinatorial problems... Here is how you solve it:

    Let's first introduce a notation. I write

    | all the A's | all the B's | all the C's | all the D's | all the E's |

    So for example, (A,A,A,B,C) is written as

    |AAA|B|C|||

    and (A,C,D,E,E) is

    |A||C|D|EE|

    But we can simplify this notation!! Indeed, under this notation, we don't have to write the A, B, etc. anymore. So I know that

    |.|||....|.|

    represents (A,D,D,D,D).

    So right now we have 11 spots: ........... and we want choose 6 spots where to put |. Under the constraints that the first and the last symbol are |.

    So (disregarding the firsst and last symbol): we have 9 spots, and we want to choose 4 spots where to put |
    Every choice of spots will induce uniquely one of the permutations you want.

    So we see that [itex]\binom{9}{4}[/itex] is the required probability.
     
  10. thank you all for the responses. It cleared up the issue!
     
  11. cepheid

    cepheid 5,194
    Staff Emeritus
    Science Advisor
    Gold Member

    Am I the only one who thinks the OP had the right equation for combination with repetition in the first place, and was just using it wrong?

    If I start with (n+r-1)! / (r!(n-1)!)

    And I plug in n=r=5, I get

    (10-1)! / (5! (5-1)!)

    = 9! / (5!4!)

    Which is just "9 choose 4", the exact same thing as micromass derived. Micromass just showed how to derive the combinatorial equation that the OP had in the first place!

    People who were telling him/her that it would be 5^5 were way off. That would be for permuation with repetition rather than combination with repetition. I.e. 5^5 would be true if order mattered, but it doesn't.

    EDIT : I re-read the thread and see that nobody was telling him that the *answer* should be 5^5, it just came up as part of the explanation. I also see that Simon Bridge pointed out the same misuse of the equation as I did. OK.

    EDIT 2: or at least *somebody* pointed it out. It's not clear who, because it's quoted but it doesnt seem to appear in any posts. Unless I am just going crazy.
     
    Last edited: Nov 15, 2011
  12. Simon Bridge

    Simon Bridge 14,924
    Science Advisor
    Homework Helper
    Gold Member

    Ah - that's what I was worried about when I gave that as my example.
    So you want AB and BA to count as one.

    By the example I presented:

    (5x5-5)/2 +5 ; removing the bottom half of the square but keeping the diagonal.

    But you have a more elegant description from the very small one.
     
  13. Simon Bridge

    Simon Bridge 14,924
    Science Advisor
    Homework Helper
    Gold Member

    I did point it out but I think I deleted it in an edit - which may be where you saw it - I thought OP understanding was more important than instruction in putting numbers into equations and didn't want to distract him. I wish I'd thought of micromass' one.

    I'm glad someone pointed it out in the end too :)
     
  14. I like your derivation micromass!

    Here are all 126 = [itex]9 \choose 4[/itex] combinations.

    Note: I've used the notation by micromass.
    Examples:

    Code (Text):

    o|o|o|o|o  means  A | B | C |  D | E  giving the combination  ABCDE
    o|o||oo|o  means  A | B |   | DD | E  giving the combination  ABDDE

     
    Code (Text):

    1    ooooo||||   AAAAA
    2    oooo|o|||   AAAAB
    3    oooo||o||   AAAAC
    4    oooo|||o|   AAAAD
    5    oooo||||o   AAAAE
    6    ooo|oo|||   AAABB
    7    ooo|o|o||   AAABC
    8    ooo|o||o|   AAABD
    9    ooo|o|||o   AAABE
    10   ooo||oo||   AAACC
    11   ooo||o|o|   AAACD
    12   ooo||o||o   AAACE
    13   ooo|||oo|   AAADD
    14   ooo|||o|o   AAADE
    15   ooo||||oo   AAAEE
    16   oo|ooo|||   AABBB
    17   oo|oo|o||   AABBC
    18   oo|oo||o|   AABBD
    19   oo|oo|||o   AABBE
    20   oo|o|oo||   AABCC
    21   oo|o|o|o|   AABCD
    22   oo|o|o||o   AABCE
    23   oo|o||oo|   AABDD
    24   oo|o||o|o   AABDE
    25   oo|o|||oo   AABEE
    26   oo||ooo||   AACCC
    27   oo||oo|o|   AACCD
    28   oo||oo||o   AACCE
    29   oo||o|oo|   AACDD
    30   oo||o|o|o   AACDE
    31   oo||o||oo   AACEE
    32   oo|||ooo|   AADDD
    33   oo|||oo|o   AADDE
    34   oo|||o|oo   AADEE
    35   oo||||ooo   AAEEE
    36   o|oooo|||   ABBBB
    37   o|ooo|o||   ABBBC
    38   o|ooo||o|   ABBBD
    39   o|ooo|||o   ABBBE
    40   o|oo|oo||   ABBCC
    41   o|oo|o|o|   ABBCD
    42   o|oo|o||o   ABBCE
    43   o|oo||oo|   ABBDD
    44   o|oo||o|o   ABBDE
    45   o|oo|||oo   ABBEE
    46   o|o|ooo||   ABCCC
    47   o|o|oo|o|   ABCCD
    48   o|o|oo||o   ABCCE
    49   o|o|o|oo|   ABCDD
    50   o|o|o|o|o   ABCDE
    51   o|o|o||oo   ABCEE
    52   o|o||ooo|   ABDDD
    53   o|o||oo|o   ABDDE
    54   o|o||o|oo   ABDEE
    55   o|o|||ooo   ABEEE
    56   o||oooo||   ACCCC
    57   o||ooo|o|   ACCCD
    58   o||ooo||o   ACCCE
    59   o||oo|oo|   ACCDD
    60   o||oo|o|o   ACCDE
    61   o||oo||oo   ACCEE
    62   o||o|ooo|   ACDDD
    63   o||o|oo|o   ACDDE
    64   o||o|o|oo   ACDEE
    65   o||o||ooo   ACEEE
    66   o|||oooo|   ADDDD
    67   o|||ooo|o   ADDDE
    68   o|||oo|oo   ADDEE
    69   o|||o|ooo   ADEEE
    70   o||||oooo   AEEEE
    71   |ooooo|||   BBBBB
    72   |oooo|o||   BBBBC
    73   |oooo||o|   BBBBD
    74   |oooo|||o   BBBBE
    75   |ooo|oo||   BBBCC
    76   |ooo|o|o|   BBBCD
    77   |ooo|o||o   BBBCE
    78   |ooo||oo|   BBBDD
    79   |ooo||o|o   BBBDE
    80   |ooo|||oo   BBBEE
    81   |oo|ooo||   BBCCC
    82   |oo|oo|o|   BBCCD
    83   |oo|oo||o   BBCCE
    84   |oo|o|oo|   BBCDD
    85   |oo|o|o|o   BBCDE
    86   |oo|o||oo   BBCEE
    87   |oo||ooo|   BBDDD
    88   |oo||oo|o   BBDDE
    89   |oo||o|oo   BBDEE
    90   |oo|||ooo   BBEEE
    91   |o|oooo||   BCCCC
    92   |o|ooo|o|   BCCCD
    93   |o|ooo||o   BCCCE
    94   |o|oo|oo|   BCCDD
    95   |o|oo|o|o   BCCDE
    96   |o|oo||oo   BCCEE
    97   |o|o|ooo|   BCDDD
    98   |o|o|oo|o   BCDDE
    99   |o|o|o|oo   BCDEE
    100      |o|o||ooo   BCEEE
    101      |o||oooo|   BDDDD
    102      |o||ooo|o   BDDDE
    103      |o||oo|oo   BDDEE
    104      |o||o|ooo   BDEEE
    105      |o|||oooo   BEEEE
    106      ||ooooo||   CCCCC
    107      ||oooo|o|   CCCCD
    108      ||oooo||o   CCCCE
    109      ||ooo|oo|   CCCDD
    110      ||ooo|o|o   CCCDE
    111      ||ooo||oo   CCCEE
    112      ||oo|ooo|   CCDDD
    113      ||oo|oo|o   CCDDE
    114      ||oo|o|oo   CCDEE
    115      ||oo||ooo   CCEEE
    116      ||o|oooo|   CDDDD
    117      ||o|ooo|o   CDDDE
    118      ||o|oo|oo   CDDEE
    119      ||o|o|ooo   CDEEE
    120      ||o||oooo   CEEEE
    121      |||ooooo|   DDDDD
    122      |||oooo|o   DDDDE
    123      |||ooo|oo   DDDEE
    124      |||oo|ooo   DDEEE
    125      |||o|oooo   DEEEE
    126      ||||ooooo   EEEEE
     
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?