Q.The number of rectangles that a chessboard has $\cdots$

A combination is an unordered selection of objects — $\{A,B,C\}$ and $\{B,A,C\}$ are the same combination, unlike a permutation. The number of ways of choosing $r$ objects (order irrelevant) from $n$ distinct objects is denoted $^nC_r$ ("$n$ choose $r$").

Link to permutations. Every combination of $r$ objects can itself be internally arranged in $r!$ ways, so $^nP_r={}^nC_r\times r!$, giving

Permutation vs. combination, at a glance: a batting line-up of 11 from 15 players is a permutation (order = batting position matters); the team of 11 chosen from 15 is a combination (no roles attached). Distributing 3 distinct prizes is a permutation-style count; distributing 3 identical prizes is a combination-style count.

Standard identities (each provable directly from the $\dfrac{n!}{r!(n-r)!}$ formula):

• $^nC_0={}^nC_n=1$; and $^nC_r=\dfrac{n(n-1)\cdots(n-r+1)}{r!}$.
• Symmetry: $^nC_r={}^nC_{n-r}$ — choosing $r$ to include is the same act as choosing $n-r$ to exclude.
• Injectivity (up to symmetry): if $^nC_x={}^nC_y$, then $x=y$ or $x+y=n$.
• Pascal's rule: $^nC_r+{}^nC_{r-1}={}^{n+1}C_r$ — the count of $r$-subsets of an $(n+1)$-set splits by whether a fixed element is included ($^nC_{r-1}$ ways, then fill the rest from the remaining $n$) or excluded ($^nC_r$ ways).
• Reduction: $^nC_r=\dfrac nr\times{}^{n-1}C_{r-1}$. …