10 Counting systematically

In section 06 (Counting by exhaustion) we posed some counting problems which we were able to solve via exhaustive manual methods. Here we will take some of these and show how we can generalise them and solve larger problems by a formula, even when manual methods become too cumbersome. We will also see, what is nice about mathematics, that even though these methods are independent, they yield the same answers.

Derangements

Let us return to Example 6.1.

Example 6.1

In how many ways can a careless office boy place four letters in four envelopes so that no one gets the right letter?

Discussion

We will recall that we were able to systematically list all the cases and count them to give an answer of 9. We will define D(n) as the number of derangements of the integer n. This is the number of was of arranging the numbers 1 to n in such a way that none of the numbers are in correct order. For example, 23514 is a derangement of 12345 whereas 23541 is not.The careless office boy problem is equivalent to finding the value of D(4), which we found manually to equal 9.

The following formula gives the number of derangements D(n), of the numbers 1,2,3,… , n.

where n!, known as n factorial, equals n(n - 1)(n -2) x … x 3 x 2 x 1 (for example, 4!=4 x 3 x 2 x 1 = 24). For a simple explanation of this formula see Niven, Ivan, Mathematics of choice - How to count without counting, MAA, 1965, or for a strong guide to the proof go to the very foot of this page after reading the material on inclusion and exclusion.

So this problem is a special case of the above formula with n = 4, where

which is the answer we found by manual calculation.

Partial Derangements

We now return to the trumpets problem.

Example 6.2

In the school band, five children each own their own trumpet. In how many ways can exactly three of the children take home the wrong trumpet, while the other two take home the right trumpet?

Discussion

This is a partial derangements problem, in which a certain number of the set are in the correct positions, while the remainder are all in the wrong positions.

In the following discussion,

is the number of combinations possible from choosing r objects from a set of n (without regard to order). It can have other notations such as ⁿC_r as I used in the manual solution of this problem in section 06. We will also use D(r) as the number of derangements of the numbers 1,2,3,… , r, as used in the discussion of Example 6.1 above.

It is now easily established that if there are n children, each owning their own trumpets, the number of ways in which exactly r take home the wrong trumpet is

For n = 5, the solutions can be tabulated as

with the solution we want (20) being found on the line corresponding to r = 3.

Note that the sum of the solutions, 1 + 0 + 10 + 20 + 45 + 44 = 120 or 5!, is the total number of ways of allocating 5 trumpets to 5 children.

Pólya's Enumeration Theorem

We now turn our attention to the necklace problem of section 06, in which we listed all the cases. As we see here, a nice generalisation exists, saving us the trouble when the number of beads and colours is larger. It turns out that we are helped by a famous result of one of the most significant 20th century mathematicians in George Pólya, whose life is summarised on this web site under biographies or by direct link here.

Example 6.4

How many necklaces of 5 beads can be made with beads of 3 colours, assuming there is an infinite supply of each colour and necklaces are not changed just by rotating?

Discussion

I quote from the relevant part of the biography linked above.

`One of Pólya’s most famous results, the Pólya Enumeration Theorem, was published in 1937. This also arose from his interest in chemical structure and looking at possible configurations of the benzene ring and other figures with 6 vertices. Generalising a theorem by Burnside in Group Theory, Pólya showed how one can determine the number of different assignments of atoms, or colours, to vertices as sides of geometrical figures.

`A special case of this is the Necklace Theorem, which shows how many necklaces of n beads can be constructed with k colours available, assuming there is an infinite supply of each colour.In the case where n is prime and necklaces are regarded as unchanged by rotation, the number of configurations is k + (kⁿ - k)/n.'

Solution 6.4

Thus if there are 5 beads and 3 colours the number of necklaces is 3 + (3⁵ - 3)/5 = 3 + 240/5 = 3 + 48 = 51.

Discussion

This matches our manual answer. In the case where n is composite there is also a formula but it is more complicated. However more details of this and another version of the theorem can be found here.

Inclusion and Exclusion

We now recall the socks problem which we solved manually in section 06.

Example 6.5

I have four pairs of socks to be hung out side by side on a straight clothes line. The socks in each pair are identical but the pairs themselves have different colours. How many different colour patterns can be made if no sock is allowed to be next to its mate?

Discussion

I should first acknowledge ANU mathematician Mike Newman, who drew my attention to this solution after the AMC had been held. We had run just with the known solution in section 06, which I had found. Author of the problem was ANU mathematician Bob Bryce.

We look for a simpler method which might generalise to larger problems more easily. We will do so by starting with the simpler case of two pairs of socks.

Consider the problem for two pairs of socks, as illustrated in the Venn diagram.

The set A₁, for instance, is the set of arrangements in which pair 1 is together.

We wish to compute the quantity outside the two sets, namely

In this problem

(We divide by 2² because the socks within each pair can be changed without changing the arrangement.)

Now

and

so the solution is

(Note that the two solutions, using the notation of section 06, are abab and baba.)

We can now proceed to the solution to the problem with 4 pairs.

Solution 6.5

The inclusion-exclusion principle, as the method is known, generalises to give, in the n-pair case

In the case of 3 pairs, this gives

In the case of 4 pairs, this gives

which is the answer we obtained manually, counting by exhaustion.

Further discussion

In the case of n pairs this gives

Note that the first two terms always cancel each other in this particular problem.

Comment on derangement formula

The derangement formula is also a special case of the Venn diagram argument above, where A_i in this case would be the set of arrangements in which element i is in the right position. The factor n! outside is the number of arrangements altogether and the successive terms in the brackets are sums of numbers of A_i, next sums of intersections of two, then intersections of three etc.