Difference between revisions of "Complementary counting"
Etmetalakret (talk | contribs) |
Etmetalakret (talk | contribs) |
||
| Line 1: | Line 1: | ||
| − | In [[combinatorics]], '''Complementary counting''' is a | + | 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]] | ||
| − | |||
Revision as of 15: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 
is a subset of 
, complementary counting exploits the property that 
, where 
is the complement of . In most instances, though, 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
