组合数学 (Fall 2011)/Sieve methods

From EtoneWiki
Jump to: navigation, search

Principle of Inclusion-Exclusion

Let and be two finite sets. The cardinality of their union is

.

For three sets , , and , the cardinality of the union of these three sets is computed as

.

This is illustrated by the following figure.

Inclusion-exclusion.png

Generally, the Principle of Inclusion-Exclusion states the rule for computing the union of finite sets , such that


In combinatorial enumeration, the Principle of Inclusion-Exclusion is usually applied in its complement form.

Let be subsets of some finite set . Here is some universe of combinatorial objects, whose cardinality is easy to calculate (e.g. all strings, tuples, permutations), and each contains the objects with some specific property (e.g. a "pattern") which we want to avoid. The problem is to count the number of objects without any of the properties. We write . The number of objects without any of the properties is

For an , we denote

with the convention that . The above equation is stated as:

Principle of Inclusion-Exclusion
Let be a family of subsets of . Then the number of elements of which lie in none of the subsets is
.

Let . Conventionally, . The principle of inclusion-exclusion can be expressed as

Surjections

In the twelvefold way, we discuss the counting problems incurred by the mappings . The basic case is that elements from both and are distinguishable. In this case, it is easy to count the number of arbitrary mappings (which is ) and the number of injective (one-to-one) mappings (which is ), but the number of surjective is difficult. Here we apply the principle of inclusion-exclusion to count the number of surjective (onto) mappings.

Theorem
The number of surjective mappings from an -set to an -set is given by
.
Proof.

Let be the set of mappings from to . Then .

For , let be the set of mappings that none of is mapped to , i.e. , thus .

More generally, for , contains the mappings . And .

A mapping is surjective if lies in none of . By the principle of inclusion-exclusion, the number of surjective is

.

Let . The theorem is proved.

Recall that, in the twelvefold way, we establish a relation between surjections and partitions.

  • Surjection to ordered partition:
For a surjective , is an ordered partition of .
  • Ordered partition to surjection:
For an ordered -partition of , we can define a function by letting if and only if . is surjective since as a partition, none of is empty.

Therefore, we have a one-to-one correspondence between surjective mappings from an -set to an -set and the ordered -partitions of an -set.

The Stirling number of the second kind is the number of -partitions of an -set. There are ways to order an -partition, thus the number of surjective mappings is . Combining with what we have proved for surjections, we give the following result for the Stirling number of the second kind.

Proposition
.

Derangements

We now count the number of bijections from a set to itself with no fixed points. This is the derangement problem.

For a permutation of , a fixed point is such an that . A derangement of is a permutation of that has no fixed points.

Theorem
The number of derangements of given by
.
Proof.

Let be the set of all permutations of . So .

Let be the set of permutations with fixed point ; so . More generally, for any , , and , since permutations in fix every point in and permute the remaining points arbitrarily. A permutation is a derangement if and only if it lies in none of the sets . So the number of derangements is

By Taylor's series,

.

It is not hard to see that is the closest integer to .

Therefore, there are about fraction of all permutations with no fixed points.

Permutations with restricted positions

We introduce a general theory of counting permutations with restricted positions. In the derangement problem, we count the number of permutations that . We now generalize to the problem of counting permutations which avoid a set of arbitrarily specified positions.

It is traditionally described using terminology from the game of chess. Let , called a board. As illustrated below, we can think of as a chess board, with the positions in marked by "".

Solid white.svg a b c d e f g h Solid white.svg
8 a8 __ b8 cross c8 cross d8 __ e8 cross f8 __ g8 __ h8 cross 8
7 a7 cross b7 __ c7 __ d7 cross e7 __ f7 __ g7 cross h7 __ 7
6 a6 cross b6 __ c6 cross d6 cross e6 __ f6 cross g6 cross h6 __ 6
5 a5 __ b5 cross c5 __ d5 __ e5 cross f5 __ g5 cross h5 __ 5
4 a4 cross b4 __ c4 __ d4 __ e4 cross f4 cross g4 cross h4 __ 4
3 a3 __ b3 cross c3 __ d3 cross e3 __ f3 __ g3 __ h3 cross 3
2 a2 __ b2 __ c2 cross d2 __ e2 cross f2 __ g2 __ h2 cross 2
1 a1 cross b1 __ c1 __ d1 cross e1 __ f1 cross g1 __ h1 __ 1
Solid white.svg a b c d e f g h Solid white.svg

