Unizor - -Combinatorics - Combinations with Repetitions

• published: 19 May 2014
• views: 447

In this lecture we will discuss a different type of combinations - the combinations with repetitions. Assume, again, that we have to pick K objects out of a set of N different objects, but after each pick we just record which object we picked and then put it back, so we can pick the same object again repetitively. Now we can have the number of picks K not restricted by the number of objects N, it can be smaller, equal or greater than N. Another, more practical situation of combinations with repetitions can be observed if the number N represents not the total number of objects, but the number of different types of objects with an unlimited number of objects of each type (so, we don't have to return back our pick to facilitate the repetition). Now our task is to pick K objects, and combinations we pick differ only by their composition, that is the number of objects of each type. For example, we came to a store to buy some wine. We would like to pick the total of K=5 bottles and we have N=3 types of wine we want - red, white and sparkling. The question is, how many different combinations of these three types of wine we can choose in a set of five bottles, assuming the store has sufficient supply of each type. As in the case of regular combinations, let's come up with some clever logical procedure to resolve this problem. We will use the wine example above to illustrate it. Let's use a letter W to indicate a bottle of wine and a slash / to separate wines of different types. For instance, we picked 1 red, 1 white and 3 sparkling wines. Then we can form a string that represents our purchase as follows: W/W/WWW Analogously, string /WWWWW/ indicates our pick of five bottles of white wine, string //WWWWW indicates a purchase of five bottles of sparkling wine, string WW/WW/W indicates a purchase of two red, two white and one sparking wine bottles. As we see, our pick is fully defined by these strings and the total number of different combinations is the total number of different strings of seven characters with five W's and two slashes. Since the difference between strings is only in the position of two slashes among seven characters, each string can be obtained by just picking two different numbers out of numbers from 1 to 7 and call the characters with these numbers "a type separator - slash", while the characters at other positions will be called "wine bottle - W". Therefore, the total number of our combinations with repetitions equals to a number of regular combinations of 2 objects of a set of 7 different objects: C(7,2) = 7! / (2!·5!) = 21. Incidentally, instead of picking the positions of two slashes, we can equally say that our pick is fully defined by the positions of five characters W. That leads to a number of regular combinations of five objects out of a set of seven different objects with a formula C(7,2) = 7! / (5!·2!) = 21. This is exactly the same as above, which should be of no surprise for us since the formula for regular combinations is symmetrical relative to a subset of chosen objects and a subset of remaining ones. Let's generalize this logic. We have N types of objects and unlimited number of objects of each type. We pick K objects out of them. How many different combinations of types (compositions of our set of picked objects) can be picked? Following the same logic and symbolics, let's imagine strings containing K characters W signifying a picked objects and N−1 type separators - slashes /. The length of each string is K+N−1. Each such string represents a particular composition of a set of picked objects by their types. So, the position of slashes (or, as we mentioned above, the position of W's) fully define the composition of a set of picked objects. The number of different strings of this kind is the number of regular combinations of N−1 objects out of K+N−1 or, equally, the number of regular combinations of K objects out of K+N−1: C(K+N−1,N−1) = = C(K+N−1,K) = = (K+N−1)! / [K!·(N−1)!] Let's consider a couple of simple examples to check this formula. Example 1: The number of object types N equals to 1. In this case we have only one choice to pick K objects - all objects are of that one and only type. The formula gives (K+1−1)! / [K!·(1−1)!] = = K! / (K!·0!) = 1 as is supposed to be. Example 2: The number of object types N equals to 2. In this case we can pick K objects by choosing 0 objects of the first type and K objects of the second type or 1 object of the first type and K−1 objects of the second type etc. up to K objects of the first type and 0 objects of the second type. The number of choices is K+1. The formula gives (K+2−1)! / [K!·(2−1)!] = = (K+1)! / [K!·1!] = = (K+1)! / K! = K+1 as is supposed to be.