Editing Double counting (proof technique) (section)

==See also==
===Additional examples===
* [[Vandermonde's identity]], another identity on sums of binomial coefficients that can be proven by double counting.{{sfn|Joshi|2015}}
* [[Square pyramidal number]]. The equality between the sum of the first <math>n</math> [[square number]]s and a cubic polynomial can be shown by double counting the triples of numbers <math>x</math>, <math>y</math>, and <math>z</math> where <math>z</math> is larger than either of the other two numbers.
* [[Lubell–Yamamoto–Meshalkin inequality]]. Lubell's proof of this result on set families is a double counting argument on [[permutation]]s, used to prove an [[Inequality (mathematics)|inequality]] rather than an equality.
* [[Erdős–Ko–Rado theorem]], an upper bound on intersecting families of sets, proven by [[Gyula O. H. Katona]] using a double counting inequality.{{sfn|Aigner|Ziegler|1998}}
* [[Proofs of Fermat's little theorem]]. A [[divisibility]] proof by double counting: for any [[Prime number|prime]] <math>p</math> and natural number <math>A</math>, there are <math>A^p-A</math> length-<math>p</math> words over an <math>A</math>-symbol alphabet having two or more distinct symbols. These may be grouped into sets of <math>p</math> words that can be transformed into each other by [[circular shift]]s; these sets are called [[necklace (combinatorics)|necklaces]]. Therefore, <math>A^p-A=p\cdot{}</math>(number of necklaces) and is divisible by <math>p</math>.{{sfn|Joshi|2015}}
* [[Proofs of quadratic reciprocity]]. A proof by [[Gotthold Eisenstein|Eisenstein]] derives another important [[number theory|number-theoretic]] fact by double counting lattice points in a triangle.

===Related topics===
* [[Bijective proof]]. Where double counting involves counting one set in two ways, bijective proofs involve counting two sets in one way, by showing that their elements correspond one-for-one.
* The [[inclusion–exclusion principle]], a formula for the size of a [[Union (set theory)|union]] of sets that may, together with another formula for the same union, be used as part of a double counting argument.