The Joy of Counting

Our initial introduction to mathematics is when we first learn to count. Counting leads to arithmetic. Children come to realize that adding 3 to 5 is simply a matter of counting 3 times past 5. The other arithmetic operations - subtraction, multiplication and division - all derive from addition. In the nineteenth century Giuseppe Peano used this counting approach to define integers and derive all the common algebraic rules.

Thus counting lies at the heart of our concepts of number,
arithmetic and algebra. Like the characters on Sesame Street
mathematicians are always finding new things that can be counted.
In this section a few of the basic concepts will be presented
from the branch of mathematics called **combinatorics**.
Combinatorics can be loosely defined as the study of the number
of ways that things can be arranged. Combinatorics is of interest
in itself and also has wide applicability to other areas of
mathematics.

Below is a list of three problems which will be used to illustrate three related calculations in combinatorics. Try to solve them before reading any further. Following the list of problems will be a discussion of how the counting methods of combinatorics can be used to gain insight into their solution.

**1.*** *Given nine coins one of which is
counterfeit and slightly heavier than the others, use a balance
to determine the counterfeit in 2 weighings.

**2.** Given five coins of different weight, use
a balance to order the coins by weight in 7 weighings.

**3.** Given four coins with two counterfeit
coins of equal weight that are slightly heavier than the normal
coins determine the two counterfeits in two weighings of a
balance.

**Solution to First Problem - the Product
Rule**

This is a classic problem in recreational mathematics. Let us start out by turning things around a little. Given only one weighing, how many coins could we start with where one of the coins is heavier than the others?

In a single weighing there are only three things that can happen. Either the left pan goes down, the right pan goes down or the two pans balance. This tells us that the best that we could do would be to decide among three possibilities. If we start with three coins then there are three possible choices for the counterfeit. If we weigh two of these it should be obvious how to determine which is the heavy one.

How many possible things can happen in two weighings? Let us label the three outcomes as L, R and B for left, right and balance. For each outcome from the first weighing there are three possible outcomes from the second for a total of 9. They could be labeled:

LL RL BL LR RR BR LB RB BB

It makes no difference that the coins chosen for the second weighing may depend on the outcome of the first. Two weighings can decide between at most 9 possibilities.

Suppose that we start with 9 coins and for the first weighing put 4 coins in each pan. If one of the pans goes down then there are 4 possible coins that might be the heavy one. However, there is only one weighing left, which can only decide among 3 possibilities. Therefore the first weighing can not lead to a solution. I can now confidently leave the solution to the problem as an exercise.

As a slight variation on the problem, combine the different second weighings into a single weighing that will be the same regardless of the outcome of the first.

How many possibilities are there in 3 weighings? What would the first weighing look like?

Another classical problem is a more advanced version of the previous one. Start with 12 coins where the counterfeit may be either heavier or lighter and find the counterfeit in 3 weighings.

Since each coin may be either heavy or light there are now 2*12 = 24 possibilities. Three weighings can decide between at most 3*3*3=27 possibilities. I will start you off on how to tackle this problem before leaving it as an exercise. Suppose that for the first weighing you place 6 coins in each pan. One pan will go down so that there are 6 coins that may be heavy and 6 that may be light for a total of 12 possibilities, but the two remaining weighings can decide between at most 9 possibilities.

This problem does not generalize as easily as the previous one. I came across a way of doing so which you can look at in Generalized Solution of 12 Coin Problem.

**The Product Rule**

The coin problems illustrate what I have seen described as the
product rule:

If there are two events e_{1} and e_{2} where the
number of possibilities for each event is independent of the
outcome of the other one and if the number of possibilities for
the two events are *n*_{1} and *n*_{2}*
*then the total number of ways that e_{1 }and e_{2
}can occur together is *n*_{1}**n*_{2}.

This generalizes to k events e_{1}, e_{2}, ...
, e_{k} with the number of possibilities for the
corresponding events of *n*_{1}, *n*_{2},
..., *n*_{k}. The total number of
possibilities is *n*_{1}**n*_{2}*..**n*_{k}.

