Chapter 6 ยท Introduction

Chapter 6 โ€” Permutations and Combinations

How many PINs, batting orders, committees or lottery tickets are there? Counting without listing โ€” by multiplying stages, arranging with ${}^nP_r$ and selecting with ${}^nC_r$.

More than two thousand years ago, the Indian scholar Pingala studied the rhythms of Sanskrit poetry, built from short and long syllables, and asked how many different rhythm patterns a line of a given length could have. A few centuries later the medical text of Sushruta counted the ways of mixing the six basic tastes โ€” sweet, sour, salty, pungent, bitter and astringent โ€” and found $63$ combinations. In the ninth century Mahฤvฤซra wrote down a general rule for the number of ways of choosing $r$ things from $n$, and in the twelfth century Bhฤskara II devoted a chapter of his Lฤซlฤvatฤซ to arrangements of digits. Counting, it turns out, is an old and very Indian branch of mathematics.

It is also a very modern one. Every time you set a UPI PIN, a password or an OTP, its security rests on the number of possible codes being too large to try them all. Vehicle number plates, mobile numbers and transaction IDs are designed by counting; IPL selectors, quiz-team captains and lottery designers all face the same two questions: how many ways can things be arranged, and how many ways can things be chosen? In this chapter you will learn to answer both without ever writing out the list โ€” first with the fundamental principle of counting, then with permutations ${}^nP_r$ for arrangements, and finally with combinations ${}^nC_r$ for selections. These numbers are the foundation of the binomial theorem in Chapter 7 and of probability in Chapter 14.

Count: stages multiply, cases addโ†’Arrange: $n!$, ${}^nP_r$, alike objectsโ†’Select: ${}^nC_r={}^nP_r/r!$โ†’Mix: select, then arrange
๐ŸŽฏ By the end of this chapter you canโ€ฆ
  • use the fundamental principle of counting and the addition principle, with tree diagrams and slots, to count codes, numbers, routes and outfits โ€” including "at least one" counts by subtraction;
  • work with factorial notation, prove ${}^nP_r=\dfrac{n!}{(n-r)!}$, and count arrangements with and without repetition;
  • count arrangements of objects that are not all different, such as the letters of a word with repeated letters, and handle "together" and "never together" conditions;
  • prove ${}^nC_r=\dfrac{n!}{r!\,(n-r)!}$ and the properties ${}^nC_r={}^nC_{n-r}$ and ${}^nC_r+{}^nC_{r-1}={}^{n+1}C_r$;
  • decide whether order matters, and solve mixed problems that select first and then arrange โ€” committees, teams, words and geometric counts.
Teaser โ€” How Fast Do Arrangements Grow?

Put $n$ different books on a shelf. The shelf shows every possible order, one after another, while the counter keeps score. With $3$ or $4$ books you can watch them all. Then slide $n$ up and look at the bars (each grid line is a thousand times the one below): the number of orders, $n!=1\times2\times\cdots\times n$, explodes โ€” showing all the orders of just $12$ books at one per second would take about $15$ years.

4
orders $n!$โ€”
shown so farโ€”
time at one order per secondโ€”

Sections in this chapter

6.1

The Fundamental Principle of Counting

Tree diagrams and slots; stages multiply, separate cases add; codes, PINs, numbers with conditions, routes and "at least one" by subtraction.

$n_1\times n_2\times\cdots\times n_k$
Open section โ†’6.2

Permutations

Factorials, the formula for ${}^nP_r$, arrangements with repetition, objects not all different, and the block and gap methods.

${}^nP_r=\dfrac{n!}{(n-r)!}$
Open section โ†’6.3

Combinations

Selections without order, the formula for ${}^nC_r$, its symmetry and addition rule, and mixed select-then-arrange problems.

${}^nC_r=\dfrac{n!}{r!\,(n-r)!}$
Open section โ†’
โœ… Before you start
You need sets, subsets, disjoint sets and the rule $n(A\cup B)=n(A)+n(B)$ for disjoint $A$ and $B$ from Section 1.3, and Cartesian products with $n(A\times B)=n(A)\,n(B)$ from Section 2.1 โ€” the first counting principle is really this formula. Functions from Section 2.3 appear in a few problems. From Class 10 Mathematics you need factorising quadratics (Chapter 4, Quadratic Equations), used to solve equations such as ${}^nP_2=72$, and probability as "favourable outcomes รท all outcomes" (Chapter 14, Probability) โ€” the counting of this chapter makes that idea far more powerful. Comfortable mental arithmetic with products like $9\times8\times7$ helps on every page.
โ† 5.2 Solving Linear Inequalities in One Variable6.1 The Fundamental Principle of Counting โ†’