Double counting

Double counting is a proof method from the field of counting combinatorics , but it is also used in other areas. The principle is to find the thickness of a set in two different ways. The two results must then be the same so that an equation is obtained.

application

The principle of proof is often used to simplify a given expression. The difficulty then is to find a suitable set whose power is on the one hand the same as the given expression, but which on the other hand can also be counted in another way that leads to a simpler formula. Such proofs are often very brief and easy to understand, as there are often no complex mathematical tools required. On the other hand, it often takes a lot of creativity to find them. Therefore, tasks that are based on this principle are often asked in mathematical student competitions .

Examples

Binomial coefficients

The method can be used to derive many equations with binomial coefficients . As an example, the equation

${\displaystyle {n \choose m}{m \choose k}={n \choose k}{n-k \choose m-k}}$

serve. To prove this, we consider the number of possibilities from a group of people to select a committee of people and from these in turn a sub-committee of people. ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle k}$

• On the one hand, we can first select the committee. There are ways to do this . Then we determine the subcommittee. There are options for this - regardless of the choice of committee - so that the total number corresponds to the left side of the above formula. ${\displaystyle {\tbinom {n}{m}}}$ ${\displaystyle {\tbinom {m}{k}}}$

• On the other hand, we can first determine the subcommittee, what there are possibilities for. Then we need to select the remaining members of the committee from among the remaining people. There are ways to do this, so this method gives the right side of the equation as the total number of ways. ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle m-k}$ ${\displaystyle n-k}$ ${\displaystyle {\tbinom {n-k}{m-k}}}$

Hence, the two sides of the formula are actually the same, the equation has been proven by counting twice.

Power sums

The Faulhaber's formula for calculating power of sums can be double-counting derive an example here for the sum of the first square numbers. To do this, we consider the power of the crowd ${\displaystyle n}$

${\displaystyle M=\{(x,y,z)\in \mathbb {N} ^{3}|1\leq x,y,z\leq n+1,x<z,y<z\}}$

the triplet of natural numbers between and where the last entry is the largest. For there are possibilities for and independently of each other , so that the quantity has the power ${\displaystyle 1}$ ${\displaystyle n+1}$ ${\displaystyle z=k+1}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle k}$

${\displaystyle |M|=\sum _{k=1}^{n}k^{2}}$

has, so just the amount you are looking for. The thickness can also be determined in other ways. For this we distinguish three cases: , and . In the first case there are possibilities to choose values ​​for , in the other two in each case . So it applies ${\displaystyle x=y<z}$ ${\displaystyle x<y<z}$ ${\displaystyle y<x<z}$ ${\displaystyle {\tbinom {n+1}{2}}}$ ${\displaystyle (x,y,z)}$ ${\displaystyle {\tbinom {n+1}{3}}}$

${\displaystyle |M|=\sum _{k=1}^{n}k^{2}={n+1 \choose 2}+2{n+1 \choose 3}={\frac {1}{3}}n^{3}+{\frac {1}{2}}n^{2}+{\frac {1}{6}}n}$.

Similarly, the sums of higher powers can be determined with longer tuples .

swell

• Martin Aigner , Günter M. Ziegler : The book of evidence . Springer, Berlin 2004, ISBN 3-540-40185-7 . Chapter 25: Drawer Principle and Double Counting, Chapter 30: Cayley's Formula for the Number of Trees.
• Arthur Engel: Problem Solving Strategies. Springer 1998, ISBN 0-387-98219-1 . Chapter 5: Enumerative Combinatorics.