Thursday, May 21, 2015

Two interpretations of (n+m)!/(n!m!) combinations

Let's say we have 5!/2!/3! combinations. This means on one hand that we have 5 elements, 12345, yielding 5! permutations. If we abstract away the order of last 3 items, we will get 20 = 5!/3! pairs (2 first letters): 12,13,14,15,23,24,25,34,35,45 and same pairs in opposite order. If we additionally abstract away the order of these 2 first letters, we will get those 10 combinations.

On the other hand, 5! divided by 2! and 3! means that we have  two elements of first class and 3 elements of second type. In other words, we are looking at permutations of 11000: 11000, 10100, 10010, 10001, 01100, 01010, 01001, 00110, 00101, 00011. Again, we have 10 such strings.

There is a one-to-one mapping between the combinations:
$$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 11000 & 10100 & 10010 & 10001 & 01100 & 01010 & 01001 & 00110 & 00101 & 00011\\ 12 & 13 & 14 & 15 & 23  & 24 & 25 & 34 & 35 & 45\end{matrix}$$

This is not a big surprise since choosing 2 elements out of 5 is the same as choosing same 2 of 5 and placing them together. The latter can be interpreted as a 2-head. Then number of 2-element heads is equal to the number of ways to pick 2 elements out of 5.

No comments: