The lottery "game" consists of picking
kk numbers from a pool of
nn. For example, you select
66 numbers out of
6060.
To win, the order in which you pick the numbers doesn't matter;
you only have to
choose the right set of 66 numbers. The chances of winning equal the number of
different length-kk sequences that can be
chosen.
A related, but different, problem is selecting the batting lineup for a
baseball team. Now the order matters, and many more choices are possible
than when order does not matter.

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 11 to
NN, the answer
is the same as the lottery problem with
k=6k6.
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
kk numbers from a pool of
nn, we have nn
choices for the first one. For the second choice, we have
n−1
n
1
. The number of length-two ordered sequences is
therefore be
n(n−1)
n
n
1
. Continuing to choose until we make
kk choices means the number of
permutations is
n(n−1)(n−2)…(n−k+1)
n
n
1
n
2
…
n
k
1
. This result can be written in terms of factorials as
n!(n−k)!
n
n
k
, with
n!=n(n−1)(n−2)…1
n
n
n
1
n
2
…
1
. For mathematical convenience, we define
0!=1
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 kk things can be ordered equals k!
k. Thus, once we choose the
nine starters for our baseball game, we have
9!=362,880
9
362,880
different lineups! The symbol for the combination of
kk things drawn from a pool of
nn is
nk
n
k
and equals
n!(n−k)!k!
n
n
k
k
.

What are the chances of winning the lottery? Assume you pick
66 numbers from the numbers
11-6060.

606=60!54!6!=50,063,860
60
6
60
54
6
50,063,860
.

Combinatorials occur in interesting places. For example, Newton
derived that the nn-th power of a
sum obeyed the formula
x+yn=n0xn+n1xn−1y+n2xn−2y2+…+nnyn
x
y
n
n
0
x
n
n
1
x
n
1
y
n
2
x
n
2
y
2
…
n
n
y
n
.

What does the sum of binomial coefficients equal?
In other words, what is
∑k=0nnk
k
0
n
n
k

Because of Newton's binomial theorem, the sum equals
1+1n=2n
1
1
n
2
n
.

A related problem is calculating the probability that
*any* two bits are in error in a
length-nn codeword when
pp is the probability of any bit
being in error. The probability of any particular two-bit error
sequence is
p21−pn−2
p
2
1
p
n
2
. The probability of a two-bit error occurring
anywhere equals this probability times the number of
combinations:
n2p21−pn−2
n
2
p
2
1
p
n
2
. 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
n01−pn+n1p1−pn−1+n2p21−pn−2+…+nnpn=1
n
0
1
p
n
n
1
p
1
p
n
1
n
2
p2
1
p
n
2
…
n
n
p
n
1
. Can you prove this?

Comments:"Electrical Engineering Digital Processing Systems in Braille."