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

Simple Counting

  1. Oct 12, 2005 #1
    Suppose I pick two number from {0,1,2} without replacement and suppose I keep track of which one was drawn first. This is a permutation question.
    There are 3!/(3-2)! = 6 possible permutations:

    (0,1)
    (0,2)
    (1,0)
    (1,2)
    (2,0)
    (2,1)

    Of course, if I only care which numbers were choosen, then I care about combinations.
    THere are 3!/(3-2)!/2! = 3 possible combinations.

    (0,1)
    (0,2)
    (1,2)

    All very basic....
    Now, I ask the same question with replacement. Now, the drawings are independent. 3^2 = 9

    (0,0)
    (0,1)
    (0,2)
    (1,0)
    (1,1)
    (1,2)
    (2,0)
    (2,1)
    (2,2)

    Suppose I don't care about permutations. That is to say, I just want to know what numbers were picked with replacement.

    (0,0)
    (0,1)
    (0,2)
    (1,1)
    (1,2)
    (2,2)

    Now there are only six combinations possible. How do I get this number? The same thing in terms of head/tails:

    00
    01
    10
    11

    4 possibilities when we care about order, but only 3 when we do not since 01 is 10. I know this must be very simple, but I don't know the formula. I am asking: If I flip a coin twice, what is the number of "unique" outcomes. It is easy with a coin....the number is always associated with the total number of possible heads (or tails)...which is always 0 to n. But how do I do this in general if there are more choices.

    If I draw k items from a set of n items with replacement, then how many different combinations (not permutations) are possible?
     
  2. jcsd
  3. Oct 12, 2005 #2

    honestrosewater

    User Avatar
    Gold Member

    I'm not sure what you're looking for, but do you see what set of pairs is left if you remove all (x, x) from
    ? Maybe you want nCk + n?
     
  4. Oct 12, 2005 #3
    Removing all (x,x) does not work in the general case. Below is another example. Suppose I am base 3 and I make three selections with replacement. Then there are 3^3 possible sets. I list them below.

    000
    001
    002
    010
    011
    012
    020
    021
    022
    100
    101
    102
    110
    111
    112
    120
    121
    122
    200
    201
    202
    210
    211
    212
    220
    221
    222

    In this set, I want to remove any outcome that is a permutation of another outcome. For example, I do not want 212 and 122 and 221. These outcomes are merely permutations. So the final sets should be:

    000
    001
    002
    011
    012
    022
    111
    112
    122
    222

    There are only 10 sets. I'm trying to deal with indistinguishable combinations. So, 001 is exactly the same as 100 and 010.

    So how do I generate the number 10? I need a general formula.
     
  5. Oct 12, 2005 #4

    honestrosewater

    User Avatar
    Gold Member

    nCk + n1 works for n = 3 and k = 2, right? Does it work for k = 2 and any n?

    What changes when n = 3 and k = 3? Start with the combinations. You then want to add all (x, x, y) - x and y not necessarily distinct. x can take 3 values, and for each of those, y can take 3 values. Does that work?

    Actually, sorry, perhaps I shouldn't have said anything because I don't know the answer. Someone else may already know and can offer more help.
     
    Last edited: Oct 12, 2005
  6. Oct 12, 2005 #5
    Anyone?

    I am looking for the number of combinations if I make n selections from k objects with replacements. Reptitions are acceptable, permutations are not important.

    So, if I select from 2 times from the objects {0,1} these are the combinations I care about:

    00
    01
    11

    Notice, 10 is not present in this list as it is equivalent to 01.

    Thanks again.
     
  7. Oct 13, 2005 #6
    (k+n-1)!/(k-1)!n! that is (k+n-1)Cn
    You can show this by putting the list in order x1, x2 ...xn and replacing each xi with xi+i-1. This gives a 1-1 correspondence between such lists and combinations of n choices from the set {1.. (k+n-1)}
     
  8. Oct 13, 2005 #7
    That's it! And that is a very well-known result too. For some reason, I had convinced myself that it had to be different from that.

    Thanks.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Simple Counting
  1. Counting Problems (Replies: 2)

  2. Counting Principle (Replies: 4)

Loading...