Counting Matches, Handshakes and Triangles

Counting Matches, Handshakes and Triangles — Moosa Academy

How many matches in a tournament, how many handshakes at a meeting, how many triangles from a fan of lines — three questions that look unrelated but share one formula. Each is really asking the same thing: how many ways can two things be picked from $n$ ?

Theorem The pairing formula

The number of ways to choose two from $n$ is $\dfrac{n(n-1)}{2}$ . If each pair meets more than once, multiply by the number of meetings.

Four teams, each playing the other three. Every line in the diagram is one match, and there are six of them — matching

\dfrac{4 \times 3}{2} = 6

Concept Why divide by two

With four teams, each plays the other three:

4 \times 3 = 12

But "Saudi Arabia versus Egypt" and "Egypt versus Saudi Arabia" are the same match

Every match has been counted twice, so halve it:

\dfrac{12}{2} = 6

In general each of the $n$ teams meets $n - 1$ others, and the double counting is undone by dividing by $2$ — giving $\dfrac{n(n-1)}{2}$ .

Note It is a combination

Choosing two teams from $n$ with order irrelevant is exactly a combination:

C(n, r) = \dfrac{n!}{r!\,(n-r)!}

C(4, 2) = \dfrac{4!}{2!\,2!} = \dfrac{4 \times 3 \times 2 \times 1}{2 \times 1 \times 2 \times 1} = \dfrac{4 \times 3}{2} = 6

The pairing formula is just $C(n, 2)$ written out. Either route gives the same answer, so use whichever is quicker.

Concept The same idea in disguise

Handshakes — a handshake needs exactly two people, and A shaking B is B shaking A.

Triangles — when

n

lines fan out from one vertex to a straight base, any two of them close off a triangle.

In all three settings you are picking two items from $n$ with order irrelevant. That is why one formula covers matches, handshakes and triangles alike.

Example Four worked cases

a) A tournament of $10$ teams, each pair meeting once

\dfrac{10 \times 9}{2} = \dfrac{90}{2}

$45$ matches

b) A league of $16$ players, each pair meeting $3$ times

Pairs first:

\dfrac{16 \times 15}{2} = 120

Then multiply by the meetings:

120 \times 3

$360$ matches

c) A meeting of $12$ people, each shaking hands once with every other

\dfrac{12 \times 11}{2} = \dfrac{132}{2}

$66$ handshakes

d) Eight lines from one vertex to a straight base

\dfrac{8 \times 7}{2} = \dfrac{56}{2}

$28$ triangles

Part (b) is the one to watch. Find the number of pairs first, then multiply by how often each pair meets — never multiply $n$ by the meetings before halving.

Summary

The number of pairs from $n$ items is $\dfrac{n(n-1)}{2}$ .
Each item meets $n - 1$ others, and dividing by $2$ removes the double counting.
The formula is exactly $C(n, 2)$ , the combination of $2$ from $n$ .
Matches, handshakes and triangles are all "choose two from $n$ " in different clothing.
If each pair meets several times, work out the pairs first, then multiply.
Order never matters in these problems — that is what makes them combinations, not permutations.