For a permutation of , define the graph as

This can also be viewed as a set of marked positions on a chess board. Each row and each column has only one marked position, because is a permutation. Thus, we can identify each as a placement of rooks (“城堡”,规则同中国象棋里的“车”) without attacking each other.

For example, the following is the of such that .

Solid white.svg a b c d e f g h Solid white.svg
8 a8 white rook b8 __ c8 __ d8 __ e8 __ f8 __ g8 __ h8 __ 8
7 a7 __ b7 white rook c7 __ d7 __ e7 __ f7 __ g7 __ h7 __ 7
6 a6 __ b6 __ c6 white rook d6 __ e6 __ f6 __ g6 __ h6 __ 6
5 a5 __ b5 __ c5 __ d5 white rook e5 __ f5 __ g5 __ h5 __ 5
4 a4 __ b4 __ c4 __ d4 __ e4 white rook f4 __ g4 __ h4 __ 4
3 a3 __ b3 __ c3 __ d3 __ e3 __ f3 white rook g3 __ h3 __ 3
2 a2 __ b2 __ c2 __ d2 __ e2 __ f2 __ g2 white rook h2 __ 2
1 a1 __ b1 __ c1 __ d1 __ e1 __ f1 __ g1 __ h1 white rook 1
Solid white.svg a b c d e f g h Solid white.svg

Now define

Interpreted in chess game,

  • : a set of marked positions in an chess board.
  • : the number of ways of placing non-attacking rooks on the chess board such that none of these rooks lie in .
  • : number of ways of placing non-attacking rooks on .

Our goal is to count in terms of . This gives the number of permutations avoid all positions in a .

Theorem
.
Proof.

For each , let be the set of permutations whose -th position is in .

is the number of permutations avoid all positions in . Thus, our goal is to count the number of permutations in none of for .

For each , let , which is the set of permutations such that for all . Due to the principle of inclusion-exclusion,

.

The next observation is that

,

because we can count both sides by first placing non-attacking rooks on and placing additional non-attacking rooks on in ways.

Therefore,

.

Derangement problem

We use the above general method to solve the derange problem again.

Take as the chess board. A derangement is a placement of non-attacking rooks such that none of them is in .

Solid white.svg a b c d e f g h Solid white.svg
8 a8 cross b8 __ c8 __ d8 __ e8 __ f8 __ g8 __ h8 __ 8
7 a7 __ b7 cross c7 __ d7 __ e7 __ f7 __ g7 __ h7 __ 7
6 a6 __ b6 __ c6 cross d6 __ e6 __ f6 __ g6 __ h6 __ 6
5 a5 __ b5 __ c5 __ d5 cross e5 __ f5 __ g5 __ h5 __ 5
4 a4 __ b4 __ c4 __ d4 __ e4 cross f4 __ g4 __ h4 __ 4
3 a3 __ b3 __ c3 __ d3 __ e3 __ f3 cross g3 __ h3 __ 3
2 a2 __ b2 __ c2 __ d2 __ e2 __ f2 __ g2 cross h2 __ 2
1 a1 __ b1 __ c1 __ d1 __ e1 __ f1 __ g1 __ h1 cross 1
Solid white.svg a b c d e f g h Solid white.svg

Clearly, the number of ways of placing non-attacking rooks on is . We want to count , which gives the number of ways of placing non-attacking rooks such that none of these rooks lie in .

By the above theorem

Problème des ménages

Suppose that in a banquet, we want to seat couples at a circular table, satisfying the following constraints:

  • Men and women are in alternate places.
  • No one sits next to his/her spouse.

In how many ways can this be done?

(For convenience, we assume that every seat at the table marked differently so that rotating the seats clockwise or anti-clockwise will end up with a different solution.)

First, let the ladies find their seats. They may either sit at the odd numbered seats or even numbered seats, in either case, there are different orders. Thus, there are ways to seat the ladies.

After sitting the wives, we label the remaining places clockwise as . And a seating of the husbands is given by a permutation of defined as follows. Let be the seat of the husband of he lady sitting at the -th place.

