Help in Regard to Combinations, Please

R

Rappaccini

Redoubtable
Registered Senior Member
Can someone give me the formula for combinations that include repetition of elements?
I've searched every internet source I can find, but no luck for me, I'm afraid.

The only mathematics text-books I've access to here in my house do not concern counting principle. So that option isn't viable.
 
No No, ah, actually, I believe it's the number of elements raised to the power of how many are to be included in your resulting samples.
 
or is it a permutation? man it's been over five years and I only really had it straight in my head for like two weeks before it turned out i never used it again and forgot the difference. i'd look it up but my probability book is at work.
 
Example, 10 possible elements with repititions counting taken three at a time is ten cubed or 1,000 different possible combinations, 000 through 999.
 
No... I think that you just gave the formula for all possible permutations with repetition included.

Does anyone know the one for combinations WITH repetition?



EDIT:

Nevermind, guys.
I found it.

It's C(n+r-1,r), which expands to

(n+r-1)! / [(n+r-1)-r]! * r!
 
Last edited:
Nope, I do not.


Let me guess...

I won't even write it... I'm listening...


...to the words on the screen. :rolleyes:

EDIT:

I know that

C(n,r) or nCr

= n! / (n-r)! * r!

if that's what you mean.


For some reason, though, I think you're probably a whiz at this, a whiz who's about to explain counting principle to me in excruciating detail.

*Puts on combat uniform*

Bring it.
 
n! = n(n-1)(n-2)...(2)(1) ...[1]
nPr = n(n-1)(n-2)...(n-r+1) r<n...[2]
nPr can also be written in factorial form...

nPr = {n(n-1)(n-2)...(n-r+1)(n-r)...(2)(1)}/(n-r)...(2)(1) this is exactly the same as [1]
nPr = n!/(n-r)!

Now given a set of n distinct elements, an r-combination of the set is an unordered selection of r-elements of the set. The number of these r-combinations is denoted nCr.

We derive the formula for nCr by counting the number of r-permutations of an n-element set by recognising that the number of r-permutations is the product of the number of r-combinations and the number of orderings of r elements. Or nPr = nCr * r!. To show what this means consider the following example:

We have a set of 4 elements X = {a,b,c,d}.
Step 1: Select an r-combination of X.
Step 2: Order it.

So to construct a 2-permuation of X (I chose 2 you can choose 1 , 3 or 4 if you wanted to) we can first select a 2-combination and then order it. (in other words to find 4P2 we can find 4C2 and then multiply it by 2!) Watch...

We know from the above formula that 4P2 = 4*3 = 12.
But 4C2 = 6 because there are six 2-combinations of {a,b,c,d}
{a,b},{a,c},{a,d},{b,a},{b,c},{b,d} This is the whole subset of 2-combinations of X
Note that {c,a} = {a,c} because order does not matter for combinations. The same goes for {c,b},{c,d},{d,a},{d,b}, and {d,c}.

And 2! = 2 (there are two ways that each of the 2-combinations can be arranged. {a,c} = ac or ca.

Hence 4P2 = 4C2 * 2! = 6*2 = 12

Therefore nPr = nCr * r! or rearranging...

nCr = nPr / r!

We know that nPr = n(n-1)(n-2)...(n-r+1) and r! = n(n-1)(n-2)...(2)(1) so

nCr = {n(n-1)(n-2)...(n-r+1)}/{n(n-1)(n-2)...(2)(1)} = n!/(n-r)!r! ...[3]

Another example X = {1,2,3,4,5}

3-combinations include

{1,2,3},{1,3,4},{1,4,5},{1,2,4},{1,2,5},{1,3,5},{2,3,4},{2,4,5},{3,4,5},{2,3,5}

Once again note that say {1,5,4} = {1,4,5} since order does not matter for combinations.

So there are 10 3-combinations of a 5 element set.
And 3! = 6

From this we know that there are 10*6 = 60 3-permutations of a 5-element set, or 5P3 = 60.

If nCr = n!/(n-r)!r! then (n+r-1)Cr = (n+r-1)!/((n+r-1)-r)!r! = (n+r-1)!/(n-1)!r!

And it is solved!
 
You must log in or register to reply here.
Back
Top