My book Notes on Counting: An Introduction to Enumerative Combinatorics should be published by Cambridge University Press in June this year, as part of the Australian Mathematical Society Lecture Series.

If you have read some of my lecture notes on enumerative combinatorics, you may want to know that this book contains more than just the union of all the notes I have written on this subject!

If you are interested, there is a flyer, and preorder form, here.

But no job is ever finished. In the book, at the start of Chapter 4, I prove (as an introductory example for recurrence relations) that the number of compositions of n (ordered sequences of positive integers with sum n) is 2ⁿ⁻¹ if n ≥ 1. The easy proof involves showing that the number of compositions of n is twice the number of compositions of n−1. When I came to mark my St Andrews exam, I found that two students had produced a beautifully short and elegant proof of this, which may not be new but was certainly new to me!

It goes like this. Imagine you are a typesetter; you set up a row of 2n−1 boxes, each to contain a symbol. In the odd numbered boxes you put a 1; in the even numbered boxes, you choose to put a plus sign or a comma. Your 2ⁿ⁻¹ choices give all the compositions of n, each once.

For example, the compositions of 3 are

1+1+1    1+1,1    1,1+1    1,1,1