Finding Combinations with Replacement: k from n

[ghotra]

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?

 

[honestrosewater]

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

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

? Maybe you want nCk + n?

 

[ghotra]

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.

 

[honestrosewater]

nCk + n¹ 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.

 

[ghotra]

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.

 

[chronon]

(k+n-1)!/(k-1)!n! that is _(k+n-1)C_n
You can show this by putting the list in order x₁, x₂ ...x_n and replacing each x_i with x_i+i-1. This gives a 1-1 correspondence between such lists and combinations of n choices from the set {1.. (k+n-1)}

 

[ghotra]

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.