Double counting (proof technique)

Double counting is a method of proof in the field of enumerative combinatorics, but which in other fields to apply. The principle is to determine the cardinality of a set of two ways. The two results must then be the same, so that we obtain an equation.

Application

The proof of principle is commonly used to facilitate a given expression. The difficulty is then to find a suitable set whose cardinality of a hand is equal to the given expression, which can be counted in a different way, on the other hand, leads to a simpler formula. Such proofs are often very short and easy to understand, since often no complex mathematical tools are necessary. In contrast, however, often requires a lot of creativity to find them. Therefore, tasks that are based on this principle, also often found in mathematical student competitions.

Examples

Binomial coefficients

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

Serve. For the proof we consider the number of ways a group of people a committee made ​​up of individuals and, from these, a sub-committee to select persons.

  • On the one hand, we can only select the committee. There are options. Then we determine the sub-committee. For this purpose there is - independent of the choice of the committee - each ways, so that the total number corresponds to just the left side of the above formula.
  • On the other hand, we can first determine the sub-committee, to which there are options. We then need to select the remaining members of the Committee from among the remaining individuals. There are ways, so that the right side of the equation gives the total number of possibilities in this method.

Consequently, the two sides of the formula are actually the same, the equation was demonstrated by double- counting.

Power sums

The Faulhabersche formula for calculating power sums can be derived with double-counting, exemplified here for the sum of the first square numbers. For this we consider the cardinality of the set

Of the triples of natural numbers between and, where the last entry is the largest. For there to and independently of each other ways, so that the amount of the thickness

Has, so just the needed number. The thickness can be determined but also in other ways. We distinguish three cases: , and. In the first case, there are ways to choose values ​​for, in the other two each. It is therefore

Analog can be determined with longer tuples also the sums of higher powers.

Swell

  • Martin Aigner, Günter M. Ziegler: The Book of Evidence. Springer, Berlin 2004, ISBN 3-540-40185-7. Chapter 25: pigeonhole principle and double counting, Chapter 30: Cayles formula for the number of trees.
  • Arthur Engel: Problem Solving Strategies. Springer 1998, ISBN 0-387-98219-1. Chapter 5: Enumerative Combinatorics.
  • Proof ( mathematics)
  • Combinatorics
246687
de