Complementary counting

Revision as of 16:37, 18 May 2021 by Etmetalakret (talk | contribs)

In combinatorics, complementary counting is a counting method where one counts what they don't want, then subtracts that from the total number of possibilities. In problems that involve complex or tedious casework, complementary counting is often a far simpler approach. A large hint that complementary counting may lead to a quick solution is the phrase "not" or "at least" within a problem statement.

More formally, if $B$ is a subset of $A$, complementary counting exploits the property that $|B| = |A| - |B'|$, where $B'$ is the complement of $B$. In most instances, though, $A$ is obvious from context.

Video

This is a video explaining the basics of casework, complementary counting, and overcounting (more specifically, the Principle of Inclusion-Exclusion): https://youtu.be/Zhsb5lv6jCI

Examples

Introductory

Intermediate

See also