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₁ and e₂ 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₁ and n₂ then the total number of ways that e₁ and e₂ can occur together is n₁*n₂.

This generalizes to k events e₁, e₂, ... , e_k with the number of possibilities for the corresponding events of n₁, n₂, ..., n_k. The total number of possibilities is n₁*n₂*..*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⁶ = (2*5)⁶ = 2⁶ * 5⁶. 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ⁿ 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⁶=64 and 2⁷=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₂ x, as lg(x). To solve for 2^m = n!, take the lg of both sides to get m = 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²⁰, or a little over one million. As a rough estimate we will take the average value of lg(n) to be lg(n/2)= lg(2²⁰ /2) = lg( 2¹⁹) = 19. Using 19 as our estimate of the average, we estimate lg(2²⁰!) as 19*2²⁰, 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.

The Birthday Problem

As another example of permutations, here is a well known problem in probability that many people find counter-intuitive and for that reason is sometimes referred to as the birthday paradox. Given 23 randomly chosen people, what is the probability that at least 2 of them celebrate their birthday on the same day.  To simplify things, ignore February 29 and assume that the birthdays are equally distributed among the other 365 days.What must be realized is that  each person is being compared to everyone else, making for a lot of comparisons, so it should not be surpising that the probability is farily high.

To write an expression for the solution to this problem, find the complementary probability, that is find the probability that everyone has a different bithday, and then subtract from 1.   By the product rule, the total number of  possible birthdays is 365²³.  The total number of different birthdays is the number of permutations of 23 numbers out of 365 = P(365, 23), so the answer is 1 - P(365, 23) / 365²³ = .507 to three places.  That is, the chances are about even that at least two people will have the same birthday.

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ⁿ 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⁶=64 and in general:
the sum of all values of C(n, k) for a fixed value of n is 2ⁿ.

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²*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)ⁿ.

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

For another interesting result, set X=1 and Y= -1. (1+ (-1))ⁿ = 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.

Exercise: Show that for integers a and b and prime number p,
(a+b)^p - a^p - b^p is divisble by p.
Hint: Look at the terms for (a+b)²,(a+b)³ and (a+b)⁵

Solution: The coefficient of a^kb^p-k in (a+b)^p is C(p,k) = p!/k!(p-k)!. When k=0 or k=p this term will be 1, which is the coefficient for a^p and b^p. For all other terms, k and p-k are both less than p, so there will be no terms in the denominator to cancel the p term in the numerator. Therefore the coefficient of every term other than a^p and b^p will be divisible by p and so the will the sum of them.

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:

1. Straight Flush - Five cards that are both a straight and a flush (see below for defininitions of straight and flush)
2. 4 of a kind - Four cards of the same rank
3. Full house - 3 cards of the same rank and two others of the same rank
4. Flush - Five cards in the same suit
5. 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.
6. 3 of a kind - 3 cards of the same rank and other two cards not of same rank
7. Two pairs - 2 cards of one rank and two cards of another rank
8. 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⁵ = 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³ = 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³. The solution then is 6!/(3!*2³) = 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).

Fermat's Little Theorem



HOME