Difference between revisions of "Complementary counting"

Line 1: Line 1:
In [[combinatorics]], '''Complementary counting''' is a method of [[counting]] 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.
+
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 <math>B</math> is a subset of <math>A</math>, complementary counting exploits the property that <math>|B| = |A| - |B'|</math>, where <math>B'</math> is the [[complement]] of <math>B</math>. In most instances, though, <math>A</math> is obvious from context.
 
More formally, if <math>B</math> is a subset of <math>A</math>, complementary counting exploits the property that <math>|B| = |A| - |B'|</math>, where <math>B'</math> is the [[complement]] of <math>B</math>. In most instances, though, <math>A</math> is obvious from context.
Line 21: Line 21:
 
* [[Overcounting]]
 
* [[Overcounting]]
  
 +
[[Category:Combinatorics]]
 
[[Category:Definition]]
 
[[Category:Definition]]
[[Category:Combinatorics]]
 

Revision as of 16:34, 18 May 2021

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