- Discusses the basics of combinations and permutations, and how to calculate the probability of certain events, such as n-bit errors in a codeword.
The lottery "game" consists of picking
Answering such questions occurs in many applications beyond games. In digital communications, for example, you might ask how many possible double-bit errors can occur in a codeword. Numbering the bit positions from 1 to N, the answer is the same as the lottery problem with k=6. Solving these kind of problems amounts to understanding permutations - the number of ways of choosing things when order matters as in baseball lineups - and combinations - the number of ways of choosing things when order does not matter as in lotteries and bit errors.
Calculating permutations is the easiest. If we are to pick k numbers from a pool of n, we have n choices for the first one. For the second choice, we have n-1. The number of length-two ordered sequences is therefore be n(n-1). Continuing to choose until we make k choices means the number of permutations is
This result can be written in terms of factorials as
For mathematical convenience, we define 0!=1.
When order does not matter, the number of combinations equals the number of permutations divided by the number of orderings. The number of ways a pool of k things can be ordered equals k!. Thus, once we choose the nine starters for our baseball game, we have
different lineups! The symbol for the combination of k things drawn from a pool of n is
What are the chances of winning the lottery? Assume you pick 6 numbers from the numbers 1-60.
Combinatorials occur in interesting places. For example, Newton derived that the n-th power of a sum obeyed the formula
What does the sum of binomial coefficients equal? In other words, what is
Because of Newton's binomial theorem, the sum equals
A related problem is calculating the probability that any two bits are in error in a length-
The probability of a two-bit error occurring anywhere equals this probability times the number of combinations:
Note that the probability that zero or one or two, etc. errors occurring must be one; in other words, something must happen to the codeword! That means that we must have
Can you prove this?