How many 3 digit numbers can we form, allowing for leading zeroes? Since there are 10 possibilities for each place there are a total of 10*10*10 possibilities, which are the numbers from 0 to 999. How many numbers can we form with 3 digits if we do not allow leading zeroes? There are now only nine possibilities for the first digit and 10 for each of the other two for a total of 900 possibilities, which are the numbers from 100 to 999.

For a combination lock where the lock opens with the correct sequence of 3 numbers from 1 to 40 the total number of possibilities is 40*40*40 = 64,000.

How many numbers divide one million? 1,000,000 = 10^{6}
= (2*5)^{6} = 2^{6} * 5^{6}. Each divisor
has the form 2^{x} * 5^{y}, where x and y range
from 0 to 6, so the total number is 7*7 = 49, which will include
one and one million as divisors.

**Solution to Second Problem -
Permutations**

In this problem each weighing has only 2 possibilities since
the coins all have different weights. A sequence of n weighings
can handle at most 2^{n} possibilities. How many
possibilities are there?

Number the coins from 1 to 5 and list them from left to right,
from lightest to heaviest. The first coin can be any one of the
five. For each of the five coins, there are 4 possibilities for
the second coin, so by the product rule there are a total of
5*4=20 possibilities for the first two coins. For each of the 20
pairs of coins there are 3 possibilities for the third coin for a
total of 5*4*3 possibilities for the first 3 coins. Continuing in
this way we get a total of 5*4*3*2*1=120 possibilities for all
five coins. Since 2^{6}=64 and 2^{7}=128 we can
conclude that it will take at least 7 weighings to order the five
coins.

Start by weighing a pair of coins and then weighing a second pair of coins. Then weigh the heavier coin from each of the first two weighings. From the first 3 weighings the situation is as depicted below. An arrow from coin 1 to coin 2 means that coin 1 is lighter than coin 2.

Note that 3 of the coins, A, B and C are ordered relative to one another. We can order four coins by first comparing E and B and, depending on the result, comparing E and A or E and C. This makes for a total so far of 5 weighings.

We know that D is lighter than C. To find how D relates to the other three coins we proceed as we did for placing coin E. Compare D to the middle coin of A, B and E. Then, depending on the result compare D to either the heaviest of the 3 coins or the lightest. This makes for a total of 7 weighings to completely order the 5 coins.

**Permutations**

The total number of ways of ordering n objects is called a **permutation
**of n objects. The number of permutations of *n*
objects is *n*(n-1)*(n-2)*...*1*, which is designated as **n!**
and pronounced "n factorial". We also speak of the
number of ways of ordering* k* out of *n* objects
as a permutation of *k* objects out of *n* or P(n,
k) and is given by

**P(n, k) = n*(n-1)*...*(n-k+1) = n! / (n - k)!**.

Note that n! = P(n,n) = n! / 0!. To get this and other formulas to work correctly it is convenient to simply define 0! to be 1 without working out the philosophic implications.

The problem of ordering information comes up all the time in
computer programming, particularly when working with databases.
As in the above coin problem the total number of possibilities
covered by *m* comparisons is *2*^{m}*
*and the total number of ways of arranging *n* objects
is *n!*. Even for relatively small values of *m *and
*n* these expressions become very large. How do we
estimate* m* for a given value of *n*?

Let us follow the common convention of designating the log of
number using a base of 2, *log*_{2}* x*,
as *lg(x)*. We want to find *lg(n!)*.

lg(n!) = lg(n*(n-1)*...*1) = lg(n) + lg(n-1) + ... + lg(1). If we
knew the average value of lg(k) for k=1 to n then we could find
lg(n!) by multiplying the average by n.

Suppose n=2^{20}, or a little over one million. The
middle value is half of 2^{20 }=^{ }2^{19},
whose log is 19. Using 19 as our estimate of the average, we
estimate lg(2^{20}!) as 19*2^{20}, or about
nineteen million, which is accurate to within about 7%. This
means that a million database records would require about
nineteen million record accesses and comparisons, which can be
done by a desktop computer in a reasonable amount of time.

