Number of combinations with repetition

There are n = 4 sorts of candy to choose from and you want to buy k = 10 candies. How many ways can you do it?

This is a problem of counting combinations (order does not matter) with repetition (you can choose multiple items from each category). Below we will translate this problem into a problem of counting combinations without repetition, which can be solved by using a better understood formula that is known as the “binomial coefficient“.

First let us represent the 10 possible candies by 10 symbols ‘C’ and divide them into 4 categories by placing a partition wall, represented by a ‘+’ sign, between each sort of candy to separate them from each other

CC+CCCC+C+CCC

Note that there are 10 symbols ‘C’ and 3 partition walls, represented by a ‘+’ sign. That is, there are n-1+k = 13, equivalently n+k-1, symbols. Further note that each of the 3 partition walls could be in 1 of 13 positions. In other words, to represent various choices of 10 candies from 4 categories, the positions of the partition walls could be rearranged by choosing n-1 = 3 of n+k-1 = 13 positions

C++CCC+CCCCCC

CCCCCCCCCC+++

We have now translated the original problem into choosing 3 of 13 available positions.

Note that each position can only be chosen once. Further, the order of the positions does not matter. Since choosing positions {1, 4, 12} does separate the same choice of candies as the set of positions {4, 12, 1}. Which means that we are now dealing with combinations without repetition.

Calculating combinations without repetition can be done using the formula that is known as the binomial coefficient

n!/k!(n-k)!

As justified above, to calculate combinations with repetition, simply replace n with n+k-1 and k with n-1,

(n+k-1)!/(n-1)!((n+k-1)-(n-1))!

In our example above this would be (4+10-1)!/(4-1)!((4+10-1)-(4-1))! = 13!/3!10!. Which is equivalent to

(n+k-1)!/k!(n-1)!

because (4+10-1)!/10!(4-1)! = 13!/10!3! = 13!/3!10!, which is the same result that we got above.

Further reading

Tags:

  • emery

    Ok, this is fine; the “proof” does make sense insofar it is along the lines of the usual verbal descriptions passing as proofs for this particular problem. However, there is nothing new here conceptually or otherwise. Why do You bother to post arguments like this? Well known, well documented part of mathematics. Unless You can come up with an original angle on this, in my view the argument is not worthy of posting.

  • emery

    How about attacking this directly without “stars and stripes”
    -for n>k the number of combinations with repetition is obviously equal to
    C(n,k)+ n*(SUM i=0 to k-2 of C(n-1,i))

  • emery

    please disregard my last comment, it is quite false…my apologies