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 n1+k = 13, equivalently n+k1, 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 n1 = 3 of n+k1 = 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!(nk)!
As justified above, to calculate combinations with repetition, simply replace n with n+k1 and k with n1,
(n+k1)!/(n1)!((n+k1)(n1))!
In our example above this would be (4+101)!/(41)!((4+101)(41))! = 13!/3!10!. Which is equivalent to
(n+k1)!/k!(n1)!
because (4+101)!/10!(41)! = 13!/10!3! = 13!/3!10!, which is the same result that we got above.
Further reading
 Combinations and Permutations
 Easy Permutations and Combinations
 How To Understand Combinations Using Multiplication
 Navigate a Grid Using Combinations And Permutations
 Combinations with Repetitions
 Counting multisets “n multichoose k”
Tags: math

emery

emery

emery