enumerative combinatorics
Enumerative combinatorics deals with the question: if we know that a set is finite, how can we determine the exact number of elements that contains?
Basic principles and techniques of enumerative combinatorics include:
-
•
the addition principle;
- •
-
•
the involution principle;
-
•
the inclusion-exclusion principle
; and
-
•
the use of generating functions.
The principles listed above are disarmingly simple and seemingly
obvious. Nonetheless, when used properly they are powerful
tools for producing bijective proofs of combinatorial identities. On
the other hand, while generating functions can frequently be used to
give quick proofs of identities, it is sometimes difficult to extract
combinatorial proofs from such proofs.
The most fundamental principle of enumerative combinatorics and the
basis of all counting is the addition principle. It says that
if is a finite set, then
More generally, if , then
By induction on , we also get
As an application of the addition principle, we prove the multiplication principle.
Proposition 1.
Multiplication principle. If and are finite sets, then
Proof.
By the addition principle,
But we can write as the disjoint union
The projection map is a bijection, so . Hence it follows that
which completes the proof.
∎
The involution principle says that if is an involution, then for any , . The following example illustrates the involution principle.
Proposition 2.
Enumerating elements of the powerset. Let and let be the powerset of . Then the cardinality of is .
Proof.
In other words, is the symmetric difference of and
— if is an element of , we remove it, and if is
not an element of , we insert it. The function is an
involution, hence a bijection. Now notice that and . In
other words,
Since is a bijection, this implies that
By induction on we obtain
Now , so . Thus , implying that
which is what we wanted to show. ∎
As we have seen above, it is possible to use the addition principle to
count the number of elements in the disjoint union of finite sets.
But what if we want to count the number of elements in a non-disjoint
union of finite sets? The inclusion-exclusion principle gives
us a way to do this. A common way of stating the inclusion-exclusion
principle is as the following proposition.
Proposition 3.
Inclusion-exclusion principle. Let be finite sets. Then
The formula in this proposition uses negative numbers. But the core
of the inclusion-exclusion principle is a statement about natural
numbers.
Proposition 4.
Proof.
By the addition principle,
Now observe that . So by a second application of the addition principle,
Hence . ∎
Title | enumerative combinatorics |
---|---|
Canonical name | EnumerativeCombinatorics |
Date of creation | 2013-03-22 16:45:58 |
Last modified on | 2013-03-22 16:45:58 |
Owner | mps (409) |
Last modified by | mps (409) |
Numerical id | 14 |
Author | mps (409) |
Entry type | Topic |
Classification | msc 05-00 |
Related topic | DijkstrasAlgorithm |
Related topic | RuleOfProduct |