= Double counting
{disambiguate=proof technique}
{wiki}
= Double counting
{synonym}
Double counting establishes an identity by computing the <cardinality> of the same <finite set> in two ways. The useful step is to identify exactly what the members of that collection are; an algebraic equality then records two legitimate ways to organize them.
Take the <ordered pairs> $(S,x)$ where $S$ is a $k$-element <subset> of an $n$-element <set> and $x\in S$ is marked. Choosing $S$ first gives $k\binom nk$ pairs. Choosing $x$ first leaves $k-1$ members to choose from the other $n-1$, giving $n\binom{n-1}{k-1}$. Hence
$$
k\binom nk=n\binom{n-1}{k-1}\qquad(1\leq k\leq n).
$$
For five people and two-person teams, both counts give $20$: ten teams with two choices of a marked member, or five choices of that member with four choices of a teammate. The identity is explained by the <bijection> between these descriptions, rather than merely verified through <factorials>.
Back to article page
