Counting

I’m teaching enumerative combinatorics this term; it brings an old incident back to my mind.

In 1984, Dugald Macpherson and I stopped for breakfast at a Dutch pancake house near Vancouver. The restaurant offered a choice of “1001 toppings”. We speculated that, because 1001 is 14 choose 4, there were 14 different sorts of toppings, and you could choose any four. But it wasn’t so; there were 25 different sorts of toppings, and you could have any combination, giving 33554432 possibilities.

Clearly, 1001 was just meant to convey “a very big number”, possibly with shades of Scheherezade and the mystic East.

A somewhat similar thing happened here recently. McDonalds, in posters splashed all over the Underground, offered a “meal deal” with 40312 combinations. What is special about 40312? It is 8!–8, certainly, but I offer a small prize to anyone who can find a “natural” counting problem to which the answer is n!–n.

Still, this suggests that McDonalds, or their advertising department, thought that 40312 was somehow related to the number of combinations of 8 things. The discussion made the “Feedback” column of New Scientist, where somebody pointed out that in that case the number should be 255. Finally someone who shares my tastes wrote to point out that the number should be 256: “you forgot my favourite combination.”

(Another possible book topic there: “Empty Set Theory”.)

I was on the verge that we should give this sequence the name “the McDonalds
sequence” and study its properties, but it has already been done: the Encyclopedia of Integer Sequences lists it as sequence number A005096, with the following comment:

McCombinations: in 2002, McDonalds advertised a McChoice menu of 8 items under the heading “40,312 combinations” rather than the more obvious 2^8-1=255 (A000225). The Advertising Standards Authority “considered that the number quoted in the advertisement was not necessarily so exaggerated as to be misleading”. – Henry Bottomley (se16(AT)btinternet.com), May 01 2003

Another counting problem was encountered by Myles Aston, who described it in the course of a book review in the Balliol College Annual Record in 2001:

The miserable wasteland of multidimensional space was first brought home to me in one gruesome solo lunch hour in one of MIT’s sandwich shops. “Wholewheat, rye, multigrain, sourdough or bagel? Toasted, one side or two? Both halves toasted, one side or two? Butter, polyunsaturated margarine, cream cheese or hoummus? Pastrami, salami, lox, honey cured ham or Canadian bacon? Aragula, iceberg, romaine, cress or alfalfa? Swiss, American, cheddar, mozzarella, or blue? Tomato, gherkin, cucumber, onion? Wholegrain, French, English or American mustard? Ketchup, piccalilli, tabasco, soy sauce? Here or to go?”

The precise number of combinations here depends on whether you are allowed to opt for “none” in answer to any of the questions – the empty set strikes again!

My last two examples have nothing to do with eating, and I freely admit that I am recycling them from exercises in my Combinatorics book published in 1994.

According to the Buddha,

Scholars speak in sixteen ways of the state of the soul after death. They say that it has form or is formless; has and has not form, or neither has nor has not form; it is finite or infinite; or both or neither; it has one mode of consciousness or several; has limited consciousness or infinite; is happy or miserable; or both or neither.

He does go on to say that such speculation is unprofitable; but bear with me for a moment.

With logical constructs such as “has and has not form, or neither has nor has not form”, it is perhaps a little difficult to see what is going on. But, while I hesitate to disagree with the Compassionate One, I think there are more than sixteen possibilities described here: how many?

The Library of Babel, according to Jorge Luis Borges, consists of interconnecting hexagonal rooms. Each room contains twenty shelves, with thirty-five books of uniform format on each shelf. A book has four hundred and ten pages, with forty lines to a page, and eighty characters on a line, taken from an alphabet of twenty-five orthographical symbols (twenty-two letters, comma, period and space). Assuming that one copy of every possible book is kept in the library, how many rooms are there?

All mathematicians should read Borges. I am going to have to acquire at least a rudimentary knowledge of Spanish: a former student gave me a copy of Borges y la Matemática by Guillermo Martínez.

Advertisements

About Peter Cameron

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

3 Responses to Counting

  1. I just checked my diary: in fact the Dutch pancake house had 26 toppings to choose from, so the number is twice what I claimed. Read about it here.

  2. Pingback: Phenomenology of 256 « Log24

  3. Jerome JEAN-CHARLES says:

    Natural to me (in real world) a counting problem whose answer is n! – n .

    n soldiers on a row get inspected by general Random his name means he does not like order, and he is blind to the first man in the row of soldiers he inspects. So to be pleased he is asking for at least one inversion of value when going from second to last spot.

    There are clearly n!-n ways of presenting the soldiers in a row to general Random so that he is satisfied.

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