Permutations and CombinationsIntroduction

Aman's grandfather has an old tin trunk with a number lock. The lock has four wheels, and each wheel can show any digit from 0 to 9. Dadaji remembers only two things about the code: it starts with 7, and no digit appears twice. The rest is gone.

So Aman will have to try codes one by one. How many might he need before the trunk opens — fifty? Five hundred? Five thousand?

Warm up on a smaller lock first. Riya's pencil box has a lock with just two wheels, each showing 1, 2, 3 or 4, and its code never repeats a digit either. Imagine the worst possible luck: the box opens only on the last code you try. Tap a wheel to change its digit, press "Try this code", and keep going until you have tried every possible code.

Look at how the grid filled up. There is one row for each digit on the first wheel — rows. In every row the second wheel can show any digit except the one already on the first wheel, so each row holds codes. That makes codes, and you could have counted them without trying a single one.

Now Dadaji's trunk. The first wheel is fixed at 7. The second wheel can show any of the other digits. Whatever it shows, the third wheel has digits left, and the fourth has 7. So Aman may have to try as many as codes. Listing them all would take an afternoon; counting them took one line.

That is what this chapter is about: counting without listing. You will learn to count the ways of arranging things in order — codes, words, seating plans — and the ways of selecting things when order does not matter — teams, committees, hands of cards. It all starts with the multiplication you just did.

Counting, the Indian Way

Around the 3rd century BCE, the Sanskrit scholar Pingala worked out, in his Chhanda Sutra, how many ways long and short syllables can be combined in a line of verse — the same counting question in a different costume. Jain scholars treated the subject as a topic of its own, which they called Vikalpa, and around 850 CE the Jain mathematician Mahavira gave general rules for counting arrangements and selections, perhaps the first anywhere. In the 12th century, Bhaskaracharya gave the topic a part of his famous book Lilavati, under the name Anka Pasha, and added several new results.

Outside India, early traces appear in the Chinese I Ching, the Book of Changes. Around 1140, Rabbi ben Ezra counted the ways of choosing the known planets two at a time, three at a time and so on, and in 1321 Levi ben Gerson wrote down general formulas. The first complete book on the subject was Ars Conjectandi by the Swiss mathematician Jacob Bernoulli, published in 1713, after his death.

Drag these milestones into the order in which they happened, earliest at the top.

Two and a half thousand years, and the question has not changed: in how many ways? Let us start answering it.