It is easy to see that satisfies that and , and every permutation with these properties gives a feasible seating of the husbands. Thus, we only need to count the number of permutations such that .

Take as the chess board. A permutation which defines a way of seating the husbands, is a placement of non-attacking rooks such that none of them is in .

Solid white.svg a b c d e f g h Solid white.svg
8 a8 cross b8 cross c8 __ d8 __ e8 __ f8 __ g8 __ h8 __ 8
7 a7 __ b7 cross c7 cross d7 __ e7 __ f7 __ g7 __ h7 __ 7
6 a6 __ b6 __ c6 cross d6 cross e6 __ f6 __ g6 __ h6 __ 6
5 a5 __ b5 __ c5 __ d5 cross e5 cross f5 __ g5 __ h5 __ 5
4 a4 __ b4 __ c4 __ d4 __ e4 cross f4 cross g4 __ h4 __ 4
3 a3 __ b3 __ c3 __ d3 __ e3 __ f3 cross g3 cross h3 __ 3
2 a2 __ b2 __ c2 __ d2 __ e2 __ f2 __ g2 cross h2 cross 2
1 a1 cross b1 __ c1 __ d1 __ e1 __ f1 __ g1 __ h1 cross 1
Solid white.svg a b c d e f g h Solid white.svg

We need to compute , the number of ways of placing non-attacking rooks on . For our choice of , is the number of ways of choosing points, no two consecutive, from a collection of points arranged in a circle.

We first see how to do this in a line.

Lemma
The number of ways of choosing non-consecutive objects from a collection of objects arranged in a line, is .
Proof.

We draw a line of black points, and then insert red points into the spaces between the black points (including the beginning and end).

This gives us a line of points, and the red points specifies the chosen objects, which are non-consecutive. The mapping is 1-1 correspondence. There are ways of placing red points into spaces.

The problem of choosing non-consecutive objects in a circle can be reduced to the case that the objects are in a line.

Lemma
The number of ways of choosing non-consecutive objects from a collection of objects arranged in a circle, is .
Proof.

Let be the desired number; and let be the number of ways of choosing non-consecutive points from points arranged in a circle, next coloring the points red, and then coloring one of the uncolored point blue.

Clearly, .

But we can also compute as follows:

  • Choose one of the points and color it blue. This gives us ways.
  • Cut the circle to make a line of points by removing the blue point.
  • Choose non-consecutive points from the line of points and color them red. This gives ways due to the previous lemma.

Thus, . Therefore we have the desired number .

By the above lemma, we have that . Then apply the theorem of counting permutations with restricted positions,

This gives the number of ways of seating the husbands after the ladies are seated. Recall that there are ways of seating the ladies. Thus, the total number of ways of seating couples as required by problème des ménages is

The Euler totient function

Two integers are said to be relatively prime if their greatest common diviser . For a positive integer , let be the number of positive integers from that are relative prime to . This function, called the Euler function or the Euler totient function, is fundamental in number theory.

We now derive a formula for this function by using the principle of inclusion-exclusion.

Theorem (The Euler totient function)

Suppose is divisible by precisely different primes, denoted . Then

.
Proof.

Let be the universe. The number of positive integers from which is divisible by some , is .

is the number of integers from which is not divisible by any . By principle of inclusion-exclusion,

Möbius inversion

Posets

A partially ordered set or poset for short is a set together with a binary relation denoted (or just if no confusion is caused), satisfying

  • (reflexivity) For all .
  • (antisymmetry) If and , then .
  • (transitivity) If and , then .

We say two elements and are comparable if or ; otherwise and are incomparable.

Notation
  • means .
  • means and .
  • means .

The Möbius function

Let be a finite poset. Consider functions in form of defined over domain . It is convenient to treat such functions as matrices whose rows and columns are indexed by .

Incidence algebra of poset
Let
be the class of such that is non-zero only for .
Treating as matrix, it is trivial to see that is closed under addition and scalar multiplication, that is,
  • if then ;
  • if then for any ;