**Solution to Third Problem -
Combinations**

I made this problem up and there should be no difficulty in solving it. Although not as challenging as the other problems, this problem will serve to introduce the next concept in combinatorics.

Since there are three possibilities for each weighing *n*
weighings can cover at most 3^{n }possibilities. How many
possibilities are there?

We can number the coins from 1 to 4 and look at the permutations of 2 out of 4 coins to get P(4,2)=4*3=12, but there is something wrong with this calculation, since this would imply that at least 3 weighings would be required. Do you see the error? We do not care about the order of the coins. If 1 and 2 are the counterfeit coins, listing ordered pairs means that the two coins will be counted twice, once as (1,2) and once as (2,1). To get the total number of possibilities we have to divide by 2 to get 6 possibilities, correctly implying that there must be at least two weighings.

Before introducing formal definitions, let us consider another related problem. In the game of Poker a hand consists of five cards dealt from a deck of 52. How many different Poker hands are there?

We start out by considering permutations of 5 out of 52. P(52,5) = 52*51*50*49*48. Each hand will be counted more than once. How many times will each hand be counted? A given hand of 5 cards can be arranged in 5! = 5*4*3*2*1 = 120 different ways, so the total number of hands is 52*51*50*49*48 / 120 = 2,598,960.

**Combinations**

A combination is a way of choosing *k* objects out of a
collection of *n*. For those familiar with the terminology
of set theory, a combination is a subset of *k* objects
from a set of* n*. The number of ways of choosing* k*
objects out of *n* is designated C(*n*,* k*)
and is usually read as "*n* choose *k*".
From the above examples it should be clear that

**C(****n****, ****k****)
= P(****n****, ****k****)
/ k! =**** n****! / ((****n****
- ****k****)! * ****k****!)**.

**Some Properties of Combinations**

Let us determine the total number of combinations of 6
objects,

C(6, 0) + C(6, 1) + C(6, 2) + C(6, 3) + C(6, 4) + C(6, 5) + C(6,
6). For each combination there are two possibilities for each
object: the object is either in the combination or it is not. We
can use the letters "I" for in and "O" for
out to list each combination. (I, I, I, I, I, I) would correspond
to the single combination containing all 6 objects. By the
product rule the total number of combinations is 2^{6}=64
and in general:

**the sum of all values of C(n, k) for a fixed value of n
is 2**^{n}.

Notice that for each combination of k objects out of n there
is a unique combination of (n - k) unchosen objects. It follows
then that the total number of ways of choosing k objects out of n
is the same as the total number of ways of choosing (n-k) objects
out of n, that is **C(n,k) = C(n, n-k)**. This can
also be easily proved algebraically. C(n,n-k) = n!/(
(n-k)!*(n-(n-k))! ) = n!/( (n-k)!*k! ) = C(n,k).

Suppose we wanted to know the number of ways of choosing 8 objects out of 20, C(20, 8), and we knew all the values for combinations of 19, C(19, k). We could reason as follows. Number the objects from 1 to 20 and divide the combinations of 8 out of 20 into two groups: combinations that do not include object number 20 and those that include it.

Combinations of 8 out of 20 that do not include 20 are simply
the combinations of 8 out of 19, of which there are C(19,8).
Consider the combinations of 8 in 20 that include 20. Since all
these combinations include 20, the only variation comes from the
7 other objects chosen, of which there are C(19, 7). Therefore
C(20,8) = C(19,8) + C(19,7) and, in general

**C(n, k) = C(n-1, k) + C(n-1, k-1)**, which is
known as Pascal's identity.

Before reading further try to algebraically prove Pascal's identity.

C(n-1,k) + C(n-1, k-1) = (n-1)!/(k!*(n-k-1)!) +
(n-1)!/((k-1)!*(n-k)!)

The two terms on the right have a common denominator of
k!*(n-k)!, since

k*(k-1)! = k! and (n-k)*(n-k-1)! = (n-k)!

Multiplying the numerator and denominator of the first term by
(n-k) and multiplying the numerator and denominator of the second
term by k gives:

(n-k)*(n-1)!/(k!*(n-k-1)!*(n-k)) + k*(n-1)!/k*((k-1)!*(n-k)!) =

(n-k)*(n-1)!/(k!*(n-k)!) + k*(n-1)!/(k!*(n-k!))=

((n-k)+k)*(n-1)!/(k!*(n-k)!) = n*(n-1)!/(k!*(n-k)!) =
n!/(k!*(n-k)!) = C(n,k)

**The Binomial Theorem**

If a coin is flipped 3 times, how many different ways are
there of getting two heads? The solution is the total number of
combinations of two tosses of the 3 or C(3, 2) = 3. Now consider
the expression (H+T) * (H+T) * (H+T) where we can think of H
standing for head and T for tail. The terms of the expansion are
formed by choosing H or T from each bracketed pair. The
coefficient of H^{2}*T is then the number of ways of
choosing 2 of the bracketed expressions out of 3 or C(3,2). In
general,** C(n,k) is the coefficient of X**^{k}***Y**^{(n-k)}**
in the expansion of (X+Y)**^{n}.

To derive another proof that the sum of the terms C(n,k)=2^{n}
for fixed n, set X=Y=1 in (X+Y)^{n}.

For another interesting result, set X=1 and Y= -1. (1+ (-1))^{n
}= 0, with the coefficients C(n,k) of 1^{k}*(-1)^{(n-k)}
alternately multiplying 1 or -1, always giving the opposite sign
for even and odd values of k. This shows that the sum of the
C(n,k) terms where k is even always equals the sum of the C(n,k)
terms where k is odd.

**Poker Hand Problem Set**

As far as I know mathematicians are no more likely to be gamblers than anyone else, but games of chance are a good source of problems. In that spirit, I thought that it would make a good problem set to determine the number of ways of being dealt the different types of Poker hands.

In the game of Poker a hand consists of 5 cards drawn from a standard deck of 52 cards. The 52 cards are divided into 4 suits - clubs, diamonds, hearts and spades - and each suit is divided hierarchically into 13 ranks - 2, 3,4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.

The types of winning hand from highest to lowest are:

__Straight Flush__- Five cards that are both a straight and a flush (see below for defininitions of straight and flush)__4 of a kind__- Four cards of the same rank__Full house__- 3 cards of the same rank and two others of the same rank__Flush__- Five cards in the same suit__Straight__- Five cards that can be arranged so that each card has rank 1 greater than previous card. There is one slight complication - In a straight the highest ranking card (the Ace) can also be used as the lowest ranking card. Since the lowest ranking card is the 2, this adds one extra type of straight - Ace, 2, 3, 4, 5 - for a total of 10 different types.__3 of a kind__- 3 cards of the same rank and other two cards not of same rank__Two pairs__- 2 cards of one rank and two cards of another rank__Single pair__- two cards of same rank and none of the other 3 cards of same rank

Not surprisingly, the number of possible hands increases going down the hierarchy, so now you do not have to worry about remembering what beats what.

Try to write expressions for the number of hands of each type and then compute them. Since it was shown above that the total number of hands is about 2.5 million the calculations can be done on a pocket calculator provided that you cancel factorial terms in the denominators with terms in the numerators. From the number of hands the probability of getting a hand of a particular type is computed by dividing by the total number of hands which is 2,598,960.

**Solution**

**Straight Flush** - There are 10 possible
straights in each suit and 4 suits so that total number of
straight flushes is 4*10=40.

**Four of a kind **- Multiplying number of ranks
for the four of a kind by the number of remaining cards gives
13*48= 624.

**Full House** - To get the possible combinations
of ranks find the number of permutations of 2 in 13 = P(13,2).
Note that you do not want the number of commbinations of 2 in 13
since the order makes a difference - three nines and two tens is
different from three tens and two nines.

The number of ways of getting 3 cards of a specified rank is C(4,3) and the number of ways of getting 2 cards of a specified rank is C(4,2) so the total number of hands is P(13,2) * C(4,3) * C(4,2) = 156 * 4 * 6 = 3,744.

