Properties of combinations

This sub-section lists nine standard Properties of Combinations and then works through seven varied solved examples that make heavy use of them.

Property 1 (Complement Property). ${}^nC_{n-r} = {}^nC_r.$ Proof (sketched in the text): ${}^nC_{n-r} = \dfrac{n!}{(n-r)!\,[n-(n-r)]!} = \dfrac{n!}{(n-r)!\,r!} = {}^nC_r.$ This holds for $0<r\le n$, and reflects the fact that CHOOSING which $r$ objects to include in a selection is exactly equivalent to CHOOSING which $n-r$ objects to leave out.

Property 2 (Boundary values). ${}^nC_0 = \dfrac{n!}{n!\,0!} = \dfrac{n!}{n!\times1} = 1,$ since $0!=1$ by definition (as stated in §3.4) — there is exactly one way to select NONE of the $n$ objects (the empty selection). By the complement property, ${}^nC_n={}^nC_0=1$ as well — there is exactly one way to select ALL $n$ objects.

Property 3. If ${}^nC_r={}^nC_s$, then EITHER $s=r$ (the trivial case) OR $s=n-r$ (via the complement property) — this dual possibility is the key tool used to solve 'find $n$' equations of the form ${}^nC_x={}^nC_y$ throughout the exercises.

Property 4. ${}^nC_r = \dfrac{{}^nP_r}{r!},$ directly restating the derivation of §3.6 — useful whenever both a permutation-count and a combination-count for the same $n,r$ are known or needed together, since dividing one by the other isolates $r!$ (and hence $r$) immediately.

Property 5 (Pascal's Rule). ${}^nC_r + {}^nC_{r-1} = {}^{n+1}C_r.$ This describes how combinations 'build upward': the number of ways to choose $r$ objects from $n+1$ objects splits into those selections that EXCLUDE one particular object (a choice of $r$ from the remaining $n$, i.e. ${}^nC_r$) and those that INCLUDE it (a choice of the remaining $r-1$ from the other $n$, i.e. ${}^nC_{r-1}$) — together accounting for every possible selection exactly once. This rule is what allows a running SUM of adjacent combinations to be 'telescoped' down into a single binomial coefficient, and, read in reverse, allows a DIFFERENCE of combinations sharing a lower index to collapse similarly.

Property 6. ${}^nC_0 + {}^nC_1 + \cdots + {}^nC_n = 2^n,$ the total number of subsets (of every possible size, including the empty set and the full set) of an $n$-element set.

Property 7. ${}^nC_0 + {}^nC_2 + {}^nC_4 + \cdots = {}^nC_1 + {}^nC_3 + {}^nC_5 + \cdots = 2^{(n-1)},$ i.e. the EVEN-indexed and ODD-indexed combinations of a given $n$ each separately sum to exactly half of $2^n$.

Property 8. ${}^nC_r = \dfrac{n}{r}\times{}^{(n-1)}C_{(r-1)} = \dfrac{n}{r}\times\dfrac{n-1}{r-1}\times{}^{(n-2)}C_{(r-2)} = \cdots,$ a telescoping product identity expressing ${}^nC_r$ as a chain of ratios times a smaller and smaller combination.

Property 9 (Maximum value). ${}^nC_r$ takes its GREATEST value (i) at $r=\dfrac{n}{2}$, when $n$ is even; or (ii) at EITHER $r=\dfrac{n-1}{2}$ or $r=\dfrac{n+1}{2}$ (both give the same, equally-maximal value), when $n$ is odd.

Solved Example 1. Find the value of (i) ${}^7C_3$, (ii) ${}^{10}C_7$, (iii) ${}^{52}C_3$. (i) ${}^7C_3=\dfrac{7!}{3!\,4!}=\dfrac{7\times6\times5\times4!}{3\times2\times1\times4!}=\dfrac{7\times6\times5}{3\times2\times1}=35.$ (ii) Using the complement property, ${}^{10}C_7={}^{10}C_3=\dfrac{10\times9\times8}{3\times2\times1}=120$. (iii) ${}^{52}C_3=\dfrac{52\times51\times50}{3\times2\times1}=22100.$

Solved Example 2. Find $n$ and $r$ if ${}^nC_{r-1}:{}^nC_r:{}^nC_{r+1}=14:8:3$. From the first two terms of the ratio, $\dfrac{{}^nC_{r-1}}{{}^nC_r}=\dfrac{14}{8}=\dfrac{7}{4}$, and using the standard identity $\dfrac{{}^nC_{r-1}}{{}^nC_r}=\dfrac{r}{n-r+1}$, this gives $\dfrac{r}{n-r+1}=\dfrac{7}{4}$, i.e. $4r=7(n-r+1)$. From the last two terms, $\dfrac{{}^nC_r}{{}^nC_{r+1}}=\dfrac{8}{3}$, and using $\dfrac{{}^nC_r}{{}^nC_{r+1}}=\dfrac{r+1}{n-r}$, this gives $3(r+1)=8(n-r)$. Solving these two simultaneous equations gives $r=7$ and $n=10$.

Solved Example 3. There are $n$ points in a plane. Find the number of straight lines and triangles obtainable by joining these points, if (i) no three points are collinear, (ii) $p$ of the points are collinear ($p\ge3$). (i) Any 2 of the $n$ points determine a distinct straight line (since no three are collinear to cause overlap), so the number of lines is ${}^nC_2$; similarly, any 3 non-collinear points determine a valid triangle, so the number of triangles is ${}^nC_3$. (ii) If $p$ of the $n$ points are collinear, treating them (incorrectly) as non-collinear would give ${}^pC_2$ 'lines' among just those $p$ points — but since they are actually all on ONE line, these ${}^pC_2$ pairs collapse to just 1 real line, so ${}^pC_2-1$ 'extra' lines have been over-counted and must be subtracted from the total: number of straight lines $={}^nC_2-({}^pC_2-1)$. For triangles, any 3 points chosen entirely from the $p$ collinear points form NO triangle at all (they're collinear, hence degenerate), so all ${}^pC_3$ such triples must simply be subtracted (nothing is added back, unlike the lines case): number of triangles $={}^nC_3-{}^pC_3$. …