## Monday, January 16, 2012

### Information Highway: Binomial Coefficient

Last time I was trying to explain hypergeometric distribution (describing probability of k successes in n draws from a finite population without replacement). Maybe that was bit too steep to start this series of mathematical topics, so I will take one step back and talk about combinations, and the binomial coefficient.

In mathematics a combination is a way of selecting several things out of a larger group where (unlike permutations) order does not matter. Combinations can refer to the combination of n things taken k at a time with or without repetitions. In this article we are only looking at combinations without repetitions. For any set S containing n elements, the number of distinct k-element subsets of it that can be formed (the so-called k-combinations of its elements) is given by the binomial coefficient.

In smaller cases it is possible to count the number of combinations. For example, take a look at a set of the first for integer number (1,2,3,4) and subsets consisting of two (different) members of this set. You can make 6 subsets of 2 numbers: (1;2), (1;3), (1;4), (2;3), (2;4), (3;4). For larger sets this explicit enumeration can become very tedious.

The formula for the binomial coefficient (or short binom) is given (for 0 ≤ k ≤ n) as:
The binom is often read as "n choose k", and the factorial n! (of a non-negative integer n) is the product of all positive integers less than or equal to n. So you can extend the formula for the binom as:
As another example, the question how many different subsets of hole cards (starting hand) can you get in Texas Hold 'Em stands. That's quite easy to calculate with the formula above. There are 52 different cards in Poker, and with a starting hand of 2 cards, you get 1326 different starting hands:
That's actually a pretty low number, especially when you compare it with the numbers of get for VtES. The number of different starting hands 7 cards for a 90 card deck is
For 75 card that's reduced to 1,984,829,850 and for a 60 card to "only" 386,206,920 different starting hands.
References: (all Wikipedia)