Counting: Permutations & Combinations

Three friends — Atharv, Diya, and Kabir — have two cinema tickets to share. Who gets to go? You can simply name the pairs: Atharv and Diya, Atharv and Kabir, Diya and Kabir. Three pairs, found by hand in a moment.

Now make it ten friends and three tickets. Listing every group by hand is suddenly hopeless — there are far too many, and you would lose count halfway. So we need a way to count the groupings without writing them all out. And before we count anything, one quiet question decides which kind of counting we do: does the order matter?

The one question that splits everything

Sharing tickets, order does not matter. A pair of friends is the same pair whoever you happen to name first. But suppose the two tickets were numbered — seat 1 and seat 2 — and it mattered who sat where. Then Atharv in seat 1, Diya in seat 2 is a different outcome from Diya in seat 1, Atharv in seat 2. The same two people, counted as two, because the order changed.

That single difference splits all of counting in two. Hold on to it; everything below is just this question, answered carefully.

Counting by filling slots

Let us count the numbered-seat version first, because it is the more natural one. Think of the two numbered seats as two slots to fill, in order. Seat 1 can go to any of the three friends — three choices. Once seat 1 is taken, seat 2 can go to either of the two who remain — two choices. For each of the three ways to fill seat 1 there are two ways to fill seat 2, so the seats can be filled in 3 × 2 = 6 ways.

That is the whole of the multiplication rule: choices made in sequence multiply. A five-question test with four options each is five slots of four, so it can be answered in 4 × 4 × 4 × 4 × 4 = 4⁵ = 1024 ways. Same idea, more slots.

Permutations — when order matters

Those six ordered seatings have a name. Arranging r things out of n, in order, is a permutation, written nPr. The slots shrink as you fill them — n choices, then n−1, then n−2, down to the last slot — so

nPr = n · (n−1) · … · (n−r+1) = n! / (n−r)!

For our friends, 3P2 = 3 · 2 = 6, exactly the six seatings we just counted. The factorial form n!/(n−r)! is only bookkeeping; the shrinking slots are the real idea.

Combinations — when order does not matter

But the cinema tickets were never numbered. A pair is a pair. So among those six ordered seatings, each pair of friends was counted twice — once for each order the two could sit in. To forget the order, divide the six by the two orderings of each pair: 6 / 2 = 3. Three pairs — exactly the list we made by hand at the very start.

Selecting r things out of n when order does not matter is a combination, written nCr. It is the permutation with each group’s r! internal orderings collapsed to one:

nCr = nPr / r! = n! / ( r! · (n−r)! )

So 3C2 = 6 / 2! = 3. And now the ten-friends question is no trouble. Numbered tickets: 10P3 = 10 · 9 · 8 = 720. An unnumbered group of three: 10C3 = 720 / 3! = 720 / 6 = 120. No listing required.

Two small facts fall out and are worth keeping. nC0 = nCn = 1 — there is exactly one way to choose nobody, and one way to choose everybody. And nCr = nC(n−r), because choosing which r to include is the same as choosing which n−r to leave out; this quietly turns 25C23 into the one-line 25C2 = 300.

When some items are identical

One more case, because GATE likes it. When the things being arranged are not all different, some orderings look the same and must not be counted twice. Arranging n items where one value repeats n₁ times, another n₂ times, and so on:

arrangements = n! / ( n₁! · n₂! · … )

The letters of LEVEL — two L’s, two E’s, one V — arrange in 5! / (2! · 2!) = 120 / 4 = 30 distinct words, not 5! = 120, because swapping the two L’s (or the two E’s) leaves the word unchanged. Same move as the combination: divide out the orderings you cannot tell apart.

A worked example — counting hidden inside a probability

Most “probability” questions in this band are really a counting question wearing a disguise: favourable outcomes over total outcomes. Watch both counts.

total PINs (repeats allowed) = 10 · 10 · 10 · 10 = 10⁴ = 10000
all four digits different     = 10 · 9 · 8 · 7    = 10P4 = 5040

P(all different) = 5040 / 10000 = 0.504

Just over one-half. The numerator is a permutation — the four positions are ordered — and the denominator is the plain multiplication rule. Get the two counts right and the probability is a single division.

A question to carry forward

Soon you will meet the binomial distribution, where the number of ways to get k heads in n coin tosses is exactly nCk — a combination, not a permutation. Here is the thread to pull: the tosses happen in a definite order, so why does the order of the heads not matter when we count them?

In one breath

• One question splits all of counting: does order matter?
• Multiplication rule: choices in sequence multiply — fill slots (4⁵ = 1024).
• Permutation nPr = n!/(n−r)! — ordered; slots shrink n, n−1, … (3P2 = 6, 10P3 = 720).
• Combination nCr = n!/(r!(n−r)!) — unordered; it is nPr with each group’s r! orderings merged into one (3C2 = 3, 10C3 = 120).
• Repeats: divide by the factorial of each repeat count (LEVEL → 5!/(2!2!) = 30); and nCr = nC(n−r).
• Counting is the engine of easy probability questions (distinct PIN = 5040/10000 = 0.504), and nCr is the backbone of the binomial.

Practice