where are treated as matrices.
With this spirit, it is natural to define the matrix multiplication in . For ,
.
The second equation is due to that for , for all other than , is zero.
By the transitivity of relation , it is also easy to prove that is closed under matrix multiplication (the detailed proof is left as an exercise). Therefore, is closed under addition, scalar multiplication and matrix multiplication, so we have an algebra , called incidence algebra, over functions on .
Zeta function and Möbius function
A special function in is the so-called zeta function , defined as
As a matrix (or more accurately, as an element of the incidence algebra), is invertible and its inversion, denoted by , is called the Möbius function. More precisely, is also in the incidence algebra , and where is the identity matrix (the identity of the incidence algebra ).

There is an equivalent explicit definition of Möbius function.

Definition (Möbius function)

To see the equivalence between this definition and the inversion of zeta function, we may have the following proposition, which is proved by directly evaluating .

Proposition
For any ,
Proof.

It holds that

.

On the other hand, , i.e.

The proposition follows.

Note that , which gives the above inductive definition of Möbius function.

Computing Möbius functions

We consider the simple poset , where is the total order. It follows directly from the recursive definition of Möbius function that

Usually for general posets, it is difficult to directly compute the Möbius function from its definition. We introduce a rule helping us compute the Möbius function by decomposing the poset into posets with simple structures.

Theorem (the product rule)
Let and be two finite posets, and be the poset resulted from Cartesian product of and , where for all , if and only if and . Then
.
Proof.

We use the recursive definition

to prove the equation in the theorem.

If , then and . It is easy to see that both sides of the equation are 1. If , then either or . It is also easy to see that both sides are 0.

The only remaining case is that , in which case either or .

where the last two equations are due to the proposition for . Thus

.

By induction, assume that the equation is true for all . Then

which complete the proof.

Poset of subsets
Consider the poset defined by all subsets of a finite universe , that is , and for , if and only if .
Möbius function for subsets
The Möbius function for the above defined poset is that for ,
Proof.

We can equivalently represent each by a boolean string , where if and only if .

For each element , we can define a poset with . By definition of Möbius function, the Möbius function of this elementary poset is given by , and .

The poset of all subsets of is the Cartesian product of all , . By the product rule,

Note that the poset is actually the Boolean algebra of rank . The proof relies only on that the fact that the poset is a Boolean algebra, thus the theorem holds for Boolean algebra posets.
Posets of divisors
Consider the poset defined by all devisors of a positive integer , that is , and for , if and only if .
Möbius function for divisors
The Möbius function for the above defined poset is that for that and ,
Proof.

Denote . Represent by a tuple . Every corresponds in this way to a tuple with for all .

Let be the poset with being the total order. The poset of divisors of is thus isomorphic to the poset constructed by the Cartesian product of all , . Then

Principle of Möbius inversion

We now introduce the the famous Möbius inversion formula.

Möbius inversion formula
Let be a finite poset and its Möbius function. Let . Then
,
if and only if
.

The functions are vectors. Evaluate the matrix multiplications and as follows:

,

and

.

The Möbius inversion formula is nothing but the following statement

,

which is trivially true due to by basic linear algebra.

The following dual form of the inversion formula is also useful.

Möbius inversion formula, dual form
Let be a finite poset and its Möbius function. Let . Then
,
if and only if
.

To prove the dual form, we only need to evaluate the matrix multiplications on left:

.
Principle of Inclusion-Exclusion
Let . For any ,
  • let be the number of elements that belongs to exactly the sets and to no others, i.e.
;
  • let .
For any , the following relation holds for the above defined and :
.
Applying the dual form of the Möbius inversion formula, we have that for any ,
,
where the Möbius function is for the poset of all subsets of , ordered by , thus it holds that for . Therefore,
.
We have a formula for the number of elements with exactly those properties for any . For the special case that , is the number of elements satisfying no property of , and
which gives precisely the Principle of Inclusion-Exclusion.
Möbius inversion formula for number theory
The number-theoretical Möbius inversion formula is stated as such: Let be a positive integer,
for all
if and only if
for all ,
where is the number-theoretical Möbius function, defined as
The number-theoretical Möbius inversion formula is just a special case of the Möbius inversion formula for posets, when the poset is the set of divisors of , and for any , if .

Reference

  • Stanley, Enumerative Combinatorics, Volume 1, Chapter 2.
  • van Lin and Wilson, A course in combinatorics, Chapter 10, 25.