Difference between revisions of "Complementary counting"
Etmetalakret (talk | contribs) |
Etmetalakret (talk | contribs) |
||
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 | + | 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. |
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. |
Revision as of 15:34, 18 May 2021
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.
More formally, if is a subset of , complementary counting exploits the property that , where is the complement of . In most instances, though, is obvious from context.
Contents
[hide]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