Combinations

This section introduces the COMBINATION — a fundamentally different counting question from the permutation, since a combination is a SELECTION of objects where the ORDER of selection is irrelevant, in contrast to a permutation's ordered arrangement.

The motivating example revisits an earlier permutation scenario (from §3.5): 2 chairs filled from a group of 4 persons, A, B, C, D. But now the question changes — instead of asking for ordered SEATINGS, we ask for unordered GROUPS of 2 people, with no regard to which chair each person occupies. Under this new question, AB and BA now represent the SAME group of two people (just described in a different order), so do BC and CB, CA and AC, AD and DA, BD and DB, and CD and DC. Listing the 12 ordered arrangements from before — AB, BA, BC, CB, CA, AC, AD, DA, BD, DB, CD, DC — and collapsing each such matching pair down to a single group, only 6 genuinely distinct GROUPS remain: $\{A,B\}, \{B,C\}, \{C,A\}, \{A,D\}, \{B,D\}, \{C,D\}$. This count of 6 is called the combination number of selecting a group of 2 from 4 persons, and is denoted ${}^4C_2$ — since ${}^4P_2=12$ (the ordered count) and each unordered group corresponds to exactly $2!=2$ ordered versions of itself, $12/2!=6$ is exactly the ${}^4C_2$ value.

This motivates the formal Definition: a combination of a set of $n$ distinct objects, taken $r$ at a time without repetition, is an $r$-element SUBSET of those $n$ objects — with the accompanying Note that, unlike a permutation, the order of the elements WITHIN the selected subset is entirely immaterial.

This is generalised immediately: to choose a team of 3 players from a set of 8 different players, first count the ORDERED selections, ${}^8P_3$ — every distinct ordered arrangement of 3 chosen players. But since any FIXED set of 3 players corresponds to $3!$ different ordered arrangements of THAT same set (the 3 players can be listed in any of $3!$ orders), dividing ${}^8P_3$ by $3!$ removes this over-counting and gives the true number of unordered TEAMS: $\dfrac{{}^8P_3}{3!} = \dfrac{8!}{(8-3)!\,3!} = \dfrac{8!}{5!\,3!}$.

The general notation is then fixed: from $n$ distinct objects, the number of ways of selecting a group (or set) of $r$ objects, without considering order, is denoted ${}^nC_r$ (also written $C(n,r)$ or $nC_r$) — it is 'the number of combinations of $r$ objects from $n$ distinct objects'.

Theorem. ${}^nC_r = \dfrac{n!}{(n-r)!\,r!}.$ …