The probability of being dealt a full house is 3744/ 2,598,960 or about 1.4 in a thousand.

**Flush** - For each suit the number of ways of
choosing 5 cards from the suit is C(13,5) giving 4 * C(13,5) =
5,148. From this you have to subtract the 40 straight flushes for
a total of 5,108.

**Straight** - There are 10 ways that the ranks
can be arranged sequentially. For each such choice there are 4
available cards for each rank giving 10 * 4^{5} = 10,240.
Subtract the 40 straight flushes from this for a total of 10,200.

**Three of a kind **- Two ways of doing the
calculation will be given.

*First method *- To exclude full house combinations the
hand must contain 3 different ranks - one for the 3 of a kind and
2 for the other two cards. Since the order of the ranks does not
matter for the other two cards the number of ways of such rank
combinations is the number of ways of choosing the first rank
multiplied by the number of ways of choosing a combination of 2
from the remaining 12 ranks = 13 * C(12,2).

For each such combination of ranks there are C(4,3) ways of choosing 3 cards and 4 ways of choosing cards from the other two ranks. The total is therefore 13 * C(12, 2) * C(4,3) * 4 * 4 = 13 * 66 * 4 * 4* 4 = 54,912.

*Second method* - Compute all the ways of getting 3
cards of the same rank, multiply by the total number of ways of
choosing the two other cards and then subtract the number of full
house combinations. 13 * C(4,3) * C(48, 2) - 3,744 = 13*4*1128 -
3,744 = 54,912.

**Two pairs** - Find the number of ways of
choosing 2 ranks out of 13, multiply by the number of ways of
choosing 2 cards of 4 for each pair and multiply by the remaining
44 cards to get C(13,2) * C(4,2) * C(4,2) * 44 = 123,552.

**One pair** - To exclude higher value hands
there must be 4 different ranks in the hand. Since the order of
choosing the unpaired cards does not matter, the number of rank
combinations is 13 * C(12,3). The total number of hands is then
13 * C(12,3) * C(4,2) * 4^{3} = 13 * 220 * 6 * 64 =
1,098,240. The chances of being dealt a pair are 1098240/ 2598960
or about 42%.

**A Useful Technique**

There is a technique that can often be used to solve combinatorial problems. The simplest way to introduce it is by way of example. To determine C(7,3), consider permutations (a,b,c,d,e,f,g) of 7 objects. We will choose the first 3 members (a,b,c) for combinations. Now determine how many times that a combination will be repeated. Each of a, b and c can be in any order and so can each of d, e, f and g, so the number of repetitions is 3! * 4! and therefore C(3, 7) = 7!/(3! * 4!).

This then is the technique:

1. Consider permutations of n objects.

2. Determine a way of assigning members of each permutation to
the desired solution set.

3. Compute how many times each solution will be repeated.

4. The answer is n! divided by the number of repetitions.

Now solve the following two problems using this technique. The second problem was submitted to me by a visitor to this page.

1. A soccer team plays 12 games and has a record of 7 wins, 3 losses and 2 ties. In how many ways can this occur?

2. In a league of 6 teams, each time that the teams play all of the teams are involved so there are always 3 games. In how many ways can this occur? What is the general equation for n teams?

Answers:

1. For each permutation of 12 games, assign the first 7 numbers to wins, the next 3 to losses and the last 2 to ties. The answer then is 12!/(7! * 3! * 2!) = 7920.

2. For each permutation of 6, assign the first 2 numbers to
the first game, the next 2 numbers to the second game and the
last two numbers to the last game. Since the order of the games
does not matter, shuffling the games around gives a factor of 3!.
The order of each of the pairs also does not matter, for a factor
of 2^{3}. The solution then is 6!/(3!*2^{3}) =
15.

The general formula is n!/( (n/2)! * 2^{(n/2)}) = P(n,
n/2)/ 2^{(n/2)}. If we distinguished between home teams
and visiting teams then the order of the pairs would matter and
the solution in that case would simply be P(n, n/2).

HOME