Difference between revisions of "Complementary counting"

Revision as of 16:39, 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^c|$ , where $B^c$ 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

2004 AIME I Problems/Problem 15

@@ Line 1: / Line 1: @@
-'''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 overly complicated and tedious [[casework]], complementary counting is often a far easier and more efficient approach. Within a problem statement, a large hint that complementary counting may lead to a quick solution is the phrase "not" or "at least".
+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^c|</math>, where <math>B^c</math> is the [[complement]] of <math>B</math>. In most instances, though, <math>A</math> is obvious from context.
 ==Video==
@@ Line 21: / Line 21: @@
 * [[Overcounting]]
+[[Category:Combinatorics]]
 [[Category:Definition]]
-[[Category:Combinatorics]]

Page

Toolbox

Search