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^{n−1} 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 2*n*−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^{n−1} 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

### Like this:

Like Loading...

*Related*

##
About Peter Cameron

I count all the things that need to be counted.

cute.

We are waiting for your book. The proof of your student is interesting.

This argument can be found e.g. in van Lint, Wilson “A course in combinatorics”, p. 134 (after problem 15C).

The devil might have the best tunes, but van Lint and Wilson have the best proofs! Unfortunately I gave my copy away when I left Queen Mary 😦

(Shameless advertising) I just ordered it from Blackwells, which had a discount plus free UK delivery….

Today is publication day, but I probably won’t actually get a copy in my hands until next week; they will send them to St Andrews but I am in Brighton this week…