Notes on Counting

Notes on Counting

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 2n−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 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 2n−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

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in books, exposition and tagged , . Bookmark the permalink.

6 Responses to Notes on Counting

  1. sris says:

    cute.

  2. Shahrooz Janbaz says:

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

  3. Adam Malinowski says:

    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 😩

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

  5. 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…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s