组合数学 (Fall 2011)/Sieve methods and 组合数学 (Fall 2011)/Counting and existence: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
 
imported>WikiSysop
 
Line 1: Line 1:
== Counting arguments ==
=== Shannon's circuit lower bound===
This is a fundamental problem in in Computer Science.


== Principle of Inclusion-Exclusion ==
A '''boolean function''' is a function in the form <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>.
Let <math>A</math> and <math>B</math> be two finite sets. The cardinality of their union is
:<math>|A\cup B|=|A|+|B|-{\color{Blue}|A\cap B|}</math>.
For three sets <math>A</math>, <math>B</math>, and <math>C</math>, the cardinality of the union of these three sets is computed as
:<math>|A\cup B\cup C|=|A|+|B|+|C|-{\color{Blue}|A\cap B|}-{\color{Blue}|A\cap C|}-{\color{Blue}|B\cap C|}+{\color{Red}|A\cap B\cap C|}</math>.
This is illustrated by the following figure.
::[[Image:Inclusion-exclusion.png|200px|border|center]]


Generally, the '''Principle of Inclusion-Exclusion''' states the rule for computing the union of <math>n</math> finite sets <math>A_1,A_2,\ldots,A_n</math>, such that
[http://en.wikipedia.org/wiki/Boolean_circuit Boolean circuit] is a mathematical model of computation.
{{Equation|
Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , x_n</math>. A circuit has a unique node with outdegree zero, called the output node. Every other node is a gate. There are three types of gates: AND, OR (both with indegree two), and NOT (with indegree one).
<math>
\begin{align}
\left|\bigcup_{i=1}^nA_i\right|
&=
\sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|-1}\left|\bigcap_{i\in I}A_i\right|.
\end{align}
</math>
}}
-----


In combinatorial enumeration, the Principle of Inclusion-Exclusion is usually applied in its complement form.
Computations in Turing machines can be simulated by circuits, and any boolean function in '''P''' can be computed by a circuit with polynomially many gates. Thus, if we can find a function in '''NP''' that cannot be computed by any circuit with polynomially many gates, then '''NP'''<math>\neq</math>'''P'''.


Let <math>A_1,A_2,\ldots,A_n\subseteq U</math> be subsets of some finite set <math>U</math>. Here <math>U</math> is some universe of combinatorial objects, whose cardinality is easy to calculate (e.g. all strings, tuples, permutations), and each <math>A_i</math> 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 <math>n</math> properties. We write <math>\bar{A_i}=U-A_i</math>. The number of objects without any of the properties <math>A_1,A_2,\ldots,A_n</math> is
The following theorem due to Shannon says that functions with exponentially large circuit complexity do exist.
{{Equation|
<math>
\begin{align}
\left|\bar{A_1}\cap\bar{A_2}\cap\cdots\cap\bar{A_n}\right|=\left|U-\bigcup_{i=1}^nA_i\right|
&=
|U|+\sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|}\left|\bigcap_{i\in I}A_i\right|.
\end{align}
</math>
}}
For an <math>I\subseteq\{1,2,\ldots,n\}</math>, we denote
:<math>A_I=\bigcap_{i\in I}A_i</math>
with the convention that <math>A_\emptyset=U</math>. The above equation is stated as:
{{Theorem|Principle of Inclusion-Exclusion|
:Let <math>A_1,A_2,\ldots,A_n</math> be a family of subsets of <math>U</math>. Then the number of elements of <math>U</math> which lie in none of the subsets <math>A_i</math> is
::<math>\sum_{I\subseteq\{1,\ldots, n\}}(-1)^{|I|}|A_I|</math>.
}}


Let <math>S_k=\sum_{|I|=k}|A_I|\,</math>. Conventionally, <math>S_0=|A_\emptyset|=|U|</math>. The principle of inclusion-exclusion can be expressed as
{{Theorem
{{Equation|<math>
|Theorem (Shannon 1949)|
S_0-S_1+S_2+\cdots+(-1)^nS_n.
:There is a boolean function <math>f:\{0,1\}^n\rightarrow \{0,1\}</math> with circuit complexity greater than <math>\frac{2^n}{3n}</math>.
</math>
}}
}}
{{Proof|
We first count the number of boolean functions <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>. There are <math>2^{2^n}</math> boolean functions <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>.


=== Surjections ===
Then we count the number of boolean circuit with fixed number of gates.
In the twelvefold way, we discuss the counting problems incurred by the mappings <math>f:N\rightarrow M</math>. The basic case is that elements from both <math>N</math> and <math>M</math> are distinguishable. In this case, it is easy to count the number of arbitrary mappings (which is <math>m^n</math>) and the number of injective (one-to-one) mappings (which is <math>(m)_n</math>), but the number of surjective is difficult. Here we apply the principle of inclusion-exclusion to count the number of surjective (onto) mappings.
Fix an integer <math>t</math>, we count the number of circuits with <math>t</math> gates. By the [http://en.wikipedia.org/wiki/De_Morgan's_laws De Morgan's laws], we can assume that all NOTs are pushed back to the inputs. Each gate has one of the two types (AND or OR), and has two inputs. Each of the inputs to a gate is either a constant 0 or 1, an input variable <math>x_i</math>, an inverted input variable <math>\neg x_i</math>, or the output of another gate; thus, there are at most <math>2+2n+t-1</math> possible gate inputs. It follows that the number of circuits with <math>t</math> gates is at most <math>2^t(t+2n+1)^{2t}</math>.  
{{Theorem|Theorem|
:The number of surjective mappings from an <math>n</math>-set to an <math>m</math>-set is given by
::<math>\sum_{k=1}^m(-1)^{m-k}{m\choose k}k^n</math>.
}}
{{Proof|
Let <math>U=\{f:[n]\rightarrow[m]\}</math> be the set of mappings from <math>[n]</math> to <math>[m]</math>. Then <math>|U|=m^n</math>.  


For <math>i\in[m]</math>, let <math>A_i</math> be the set of mappings <math>f:[n]\rightarrow[m]</math> that none of <math>j\in[n]</math> is mapped to <math>i</math>, i.e. <math>A_i=\{f:[n]\rightarrow[m]\setminus\{i\}\}</math>, thus <math>|A_i|=(m-1)^n</math>.
If <math>t=2^n/3n</math>, then
 
:<math>
More generally, for <math>I\subseteq [m]</math>, <math>A_I=\bigcap_{i\in I}A_i</math> contains the mappings <math>f:[n]\rightarrow[m]\setminus I</math>. And <math>|A_I|=(m-|I|)^n\,</math>.
\frac{2^t(t+2n+1)^{2t}}{2^{2^n}}=o(1)<1,</math>     thus, <math>2^t(t+2n+1)^{2t} < 2^{2^n}.</math>


A mapping <math>f:[n]\rightarrow[m]</math> is surjective if <math>f</math> lies in none of <math>A_i</math>. By the principle of inclusion-exclusion, the number of surjective <math>f:[n]\rightarrow[m]</math> is
Each boolean circuit computes one boolean function. Therefore, there must exist a boolean function <math>f</math> which cannot be computed by any circuits with <math>2^n/3n</math> gates.
:<math>\sum_{I\subseteq[m]}(-1)^{|I|}\left|A_I\right|=\sum_{I\subseteq[m]}(-1)^{|I|}(m-|I|)^n=\sum_{j=0}^m(-1)^j{m\choose j}(m-j)^n</math>.
Let <math>k=m-j</math>. The theorem is proved.
}}
}}


Recall that, in the twelvefold way, we establish a relation between surjections and partitions.
Note that by Shannon's theorem, not only there exists a boolean function with exponentially large circuit complexity, but ''almost all'' boolean functions have exponentially large circuit complexity.
 
* Surjection to ordered partition:
:For a surjective <math>f:[n]\rightarrow[m]</math>, <math>(f^{-1}(0),f^{-1}(1),\ldots,f^{-1}(m-1))</math> is an '''ordered partition''' of <math>[n]</math>.
* Ordered partition to surjection:
:For an ordered <math>m</math>-partition <math>(B_0,B_1,\ldots, B_{m-1})</math> of <math>[n]</math>, we can define a function <math>f:[n]\rightarrow[m]</math> by letting <math>f(i)=j</math> if and only if <math>i\in B_j</math>. <math>f</math> is surjective since as a partition, none of <math>B_i</math> is empty.
 
Therefore, we have a one-to-one correspondence between surjective mappings from an <math>n</math>-set to an <math>m</math>-set and the ordered <math>m</math>-partitions of an <math>n</math>-set.
 
The Stirling number of the second kind <math>S(n,m)</math> is the number of <math>m</math>-partitions of an <math>n</math>-set. There are <math>m!</math> ways to order an <math>m</math>-partition, thus the number of surjective mappings <math>f:[n]\rightarrow[m]</math> is <math>m! S(n,m)</math>. Combining with what we have proved for surjections, we give the following result for the Stirling number of the second kind.


{{Theorem|Proposition|
=== Double counting ===
:<math>S(n,m)=\frac{1}{m!}\sum_{k=1}^m(-1)^{m-k}{m\choose k}k^n</math>.
The double counting principle states the following obvious fact: if the elements of a set are counted in two different ways, the answers are the same.
;Handshaking lemma
The following lemma is a standard demonstration of double counting.
{{Theorem|Handshaking Lemma|
:At a party, the number of guests who shake hands an odd number of times is even.
}}
}}


=== Derangements ===
We model this scenario as an undirected graph <math>G(V,E)</math> with <math>|V|=n</math> standing for the <math>n</math> guests. There is an edge <math>uv\in E</math> if <math>u</math> and <math>v</math> shake hands. Let <math>d(v)</math> be the degree of vertex <math>v</math>, which represents the number of times that <math>v</math> shakes hand. The handshaking lemma states that in any undirected graph, the number of vertices whose degrees are odd is even. It is sufficient to show that the sum of odd degrees is even.
We now count the number of bijections from a set to itself with no fixed points. This is the '''derangement problem'''.


For a permutation <math>\pi</math> of <math>\{1,2,\ldots,n\}</math>, a '''fixed point''' is such an <math>i\in\{1,2,\ldots,n\}</math> that <math>\pi(i)=i</math>.
The handshaking lemma is a direct consequence of the following lemma, which is proved by Euler in his 1736 paper on [http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg Seven Bridges of Königsberg] that began the study of graph theory.
A [http://en.wikipedia.org/wiki/Derangement '''derangement'''] of <math>\{1,2,\ldots,n\}</math> is a permutation of <math>\{1,2,\ldots,n\}</math> that has no fixed points.


{{Theorem|Theorem|
{{Theorem|Lemma (Euler 1736)|
:The number of derangements of <math>\{1,2,\ldots,n\}</math> given by
:<math>\sum_{v\in V}d(v)=2|E|</math>
::<math>n!\sum_{k=0}^n\frac{(-1)^k}{k!}\approx \frac{n!}{\mathrm{e}}</math>.
}}
}}
{{Proof|
{{Proof|
Let <math>U</math> be the set of all permutations of <math>\{1,2,\ldots,n\}</math>. So <math>|U|=n!</math>.
We count the number of '''directed''' edges. A directed edge is an ordered pair <math>(u,v)</math> such that <math>\{u,v\}\in E</math>. There are two ways to count the directed edges.


Let <math>A_i</math> be the set of permutations with fixed point <math>i</math>; so <math>|A_i|=(n-1)!</math>. More generally, for any <math>I\subseteq \{1,2,\ldots,n\}</math>, <math>A_I=\bigcap_{i\in I}A_i</math>, and <math>|A_I|=(n-|I|)!</math>, since permutations in <math>A_I</math> fix every point in <math>I</math> and permute the remaining points arbitrarily. A permutation is a derangement if and only if it lies in none of the sets <math>A_i</math>. So the number of derangements is
First, we can enumerate by edges. Pick every edge <math>uv\in E</math> and apply two directions <math>(u,v)</math> and <math>(v,u)</math> to the edge. This gives us <math>2|E|</math> directed edges.
:<math>\sum_{I\subseteq\{1,2,\ldots,n\}}(-1)^{|I|}(n-|I|)!=\sum_{k=0}^n(-1)^k{n\choose k}(n-k)!=n!\sum_{k=0}^n\frac{(-1)^k}{k!}.</math>
By Taylor's series,
:<math>\frac{1}{\mathrm{e}}=\sum_{k=0}^\infty\frac{(-1)^k}{k!}=\sum_{k=0}^n\frac{(-1)^k}{k!}\pm o\left(\frac{1}{n!}\right)</math>.
It is not hard to see that <math>n!\sum_{k=0}^n\frac{(-1)^k}{k!}</math> is the closest integer to <math>\frac{n!}{\mathrm{e}}</math>.
}}
 
Therefore, there are about <math>\frac{1}{\mathrm{e}}</math> 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 <math>\pi(i)\neq i</math>. 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 <math>B\subseteq \{1,\ldots,n\}\times \{1,\ldots,n\}</math>, called a '''board'''.  As illustrated below, we can think of <math>B</math> as a chess board, with the positions in <math>B</math> marked by "<math>\times</math>".
{{Chess diagram small
|
|
|=
8 |__|xx|xx|__|xx|__|__|xx|=
7 |xx|__|__|xx|__|__|xx|__|=
6 |xx|__|xx|xx|__|xx|xx|__|=
5 |__|xx|__|__|xx|__|xx|__|=
4 |xx|__|__|__|xx|xx|xx|__|=
3 |__|xx|__|xx|__|__|__|xx|=
2 |__|__|xx|__|xx|__|__|xx|=
1 |xx|__|__|xx|__|xx|__|__|=
a b c d e f g h
|
}}
For a permutation <math>\pi</math> of <math>\{1,\ldots,n\}</math>, define the '''graph''' <math>G_\pi(V,E)</math> as
:<math>
\begin{align}
G_\pi &= \{(i,\pi(i))\mid i\in \{1,2,\ldots,n\}\}.
\end{align}
</math>
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 <math>\pi</math> is a permutation. Thus, we can identify each <math>G_\pi</math> as a placement of <math>n</math> rooks (“城堡”，规则同中国象棋里的“车”) without attacking each other.
 
For example, the following is the <math>G_\pi</math> of such <math>\pi</math> that <math>\pi(i)=i</math>.
{{Chess diagram small
|
|
|=
8 |rl|__|__|__|__|__|__|__|=
7 |__|rl|__|__|__|__|__|__|=
6 |__|__|rl|__|__|__|__|__|=
5 |__|__|__|rl|__|__|__|__|=
4 |__|__|__|__|rl|__|__|__|=
3 |__|__|__|__|__|rl|__|__|=
2 |__|__|__|__|__|__|rl|__|=
1 |__|__|__|__|__|__|__|rl|=
a b c d e f g h
|
}}
Now define
:<math>\begin{align}
N_0 &= \left|\left\{\pi\mid B\cap G_\pi=\emptyset\right\}\right|\\
r_k &= \mbox{number of }k\mbox{-subsets of }B\mbox{ such that no two elements have a common coordinate}\\
&=\left|\left\{S\in{B\choose k} \,\bigg|\, \forall (i_1,j_1),(i_2,j_2)\in S, i_1\neq i_2, j_1\neq j_2 \right\}\right|
\end{align}
</math>
Interpreted in chess game,
* <math>B</math>: a set of marked positions in an <math>[n]\times [n]</math> chess board.
* <math>N_0</math>: the number of ways of placing <math>n</math> non-attacking rooks on the chess board such that none of these rooks lie in <math>B</math>.
* <math>r_k</math>: number of ways of placing <math>k</math> non-attacking rooks on <math>B</math>.


Our goal is to count <math>N_0</math> in terms of <math>r_k</math>. This gives the number of permutations avoid all positions in a <math>B</math>.
On the other hand, we can enumerate by vertices. Pick every vertex <math>v\in V</math> and for each of its <math>d(v)</math> neighbors, say <math>u</math>, generate a directed edge <math>(v,u)</math>. This gives us <math>\sum_{v\in V}d(v)</math> directed edges.


{{Theorem|Theorem|
It is obvious that the two terms are equal, since we just count the same thing twice with different methods. The lemma follows.
:<math>N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!</math>.
}}
}}
{{Proof|
For each <math>i\in[n]</math>, let <math>A_i=\{\pi\mid (i,\pi(i))\in B\}</math> be the set of permutations <math>\pi</math> whose <math>i</math>-th position is in <math>B</math>.


<math>N_0</math> is the number of permutations avoid all positions in <math>B</math>. Thus, our goal is to count the number of permutations <math>\pi</math> in none of <math>A_i</math> for <math>i\in [n]</math>.
The handshaking lemma is implied directly by the above lemma, since the sum of even degrees is even.


For each <math>I\subseteq [n]</math>, let <math>A_I=\bigcap_{i\in I}A_i</math>, which is the set of permutations <math>\pi</math> such that <math>(i,\pi(i))\in B</math> for all <math>i\in I</math>. Due to the principle of inclusion-exclusion,
;Cayley's formula
:<math>N_0=\sum_{I\subseteq [n]} (-1)^{|I|}|A_I|=\sum_{k=0}^n(-1)^k\sum_{I\in{[n]\choose k}}|A_I|</math>.
We now present a theorem of the number of labeled trees on a fixed number of vertices. It is due to [http://en.wikipedia.org/wiki/Arthur_Cayley Cayley] in 1889. The theorem is often referred by the name [http://en.wikipedia.org/wiki/Cayley's_formula Cayley's formula].


The next observation is that
{{Theorem|Caylay's formula for trees|
:<math>\sum_{I\in{[n]\choose k}}|A_I|=r_k(n-k)!</math>,
: There are <math>n^{n-2}</math> different trees on <math>n</math> distinct vertices.
because we can count both sides by first placing <math>k</math> non-attacking rooks on <math>B</math> and placing <math>n-k</math> additional non-attacking rooks on <math>[n]\times [n]</math> in <math>(n-k)!</math> ways.
 
Therefore,
:<math>N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!</math>.
}}
}}


====Derangement problem====
The theorem has several proofs. Classical methods include the bijection which encodes a tree by a [http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence Prüfer sequence], and through the [http://en.wikipedia.org/wiki/Kirchhoff's_matrix_tree_theorem Kirchhoff's matrix tree theorem]. Here we present a proof by double counting, which is considered by the [http://en.wikipedia.org/wiki/Proofs_from_THE_BOOK Proofs from THE BOOK] "the most beautiful of them all".
We use the above general method to solve the derange problem again.
{{Proof|(Due to Pitman 1999)


Take <math>B=\{(1,1),(2,2),\ldots,(n,n)\}</math> as the chess board.  A derangement <math>\pi</math> is a placement of <math>n</math> non-attacking rooks such that none of them is in <math>B</math>.
Let <math>T_n</math> be the number of different trees defined on <math>n</math> distinct vertices.
{{Chess diagram small
|
|
|=
8 |xx|__|__|__|__|__|__|__|=
7 |__|xx|__|__|__|__|__|__|=
6 |__|__|xx|__|__|__|__|__|=
5 |__|__|__|xx|__|__|__|__|=
4 |__|__|__|__|xx|__|__|__|=
3 |__|__|__|__|__|xx|__|__|=
2 |__|__|__|__|__|__|xx|__|=
1 |__|__|__|__|__|__|__|xx|=
a b c d e f g h
|
}}
Clearly, the number of ways of placing <math>k</math> non-attacking rooks on <math>B</math> is <math>r_k={n\choose k}</math>. We want to count <math>N_0</math>, which gives the number of ways of placing <math>n</math> non-attacking rooks such that none of these rooks lie in <math>B</math>.


By the above theorem
A '''rooted tree''' is a tree with a special vertex. That is, one of the <math>n</math> vertices is marked as the "root" of the tree. A rooted tree defines a natural direction of all edges, such that an edge <math>uv</math> of the tree is directed from <math>u</math> to <math>v</math> if <math>u</math> is before <math>v</math> along the unique path from the root.
:<math>
N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!=\sum_{k=0}^n(-1)^k{n\choose k}(n-k)!=\sum_{k=0}^n(-1)^k\frac{n!}{k!}=n!\sum_{k=0}^n(-1)^k\frac{1}{k!}\approx\frac{n!}{e}.
</math>


====Problème des ménages====
We count the number of different ''sequences'' of directed edges that can be added to an empty graph on <math>n</math> vertices to form from it a ''rooted'' tree. We note that such a sequence can be formed in two ways:
Suppose that in a banquet, we want to seat <math>n</math> couples at a circular table, satisfying the following constraints:
# Starting with an unrooted tree, choose one of its vertices as root, and fix an total order of edges to specify the order in which the edges are added.
* Men and women are in alternate places.
# Starting from an empty graph, add the edges one by one in steps.
* No one sits next to his/her spouse.


In how many ways can this be done?
In the first method, we pick one of the <math>T_n</math> unrooted trees, choose one of the <math>n</math> vertices as the root, and pick one of the <math>(n-1)!</math> total orders of the <math>n-1</math> edges. This gives us <math>T_nn(n-1)!=T_nn!</math> ways.


(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.)
In the second method, we consider the number of choices in one step, and multiply the numbers of choices in all steps. This is done as follows.


First, let the <math>n</math> ladies find their seats. They may either sit at the odd numbered seats or even numbered seats, in either case, there are <math>n!</math> different orders. Thus, there are <math>2(n!)</math> ways to seat the <math>n</math> ladies.
Given a sequence of ''adding'' <math>n-1</math> edges to an empty graph to form a rooted tree, we reverse this sequence and get a sequence of ''removing'' edges one by one from the final rooted tree until no edge left. We observe that:
* At first, we remove an edge from the rooted tree. Suppose that the root of the tree is <math>r</math>, and the removed directed edge is <math>(u,v)</math>. After removing <math>(u,v)</math>, the original rooted tree is disconnected into two rooted trees, one rooted at <math>r</math> and the other rooted at <math>v</math>.
* After removing <math>k-1</math> edges, there are <math>k</math> rooted trees. In the <math>k</math>th step, a directed edge <math>(u,v)</math> in the current forest is removed and the tree containing <math>(u,v)</math> is disconnected into two trees, one rooted at the old root of that tree, and the other rooted at <math>v</math>.


After sitting the wives, we label the remaining <math>n</math> places clockwise as <math>0,1,\ldots, n-1</math>. And a seating of the <math>n</math> husbands is given by a permutation <math>\pi</math> of <math>[n]</math> defined as follows. Let <math>\pi(i)</math> be the seat of the husband of he lady sitting at the <math>i</math>-th place.
We now again reverse the above procedure, and consider the sequence of adding directed edges to an empty graph to form a rooted tree.
* At first, we have <math>n</math> rooted trees, each of 0 edge (<math>n</math> isolated vertices).
* After adding <math>n-k</math> edges, there are <math>k</math> rooted trees. Denoting the directed edge added next as <math>(u,v)</math>. As observed above, <math>u</math> can be any one of the <math>n</math> vertices; but <math>v</math> must be the root of one of the <math>k</math> trees, except the tree which contains <math>u</math>. There are <math>n(k-1)</math> choices of such <math>(u,v)</math>.
Multiplying the numbers of choices in all steps, the number of sequences of adding directed edges to an empty graph to form a rooted tree is given by
:<math>\prod_{k=2}^nn(k-1)=n^{n-2}n!</math>.


It is easy to see that <math>\pi</math> satisfies that <math>\pi(i)\neq i</math> and <math>\pi(i)\not\equiv i+1\pmod n</math>, and every permutation <math>\pi</math> with these properties gives a feasible seating of the <math>n</math> husbands. Thus, we only need to count the number of permutations <math>\pi</math> such that <math>\pi(i)\not\equiv i, i+1\pmod n</math>.
By the principle of double counting, counting the same thing by different methods yield the same result.
 
:<math>T_nn!=n^{n-2}n!</math>,
Take <math>B=\{(0,0),(1,1),\ldots,(n-1,n-1), (0,1),(1,2),\ldots,(n-2,n-1),(n-1,0)\}</math> as the chess board.  A permutation <math>\pi</math> which defines a way of seating the husbands, is a placement of <math>n</math> non-attacking rooks such that none of them is in <math>B</math>.
which gives that <math>T_n=n^{n-2}</math>.
{{Chess diagram small
|
|
|=
8 |xx|xx|__|__|__|__|__|__|=
7 |__|xx|xx|__|__|__|__|__|=
6 |__|__|xx|xx|__|__|__|__|=
5 |__|__|__|xx|xx|__|__|__|=
4 |__|__|__|__|xx|xx|__|__|=
3 |__|__|__|__|__|xx|xx|__|=
2 |__|__|__|__|__|__|xx|xx|=
1 |xx|__|__|__|__|__|__|xx|=
a b c d e f g h
|
}}
We need to compute <math>r_k</math>, the number of ways of placing <math>k</math> non-attacking rooks on <math>B</math>. For our choice of <math>B</math>, <math>r_k</math> is the number of ways of choosing <math>k</math> points, no two consecutive, from a collection of <math>2n</math> points arranged in a circle.
 
We first see how to do this in a ''line''.
{{Theorem|Lemma|
:The number of ways of choosing <math>k</math> ''non-consecutive'' objects from a collection of <math>m</math> objects arranged in a ''line'', is <math>{m-k+1\choose k}</math>.
}}
{{Proof|
We draw a line of <math>m-k</math> black points, and then insert <math>k</math> red points into the <math>m-k+1</math> spaces between the black points (including the beginning and end).
::<math>
\begin{align}
&\sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \\
&\qquad\qquad\qquad\quad\Downarrow\\
&\sqcup \, \bullet \,\, {\color{Red}\bullet} \, \bullet \,\, {\color{Red}\bullet} \, \bullet \, \sqcup \, \bullet \,\, {\color{Red}\bullet}\, \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \,\, {\color{Red}\bullet}
\end{align}
</math>
This gives us a line of <math>m</math> points, and the red points specifies the chosen objects, which are non-consecutive. The mapping is 1-1 correspondence.
There are <math>{m-k+1\choose k}</math> ways of placing <math>k</math> red points into <math>m-k+1</math> spaces.
}}
}}


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


{{Theorem|Lemma|
:The number of ways of choosing <math>k</math> ''non-consecutive'' objects from a collection of <math>m</math> objects arranged in a ''circle'', is <math>\frac{m}{m-k}{m-k\choose k}</math>.
== The Pigeonhole Principle ==
The '''pigeonhole principle''' states the following "obvious" fact:
:''<math>n+1</math> pigeons cannot sit in <math>n</math> holes so that every pigeon is alone in its hole.''
More generally, the pigeonhole principle states as the following.
{{Theorem|Generalized pigeonhole principle|
:If a set consisting of more than <math>mn</math> objects is partitioned into <math>n</math> classes, then some class receives more than <math>m</math> objects.
}}
}}
{{Proof|
Let <math>f(m,k)</math> be the desired number; and let <math>g(m,k)</math> be the number of ways of choosing <math>k</math> non-consecutive points from <math>m</math> points arranged in a circle, next coloring the <math>k</math> points red, and then coloring one of the uncolored point blue.


Clearly, <math>g(m,k)=(m-k)f(m,k)</math>.
This is one of the oldest '''non-constructive''' principles: it states only the ''existence'' of a pigeonhole with more than <math>m</math> pigeons and says nothing about how to ''find'' such a pigeonhole.


But we can also compute <math>g(m,k)</math> as follows:
=== Monotonic subsequences ===
* Choose one of the <math>m</math> points and color it blue. This gives us <math>m</math> ways.
Let <math>(a_1,a_2,\ldots,a_n)</math> be a sequence of <math>n</math> distinct real numbers. A '''subsequence''' is a sequence of distinct terms of <math>(a_1,a_2,\ldots,a_n)</math> appearing in the same order in which they appear in <math>(a_1,a_2,\ldots,a_n)</math>. Formally, a subsequence of <math>(a_1,a_2,\ldots,a_n)</math> is an <math>(a_{i_1},a_{i_2},\ldots,a_{i_k})</math>, with <math>i_1<i_2<\cdots<i_k</math>.
* Cut the circle to make a line of <math>m-1</math> points by removing the blue point.
* Choose <math>k</math> non-consecutive points from the line of <math>m-1</math> points and color them red. This gives <math>{m-k\choose k}</math> ways due to the previous lemma.


Thus, <math>g(m,k)=m{m-k\choose k}</math>. Therefore we have the desired number <math>f(m,k)=\frac{m}{m-k}{m-k\choose k}</math>.
A sequence <math>(a_1,a_2,\ldots,a_n)</math> is '''increasing''' if <math>a_1<a_2<\cdots<a_n</math>, and '''decreasing''' if <math>a_1>a_2>\cdots>a_n</math>.
}}


By the above lemma, we have that <math>r_k=\frac{2n}{2n-k}{2n-k\choose k}</math>. Then apply the theorem of counting permutations with restricted positions,
We are interested in the ''longest'' increasing and decreasing subsequences of an <math>a_1<a_2<\cdots<a_n</math>. It is intuitive that the length of both the longest increasing subsequence and the longest decreasing subsequence cannot be small simultaneously. A famous result of Erdős and Szekeres formally justifies this intuition. This is one of the first results in extremal combinatorics, published in the influential 1935 paper of Erdős and Szekeres.
:<math>
N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!=\sum_{k=0}^n(-1)^k\frac{2n}{2n-k}{2n-k\choose k}(n-k)!.
</math>


This gives the number of ways of seating the <math>n</math> husbands ''after the ladies are seated''. Recall that there are <math>2n!</math> ways of seating the <math>n</math> ladies. Thus, the total number of ways of seating <math>n</math> couples as required by problème des ménages is
{{Theorem|Theorem (Erdős-Szekeres 1935)|
:<math>
:A sequence of more than <math>mn</math> different real numbers must contain either an increasing subsequence of length <math>m+1</math>, or a decreasing subsequence of length <math>n+1</math>.
2n!\sum_{k=0}^n(-1)^k\frac{2n}{2n-k}{2n-k\choose k}(n-k)!.
</math>
 
=== The Euler totient function ===
Two integers <math>m, n</math> are said to be '''relatively prime''' if their greatest common diviser <math>\mathrm{gcd}(m,n)=1</math>. For a positive integer <math>n</math>, let <math>\phi(n)</math> be the number of positive integers from <math>\{1,2,\ldots,n\}</math> that are relative prime to <math>n</math>. This function, called the Euler <math>\phi</math> 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|Theorem (The Euler totient function)|
Suppose <math>n</math> is divisible by precisely <math>r</math> different primes, denoted <math>p_1,\ldots,p_r</math>. Then
:<math>\phi(n)=n\prod_{i=1}^r\left(1-\frac{1}{p_i}\right)</math>.
}}
}}
{{Proof|
{{Proof|(due to Seidenberg 1959)
Let <math>U=\{1,2,\ldots,n\}</math> be the universe. The number of positive integers from <math>U</math> which is divisible by some <math>p_{i_1},p_{i_2},\ldots,p_{i_s}\in\{p_1,\ldots,p_r\}</math>, is <math>\frac{n}{p_{i_1}p_{i_2}\cdots p_{i_s}}</math>.  
Let <math>(a_1,a_2,\ldots,a_{N})</math> be the original sequence of <math>N>mn</math> distinct real numbers. Associate each <math>a_i</math> a pair <math>(x_i,y_i)</math>, defined as:
*<math>x_i</math>: the length of the longest ''increasing'' subsequence ''ending'' at <math>a_i</math>;
*<math>y_i</math>: the length of the longest ''decreasing'' subsequence ''starting'' at <math>a_i</math>.
A key observation is that <math>(x_i,y_i)\neq (x_j,y_j)</math> whenever <math>i\neq j</math>. This is proved as follows:
: '''Case 1:''' If <math>a_i<a_j</math>, then the longest increasing subsequence ending at <math>a_i</math> can be extended by adding on <math>a_j</math>, so <math>x_i<x_j</math>.
: '''Case 2:'''  If <math>a_i>a_j</math>, then the longest decreasing subsequence starting at <math>a_j</math> can be preceded by <math>a_i</math>, so <math>y_i>y_j</math>.
Now we put <math>N</math> "pigeons" <math>a_1,a_2,\ldots,a_N</math> into "pigeonholes" <math>\{1,2,\ldots,N\}\times\{1,2,\ldots,N\}</math>, such that <math>a_i</math> is put into hole <math>(x_i,y_i)</math>, with at most one pigeon per each hole (since different <math>a_i</math> has different <math>(x_i,y_i)</math>).  


<math>\phi(n)</math> is the number of integers from <math>U</math> which is not divisible by any <math>p_1,\ldots,p_r</math>.
The number of pigeons is <math>N>mn</math>. Due to pigeonhole principle, there must be a pigeon which is outside the region <math>\{1,2,\ldots,m\}\times\{1,2,\ldots,n\}</math>, which implies that there exists an <math>a_i</math> with either <math>x_i>m</math> or <math>y_i>n</math>. Due to our definition of <math>(x_i,y_i)</math>, there must be either an increasing subsequence of length <math>m+1</math>, or a decreasing subsequence of length <math>n+1</math>.
By principle of inclusion-exclusion,
:<math>
\begin{align}
\phi(n)
&=n+\sum_{k=1}^r(-1)^k\sum_{1\le i_1<i_2<\cdots <i_k\le n}\frac{n}{p_{i_1}p_{i_2}\cdots p_{i_k}}\\
&=n-\sum_{1\le i\le n}\frac{n}{p_i}+\sum_{1\le i<j\le n}\frac{n}{p_i p_j}-\sum_{1\le i<j<k\le n}\frac{n}{p_{i} p_{j} p_{k}}+\cdots + (-1)^r\frac{n}{p_{1}p_{2}\cdots p_{r}}\\
&=n\left(1-\sum_{1\le i\le n}\frac{1}{p_i}+\sum_{1\le i<j\le n}\frac{1}{p_i p_j}-\sum_{1\le i<j<k\le n}\frac{1}{p_{i} p_{j} p_{k}}+\cdots + (-1)^r\frac{1}{p_{1}p_{2}\cdots p_{r}}\right)\\
&=n\prod_{i=1}^n\left(1-\frac{1}{p_i}\right).
\end{align}
</math>
}}
}}


== Möbius inversion ==
=== Dirichlet's approximation ===
Let <math>x</math> be an irrational number. We now want to approximate <math>x</math> be a rational number (a fraction).


=== Posets ===
Since every real interval <math>[a,b]</math> with <math>a<b</math> contains infinitely many rational numbers, there must exist rational numbers arbitrarily close to <math>x</math>. The trick is to let the denominator of the fraction sufficiently large.
A '''partially ordered set''' or '''poset''' for short is a set <math>P</math> together with a binary relation denoted <math>\le_P</math> (or just <math>\le</math> if no confusion is caused), satisfying
* (''reflexivity'') For all <math>x\in P, x\le x</math>.
* (''antisymmetry'') If <math>x\le y</math> and <math>y\le x</math>, then <math>x=y</math>.
* (''transitivity'') If <math>x\le y</math> and <math>y\le z</math>, then <math>x\le z</math>.


We say two elements <math>x</math> and <math>y</math> are '''comparable''' if <math>x\le y</math> or <math>y\le x</math>; otherwise <math>x</math> and <math>y</math> are '''incomparable'''.
Suppose however we restrict the rationals we may select to have denominators bounded by <math>n</math>. How closely we can approximate <math>x</math> now?


;Notation
The following important theorem is due to Dirichlet and his ''Schubfachprinzip'' ("drawer principle"). The theorem is fundamental in numer theory and real analysis, but the proof is combinatorial.
* <math>x\ge y</math> means <math>y\le x</math>.
* <math>x<y</math> means <math>x\le y</math> and <math>x\neq y</math>.
* <math>x>y</math> means <math>y<x</math>.


=== The Möbius function===
{{Theorem|Theorem (Dirichlet 1879)|
Let <math>P</math> be a finite poset. Consider functions in form of <math>\alpha:P\times P\rightarrow\mathbb{R}</math> defined over domain <math>P\times P</math>. It is convenient to treat such functions as matrices whose rows and columns are indexed by <math>P</math>.
:Let <math>x</math> be an irrational number. For any natural number <math>n</math>, there is a rational number <math>\frac{p}{q}</math> such that <math>1\le q\le n</math> and  
 
::<math>\left|x-\frac{p}{q}\right|<\frac{1}{nq}</math>.
;Incidence algebra of poset
:Let
::<math>I(P)=\{\alpha:P\times P\rightarrow\mathbb{R}\mid \alpha(x,y)=0\text{ for all }x\not\le_P y\}</math>
:be the class of <math>\alpha</math> such that <math>\alpha(x,y)</math> is non-zero only for <math>x\le_P y</math>.
 
:Treating <math>\alpha</math> as matrix, it is trivial to see that <math>I(P)</math> is closed under addition and scalar multiplication, that is,
:* if <math>\alpha,\beta\in I(P)</math> then <math>\alpha+\beta\in I(P)</math>;
:* if <math>\alpha\in I(P)</math> then <math>c\alpha\in I(P)</math> for any <math>c\in\mathbb{R}</math>;
:where <math>\alpha,\beta</math> are treated as matrices.
 
:With this spirit, it is natural to define the matrix multiplication in <math>I(P)</math>. For <math>\alpha,\beta\in I(P)</math>,
::<math>(\alpha\beta)(x,y)=\sum_{z\in P}\alpha(x,z)\beta(z,y)=\sum_{x\le z\le y}\alpha(x,z)\beta(z,y)</math>.
:The second equation is due to that for <math>\alpha,\beta\in I(P)</math>, for all <math>z</math> other than <math>x\le z\le y</math>, <math>\alpha(x,z)\beta(z,y)</math> is zero.
:By the transitivity of relation <math>\le_P</math>, it is also easy to prove that <math>I(P)</math> is closed under matrix multiplication (the detailed proof is left as an exercise). Therefore, <math>I(P)</math> is closed under addition, scalar multiplication and matrix multiplication, so we have an algebra <math>I(P)</math>, called '''incidence algebra''', over functions on <math>P\times P</math>.
 
;Zeta function and Möbius function
:A special function in <math>I(P)</math> is the so-called '''zeta function''' <math>\zeta</math>, defined as
::<math>\zeta(x,y)=\begin{cases}1&\text{if }x\le_P y,\\0 &\text{otherwise.}\end{cases}</math>
:As a matrix (or more accurately, as an element of the incidence algebra), <math>\zeta</math> is invertible and its inversion, denoted by <math>\mu</math>, is called the '''Möbius function'''. More precisely, <math>\mu</math> is also in the incidence algebra <math>I(P)</math>, and <math>\mu\zeta=I</math> where <math>I</math> is the identity matrix (the identity of the incidence algebra <math>I(P)</math>).
 
There is an equivalent explicit definition of Möbius function.
{{Theorem|Definition (Möbius function)|
:<math>\mu(x,y)=\begin{cases}
-\sum_{x\le z< y}\mu(x,z)&\text{if }x<y,\\
1&\text{if }x=y,\\
0&\text{if }x\not\le y.
\end{cases}
</math>
}}
 
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 <math>\mu\zeta</math>.
{{Theorem|Proposition|
:For any <math>x,y\in P</math>,
::<math>\sum_{x\le z\le y}\mu(x,z)=\begin{cases}1 &\text{if }x=y,\\
0 &\text{otherwise.}\end{cases}</math>
}}
}}
{{Proof|
{{Proof|
It holds that
Let <math>\{x\}=x-\lfloor x\rfloor</math> denote the '''fractional part''' of the real number <math>x</math>. It is obvious that <math>\{x\}\in[0,1)</math> for any real number <math>x</math>.
:<math>(\mu\zeta)(x,y)=\sum_{x\le z\le y}\mu(x,z)\zeta(z,y)=\sum_{x\le z\le y}\mu(x,z)</math>.
On the other hand, <math>\mu\zeta=I</math>, i.e.
:<math>(\mu\zeta)(x,y)=\begin{cases}1 &\text{if }x=y,\\
0 &\text{otherwise.}\end{cases}</math>
The proposition follows.
}}
Note that <math>\mu(x,y)=\sum_{x\le z\le y}\mu(x,z)-\sum_{x\le z< y}\mu(x,z)</math>, which gives the above inductive definition of Möbius function.


=== Computing Möbius functions===
Consider the <math>n+1</math> numbers <math>\{kx\}</math>, <math>k=1,2,\ldots,n+1</math>. These <math>n+1</math> numbers (pigeons) belong to the following <math>n</math> intervals (pigeonholes):
We consider the simple poset <math>P=[n]</math>, where <math>\le</math> is the total order. It follows directly from the recursive definition of Möbius function that
:<math>\left(0,\frac{1}{n}\right),\left(\frac{1}{n},\frac{2}{n}\right),\ldots,\left(\frac{n-1}{n},1\right)</math>.
:<math>\mu(i,j)=\begin{cases}1 & \text{if }i=j,\\
Since <math>x</math> is irrational, <math>\{kx\}</math> cannot coincide with any endpoint of the above intervals.
-1 & \text{if }i+1=j,\\
0 & \text{otherwise.}
\end{cases}
</math>


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.
By the pigeonhole principle, there exist <math>1\le a<b\le n+1</math>, such that <math>\{ax\},\{bx\}</math> are in the same interval, thus
 
:<math>|\{bx\}-\{ax\}|<\frac{1}{n}</math>.
{{Theorem|Theorem (the product rule)|
Therefore,
: Let <math>P</math> and <math>Q</math> be two finite posets, and <math>P\times Q</math> be the poset resulted from Cartesian product of <math>P</math> and <math>Q</math>, where for all <math>(x,y), (x',y')\in P\times Q</math>, <math>(x,y)\le (x',y')</math> if and only if <math>x\le x'</math> and <math>y\le y'</math>. Then
:<math>|(b-a)x-\left(\lfloor bx\rfloor-\lfloor ax\rfloor\right)|<\frac{1}{n}</math>.
::<math>\mu_{P\times Q}((x,y),(x',y'))=\mu_P(x,x')\mu_Q(y,y')</math>.
Let <math>q=b-a</math> and <math>p=\lfloor bx\rfloor-\lfloor ax\rfloor</math>. We have <math>|qx-p|<\frac{1}{n}</math> and <math>1\le q\le n</math>. Dividing both sides by <math>q</math>, the theorem is proved.
}}
}}
{{Proof|
We use the recursive definition
:<math>\mu(x,y)=\begin{cases}
-\sum_{x\le z< y}\mu(x,z)&\text{if }x<y,\\
1&\text{if }x=y,\\
0&\text{if }x\not\le y.
\end{cases}
</math>
to prove the equation in the theorem.


If <math>(x,y)=(x',y')</math>, then <math>x=x'</math> and <math>y=y'</math>. It is easy to see that both sides of the equation are 1. If <math>(x,y)\not\le(x',y')</math>, then either <math>x\not\le x'</math> or <math>y\not\le y'</math>. It is also easy to see that both sides are 0.
=== Pigeonhole vs. resolution proofs ===
 
The only remaining case is that <math>(x,y)<(x',y')</math>, in which case either <math>x<x'</math> or <math>y<y'</math>.
:<math>
\begin{align}
\sum_{(x,y)\le (u,v)\le (x',y')}\mu_P(x,u)\mu_Q(y,v)
&=\left(\sum_{x\le u\le x'}\mu_P(x,u)\right)\left(\sum_{y\le v\le y'}\mu_Q(y,v)\right)=I(x,x')I(y,y')=0,
\end{align}
</math>
where the last two equations are due to the proposition for <math>\mu</math>. Thus
:<math>\mu_P(x,x')\mu_Q(y,y')=-\sum_{(x,y)\le (u,v)< (x',y')}\mu_P(x,u)\mu_Q(y,v)</math>.
 
By induction, assume that the equation <math>\mu_{P\times Q}((x,y),(u,v))=\mu_P(x,u)\mu_Q(y,v)</math> is true for all <math>(u,v)< (x',y')</math>. Then
:<math>
\begin{align}
\mu_{P\times Q}((x,y),(x',y'))
&=-\sum_{(x,y)\le (u,v)< (x',y')}\mu_{P\times Q}((x,y),(u,v))\\
&=-\sum_{(x,y)\le (u,v)< (x',y')}\mu_P(x,u)\mu_Q(y,v)\\
&=\mu_P(x,x')\mu_Q(y,y'),
\end{align}
</math>
which complete the proof.
}}
 
;Poset of subsets
:Consider the poset defined by all subsets of a finite universe <math>U</math>, that is <math>P=2^U</math>, and for <math>S,T\subseteq U</math>, <math>S\le_P T</math> if and only if <math>S\subseteq T</math>.
 
{{Theorem| Möbius function for subsets|
:The Möbius function for the above defined poset <math>P</math> is that for <math>S,T\subseteq U</math>,
::<math>\mu(S,T)=
\begin{cases}
(-1)^{|T|-|S|} & \text{if }S\subseteq T,\\
0 &\text{otherwise.}
\end{cases}
</math>
}}
{{Proof|
We can equivalently represent each <math>S\subseteq U</math> by a boolean string <math>S\in\{0,1\}^U</math>, where <math>S(x)=1</math> if and only if <math>x\in S</math>.
 
For each element <math>x\in U</math>, we can define a poset <math>P_x=\{0, 1\}</math> with <math>0\le 1</math>. By definition of Möbius function, the Möbius function of this elementary poset is given by <math>\mu_x(0,0)=\mu_x(1,1)=1</math>, <math>\mu_x(0,1)=-1</math> and <math>\mu(1,0)=0</math>.
 
The poset <math>P</math> of all subsets of <math>U</math> is the Cartesian product of all <math>P_x</math>, <math>x\in U</math>. By the product rule,
:<math>\mu(S,T)=\prod_{x\in U}\mu_x(S(x), T(x))=\prod_{x\in S\atop x\in T}1\prod_{x\not\in S\atop x\not\in T}1\prod_{x\in S\atop x\not\in T}0\prod_{x\not\in S\atop x\in T}(-1)=\begin{cases}
(-1)^{|T|-|S|} & \text{if }S\subseteq T,\\
0 &\text{otherwise.}
\end{cases}</math>
}}
 
:Note that the poset <math>P</math> is actually the [http://en.wikipedia.org/wiki/Boolean_algebra_(structure) Boolean algebra] of rank <math>|U|</math>. 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 <math>n</math>, that is <math>P=\{a>0\mid a|n\}</math>, and for <math>a,b\in P</math>, <math>a\le_P b</math> if and only if <math>a|b\,</math>.
 
{{Theorem|Möbius function for divisors|
:The Möbius function for the above defined poset <math>P</math> is that for <math>a,b>0</math> that <math>a|n</math> and <math>b|n</math>,
::<math>\mu(a,b)=
\begin{cases}
(-1)^{r} & \text{if }\frac{b}{a}\text{ is the product of }r\text{ distinct primes},\\
0 &\text{otherwise, i.e. if }a\not|b\text{ or }\frac{b}{a}\text{ is not squarefree.}
\end{cases}
</math>
}}
{{Proof|
Denote <math>n=p_1^{n_1}p_2^{n_2}\cdots p_k^{n_k}</math>. Represent <math>n</math> by a tuple <math>(n_1,n_2,\ldots,n_k)</math>. Every <math>a\in P</math> corresponds in this way to a tuple <math>(a_1,a_2,\ldots,a_k)</math> with <math>a_i\le n_i</math> for all <math>1\le i\le k</math>.
 
Let <math>P_i=\{1,2,\ldots,n_i\}</math> be the poset with <math>\le</math> being the total order. The poset <math>P</math> of divisors of <math>n</math> is thus isomorphic to the poset constructed by the Cartesian product of all <math>P_i</math>, <math>1\le i\le k</math>. Then
:<math>
\begin{align}
\mu(a,b)
&=\prod_{1\le i\le k}\mu(a_i,b_i)=\prod_{1\le i\le k\atop a_i=b_i}1\prod_{1\le i\le k\atop b_i-a_i=1}(-1)\prod_{1\le i\le k\atop b_i-a_i\not\in\{0,1\}}0
=\begin{cases}
(-1)^{\sum_{i}(b_i-a_i)} & \text{if all }b_i-a_i\in\{0,1\},\\
0 &\text{otherwise.}
\end{cases}\\
&=\begin{cases}
(-1)^{r} & \text{if }\frac{b}{a}\text{ is the product of }r\text{ distinct primes},\\
0 &\text{otherwise.}
\end{cases}
\end{align}
</math>
}}
 
=== Principle of Möbius inversion ===
We now introduce the the famous Möbius inversion formula.
{{Theorem|Möbius inversion formula|
:Let <math>P</math> be a finite poset and <math>\mu</math> its Möbius function. Let <math>f,g:P\rightarrow \mathbb{R}</math>. Then
::<math>\forall x\in P,\,\, g(x)=\sum_{y\le x} f(y)</math>,
:if and only if
::<math>\forall x\in P,\,\, f(x)=\sum_{y\le x}g(y)\mu(y,x)</math>.
}}
The functions <math>f,g:P\rightarrow\mathbb{R}</math> are vectors. Evaluate the matrix multiplications <math>f\zeta</math> and <math>g\mu</math> as follows:
:<math>(f\zeta)(x)=\sum_{y\in P}f(y)\zeta(y,x)=\sum_{y\le x}f(y)\zeta(y,x)=\sum_{y\le x}f(y)</math>,
and
:<math>(g\mu)(x)=\sum_{y\in P}g(y)\mu(y,x)=\sum_{y\le x}g(y)\mu(y,x)</math>.
The Möbius inversion formula is nothing but the following statement
:<math>f\zeta=g\Leftrightarrow f=g\mu</math>,
which is trivially true due to <math>\mu\zeta=I</math> by basic linear algebra.
 
The following dual form of the inversion formula is also useful.
{{Theorem|Möbius inversion formula, dual form|
:Let <math>P</math> be a finite poset and <math>\mu</math> its Möbius function. Let <math>f,g:P\rightarrow \mathbb{R}</math>. Then
::<math>\forall x\in P, \,\, g(x)=\sum_{y{\color{red}\ge} x} f(y)</math>,
: if and only if
::<math>\forall x\in P, \,\, f(x)=\sum_{y{\color{red}\ge} x}\mu(x,y)g(y)</math>.
}}
To prove the dual form, we only need to evaluate the matrix multiplications on left:
:<math>\zeta f=g\Leftrightarrow f=\mu g</math>.


;Principle of Inclusion-Exclusion
== Averaging Principle ==
:Let <math>A_1,A_2,\ldots,A_n\subseteq U</math>. For any <math>J\subseteq\{1,2,\ldots,n\}</math>,
:*let <math>f(J)</math> be the number of elements that belongs to ''exactly'' the sets <math>A_i, i\in J</math> and to no others, i.e.
:::<math>f(J)=\left|\left(\bigcap_{i\in J}A_i\right)\setminus\left(\bigcup_{i\not\in J}A_i\right)\right|</math>;
:*let <math>g(J)=\left|\bigcap_{i\in J}A_i\right|</math>.
:For any <math>J\subseteq\{1,2,\ldots,n\}</math>, the following relation holds for the above defined <math>f</math> and <math>g</math>:
::<math>g(J)=\sum_{I\supseteq J}f(I)</math>.
:Applying the dual form of the Möbius inversion formula, we have that for any <math>J\subseteq\{1,2,\ldots,n\}</math>,
::<math>f(J)=\sum_{I\supseteq J}\mu(J,I)g(I)=\sum_{I\supseteq J}\mu(J,I)\left|\bigcap_{i\in I}A_i\right|</math>,
:where the Möbius function is for the poset of all subsets of <math>\{1,2,\ldots,n\}</math>, ordered by <math>\subseteq</math>, thus it holds that <math>\mu(J,I)=(-1)^{|I|-|J|}\,</math> for <math>J\subseteq I</math>. Therefore,
::<math>f(J)=\sum_{I\supseteq J}(-1)^{|I|-|J|}\left|\bigcap_{i\in I}A_i\right|</math>.
:We have a formula for the number of elements with exactly those properties <math>A_i, i\in J</math> for any <math>J\subseteq\{1,2,\ldots,n\}</math>. For the special case that <math>J=\emptyset</math>, <math>f(\emptyset)</math> is the number of elements satisfying no property of <math>A_1,A_2,\ldots,A_n</math>, and
::<math>f(\emptyset)=\left|U\setminus\bigcup_iA_i\right|=\sum_{I\subseteq \{1,\ldots,n\}}(-1)^{|I|}\left|\bigcap_{i\in I}A_i\right|</math>
:which gives precisely the Principle of Inclusion-Exclusion.


;Möbius inversion formula for number theory
== References ==
:The number-theoretical Möbius inversion formula is stated as such: Let <math>N</math> be a positive integer,
:('''声明:''' 资料受版权保护, 仅用于教学.)
::<math>g(n)=\sum_{d|n}f(d)\,</math> for all <math>n|N</math>
:('''Disclaimer:''' The following copyrighted materials are meant for educational uses only.)
:if and only if
::<math>f(n)=\sum_{d|n}g(d)\mu\left(\frac{n}{d}\right)\,</math> for all <math>n|N</math>,
:where <math>\mu</math> is the [http://en.wikipedia.org/wiki/M%C3%B6bius_function number-theoretical Möbius function], defined as
::<math>\mu(n)=\begin{cases}1 & \text{if }n\text{ is product of an even number of distinct primes,}\\
-1 &\text{if }n\text{ is product of an odd number of distinct primes,}\\
0 &\text{otherwise.}\end{cases}</math>
:This is just a special case of the Möbius inversion formula for posets, when the poset is the set of divisors of <math>N</math>, and for any <math>a,b\in P</math>, <math>a\le_P b</math> if <math>a|b</math>.


== Reference ==
* Aigner and Ziegler. ''Proofs from THE BOOK, 4th Edition.'' Springer-Verlag. [[media:PFTB_chap25.pdf| Chapter 25]] and [[media:PFTB_chap30.pdf| Chapter 30]].  
* ''Stanley,'' Enumerative Combinatorics, Volume 1, Chapter 2.
* Alon and Spencer. ''The Probabilistic Method, 3rd Edition.'' Wiley, 2008. [[media:TPM_Chap1.pdf|Chapter 1]], [[media:TPM_Chap2.pdf|Chapter 2]], and [[media:TPM_Chap3.pdf|Chapter 3]].
* ''van Lin and Wilson'', A course in combinatorics, Chapter 10, 25.

Revision as of 06:49, 17 August 2011

Counting arguments

Shannon's circuit lower bound

This is a fundamental problem in in Computer Science.

A boolean function is a function in the form [math]\displaystyle{ f:\{0,1\}^n\rightarrow \{0,1\} }[/math].

Boolean circuit is a mathematical model of computation. Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled [math]\displaystyle{ x_1, x_2, \ldots , x_n }[/math]. A circuit has a unique node with outdegree zero, called the output node. Every other node is a gate. There are three types of gates: AND, OR (both with indegree two), and NOT (with indegree one).

Computations in Turing machines can be simulated by circuits, and any boolean function in P can be computed by a circuit with polynomially many gates. Thus, if we can find a function in NP that cannot be computed by any circuit with polynomially many gates, then NP[math]\displaystyle{ \neq }[/math]P.

The following theorem due to Shannon says that functions with exponentially large circuit complexity do exist.

Theorem (Shannon 1949)
There is a boolean function [math]\displaystyle{ f:\{0,1\}^n\rightarrow \{0,1\} }[/math] with circuit complexity greater than [math]\displaystyle{ \frac{2^n}{3n} }[/math].
Proof.

We first count the number of boolean functions [math]\displaystyle{ f:\{0,1\}^n\rightarrow \{0,1\} }[/math]. There are [math]\displaystyle{ 2^{2^n} }[/math] boolean functions [math]\displaystyle{ f:\{0,1\}^n\rightarrow \{0,1\} }[/math].

Then we count the number of boolean circuit with fixed number of gates. Fix an integer [math]\displaystyle{ t }[/math], we count the number of circuits with [math]\displaystyle{ t }[/math] gates. By the De Morgan's laws, we can assume that all NOTs are pushed back to the inputs. Each gate has one of the two types (AND or OR), and has two inputs. Each of the inputs to a gate is either a constant 0 or 1, an input variable [math]\displaystyle{ x_i }[/math], an inverted input variable [math]\displaystyle{ \neg x_i }[/math], or the output of another gate; thus, there are at most [math]\displaystyle{ 2+2n+t-1 }[/math] possible gate inputs. It follows that the number of circuits with [math]\displaystyle{ t }[/math] gates is at most [math]\displaystyle{ 2^t(t+2n+1)^{2t} }[/math].

If [math]\displaystyle{ t=2^n/3n }[/math], then

[math]\displaystyle{ \frac{2^t(t+2n+1)^{2t}}{2^{2^n}}=o(1)\lt 1, }[/math] thus, [math]\displaystyle{ 2^t(t+2n+1)^{2t} \lt 2^{2^n}. }[/math]

Each boolean circuit computes one boolean function. Therefore, there must exist a boolean function [math]\displaystyle{ f }[/math] which cannot be computed by any circuits with [math]\displaystyle{ 2^n/3n }[/math] gates.

[math]\displaystyle{ \square }[/math]

Note that by Shannon's theorem, not only there exists a boolean function with exponentially large circuit complexity, but almost all boolean functions have exponentially large circuit complexity.

Double counting

The double counting principle states the following obvious fact: if the elements of a set are counted in two different ways, the answers are the same.

Handshaking lemma

The following lemma is a standard demonstration of double counting.

Handshaking Lemma
At a party, the number of guests who shake hands an odd number of times is even.

We model this scenario as an undirected graph [math]\displaystyle{ G(V,E) }[/math] with [math]\displaystyle{ |V|=n }[/math] standing for the [math]\displaystyle{ n }[/math] guests. There is an edge [math]\displaystyle{ uv\in E }[/math] if [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] shake hands. Let [math]\displaystyle{ d(v) }[/math] be the degree of vertex [math]\displaystyle{ v }[/math], which represents the number of times that [math]\displaystyle{ v }[/math] shakes hand. The handshaking lemma states that in any undirected graph, the number of vertices whose degrees are odd is even. It is sufficient to show that the sum of odd degrees is even.

The handshaking lemma is a direct consequence of the following lemma, which is proved by Euler in his 1736 paper on Seven Bridges of Königsberg that began the study of graph theory.

Lemma (Euler 1736)
[math]\displaystyle{ \sum_{v\in V}d(v)=2|E| }[/math]
Proof.

We count the number of directed edges. A directed edge is an ordered pair [math]\displaystyle{ (u,v) }[/math] such that [math]\displaystyle{ \{u,v\}\in E }[/math]. There are two ways to count the directed edges.

First, we can enumerate by edges. Pick every edge [math]\displaystyle{ uv\in E }[/math] and apply two directions [math]\displaystyle{ (u,v) }[/math] and [math]\displaystyle{ (v,u) }[/math] to the edge. This gives us [math]\displaystyle{ 2|E| }[/math] directed edges.

On the other hand, we can enumerate by vertices. Pick every vertex [math]\displaystyle{ v\in V }[/math] and for each of its [math]\displaystyle{ d(v) }[/math] neighbors, say [math]\displaystyle{ u }[/math], generate a directed edge [math]\displaystyle{ (v,u) }[/math]. This gives us [math]\displaystyle{ \sum_{v\in V}d(v) }[/math] directed edges.

It is obvious that the two terms are equal, since we just count the same thing twice with different methods. The lemma follows.

[math]\displaystyle{ \square }[/math]

The handshaking lemma is implied directly by the above lemma, since the sum of even degrees is even.

Cayley's formula

We now present a theorem of the number of labeled trees on a fixed number of vertices. It is due to Cayley in 1889. The theorem is often referred by the name Cayley's formula.

Caylay's formula for trees
There are [math]\displaystyle{ n^{n-2} }[/math] different trees on [math]\displaystyle{ n }[/math] distinct vertices.

The theorem has several proofs. Classical methods include the bijection which encodes a tree by a Prüfer sequence, and through the Kirchhoff's matrix tree theorem. Here we present a proof by double counting, which is considered by the Proofs from THE BOOK "the most beautiful of them all".

Proof.
(Due to Pitman 1999)

Let [math]\displaystyle{ T_n }[/math] be the number of different trees defined on [math]\displaystyle{ n }[/math] distinct vertices.

A rooted tree is a tree with a special vertex. That is, one of the [math]\displaystyle{ n }[/math] vertices is marked as the "root" of the tree. A rooted tree defines a natural direction of all edges, such that an edge [math]\displaystyle{ uv }[/math] of the tree is directed from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ v }[/math] if [math]\displaystyle{ u }[/math] is before [math]\displaystyle{ v }[/math] along the unique path from the root.

We count the number of different sequences of directed edges that can be added to an empty graph on [math]\displaystyle{ n }[/math] vertices to form from it a rooted tree. We note that such a sequence can be formed in two ways:

  1. Starting with an unrooted tree, choose one of its vertices as root, and fix an total order of edges to specify the order in which the edges are added.
  2. Starting from an empty graph, add the edges one by one in steps.

In the first method, we pick one of the [math]\displaystyle{ T_n }[/math] unrooted trees, choose one of the [math]\displaystyle{ n }[/math] vertices as the root, and pick one of the [math]\displaystyle{ (n-1)! }[/math] total orders of the [math]\displaystyle{ n-1 }[/math] edges. This gives us [math]\displaystyle{ T_nn(n-1)!=T_nn! }[/math] ways.

In the second method, we consider the number of choices in one step, and multiply the numbers of choices in all steps. This is done as follows.

Given a sequence of adding [math]\displaystyle{ n-1 }[/math] edges to an empty graph to form a rooted tree, we reverse this sequence and get a sequence of removing edges one by one from the final rooted tree until no edge left. We observe that:

  • At first, we remove an edge from the rooted tree. Suppose that the root of the tree is [math]\displaystyle{ r }[/math], and the removed directed edge is [math]\displaystyle{ (u,v) }[/math]. After removing [math]\displaystyle{ (u,v) }[/math], the original rooted tree is disconnected into two rooted trees, one rooted at [math]\displaystyle{ r }[/math] and the other rooted at [math]\displaystyle{ v }[/math].
  • After removing [math]\displaystyle{ k-1 }[/math] edges, there are [math]\displaystyle{ k }[/math] rooted trees. In the [math]\displaystyle{ k }[/math]th step, a directed edge [math]\displaystyle{ (u,v) }[/math] in the current forest is removed and the tree containing [math]\displaystyle{ (u,v) }[/math] is disconnected into two trees, one rooted at the old root of that tree, and the other rooted at [math]\displaystyle{ v }[/math].

We now again reverse the above procedure, and consider the sequence of adding directed edges to an empty graph to form a rooted tree.

  • At first, we have [math]\displaystyle{ n }[/math] rooted trees, each of 0 edge ([math]\displaystyle{ n }[/math] isolated vertices).
  • After adding [math]\displaystyle{ n-k }[/math] edges, there are [math]\displaystyle{ k }[/math] rooted trees. Denoting the directed edge added next as [math]\displaystyle{ (u,v) }[/math]. As observed above, [math]\displaystyle{ u }[/math] can be any one of the [math]\displaystyle{ n }[/math] vertices; but [math]\displaystyle{ v }[/math] must be the root of one of the [math]\displaystyle{ k }[/math] trees, except the tree which contains [math]\displaystyle{ u }[/math]. There are [math]\displaystyle{ n(k-1) }[/math] choices of such [math]\displaystyle{ (u,v) }[/math].

Multiplying the numbers of choices in all steps, the number of sequences of adding directed edges to an empty graph to form a rooted tree is given by

[math]\displaystyle{ \prod_{k=2}^nn(k-1)=n^{n-2}n! }[/math].

By the principle of double counting, counting the same thing by different methods yield the same result.

[math]\displaystyle{ T_nn!=n^{n-2}n! }[/math],

which gives that [math]\displaystyle{ T_n=n^{n-2} }[/math].

[math]\displaystyle{ \square }[/math]

Cayley's formula

The Pigeonhole Principle

The pigeonhole principle states the following "obvious" fact:

[math]\displaystyle{ n+1 }[/math] pigeons cannot sit in [math]\displaystyle{ n }[/math] holes so that every pigeon is alone in its hole.

More generally, the pigeonhole principle states as the following.

Generalized pigeonhole principle
If a set consisting of more than [math]\displaystyle{ mn }[/math] objects is partitioned into [math]\displaystyle{ n }[/math] classes, then some class receives more than [math]\displaystyle{ m }[/math] objects.

This is one of the oldest non-constructive principles: it states only the existence of a pigeonhole with more than [math]\displaystyle{ m }[/math] pigeons and says nothing about how to find such a pigeonhole.

Monotonic subsequences

Let [math]\displaystyle{ (a_1,a_2,\ldots,a_n) }[/math] be a sequence of [math]\displaystyle{ n }[/math] distinct real numbers. A subsequence is a sequence of distinct terms of [math]\displaystyle{ (a_1,a_2,\ldots,a_n) }[/math] appearing in the same order in which they appear in [math]\displaystyle{ (a_1,a_2,\ldots,a_n) }[/math]. Formally, a subsequence of [math]\displaystyle{ (a_1,a_2,\ldots,a_n) }[/math] is an [math]\displaystyle{ (a_{i_1},a_{i_2},\ldots,a_{i_k}) }[/math], with [math]\displaystyle{ i_1\lt i_2\lt \cdots\lt i_k }[/math].

A sequence [math]\displaystyle{ (a_1,a_2,\ldots,a_n) }[/math] is increasing if [math]\displaystyle{ a_1\lt a_2\lt \cdots\lt a_n }[/math], and decreasing if [math]\displaystyle{ a_1\gt a_2\gt \cdots\gt a_n }[/math].

We are interested in the longest increasing and decreasing subsequences of an [math]\displaystyle{ a_1\lt a_2\lt \cdots\lt a_n }[/math]. It is intuitive that the length of both the longest increasing subsequence and the longest decreasing subsequence cannot be small simultaneously. A famous result of Erdős and Szekeres formally justifies this intuition. This is one of the first results in extremal combinatorics, published in the influential 1935 paper of Erdős and Szekeres.

Theorem (Erdős-Szekeres 1935)
A sequence of more than [math]\displaystyle{ mn }[/math] different real numbers must contain either an increasing subsequence of length [math]\displaystyle{ m+1 }[/math], or a decreasing subsequence of length [math]\displaystyle{ n+1 }[/math].
Proof.
(due to Seidenberg 1959)

Let [math]\displaystyle{ (a_1,a_2,\ldots,a_{N}) }[/math] be the original sequence of [math]\displaystyle{ N\gt mn }[/math] distinct real numbers. Associate each [math]\displaystyle{ a_i }[/math] a pair [math]\displaystyle{ (x_i,y_i) }[/math], defined as:

  • [math]\displaystyle{ x_i }[/math]: the length of the longest increasing subsequence ending at [math]\displaystyle{ a_i }[/math];
  • [math]\displaystyle{ y_i }[/math]: the length of the longest decreasing subsequence starting at [math]\displaystyle{ a_i }[/math].

A key observation is that [math]\displaystyle{ (x_i,y_i)\neq (x_j,y_j) }[/math] whenever [math]\displaystyle{ i\neq j }[/math]. This is proved as follows:

Case 1: If [math]\displaystyle{ a_i\lt a_j }[/math], then the longest increasing subsequence ending at [math]\displaystyle{ a_i }[/math] can be extended by adding on [math]\displaystyle{ a_j }[/math], so [math]\displaystyle{ x_i\lt x_j }[/math].
Case 2: If [math]\displaystyle{ a_i\gt a_j }[/math], then the longest decreasing subsequence starting at [math]\displaystyle{ a_j }[/math] can be preceded by [math]\displaystyle{ a_i }[/math], so [math]\displaystyle{ y_i\gt y_j }[/math].

Now we put [math]\displaystyle{ N }[/math] "pigeons" [math]\displaystyle{ a_1,a_2,\ldots,a_N }[/math] into "pigeonholes" [math]\displaystyle{ \{1,2,\ldots,N\}\times\{1,2,\ldots,N\} }[/math], such that [math]\displaystyle{ a_i }[/math] is put into hole [math]\displaystyle{ (x_i,y_i) }[/math], with at most one pigeon per each hole (since different [math]\displaystyle{ a_i }[/math] has different [math]\displaystyle{ (x_i,y_i) }[/math]).

The number of pigeons is [math]\displaystyle{ N\gt mn }[/math]. Due to pigeonhole principle, there must be a pigeon which is outside the region [math]\displaystyle{ \{1,2,\ldots,m\}\times\{1,2,\ldots,n\} }[/math], which implies that there exists an [math]\displaystyle{ a_i }[/math] with either [math]\displaystyle{ x_i\gt m }[/math] or [math]\displaystyle{ y_i\gt n }[/math]. Due to our definition of [math]\displaystyle{ (x_i,y_i) }[/math], there must be either an increasing subsequence of length [math]\displaystyle{ m+1 }[/math], or a decreasing subsequence of length [math]\displaystyle{ n+1 }[/math].

[math]\displaystyle{ \square }[/math]

Dirichlet's approximation

Let [math]\displaystyle{ x }[/math] be an irrational number. We now want to approximate [math]\displaystyle{ x }[/math] be a rational number (a fraction).

Since every real interval [math]\displaystyle{ [a,b] }[/math] with [math]\displaystyle{ a\lt b }[/math] contains infinitely many rational numbers, there must exist rational numbers arbitrarily close to [math]\displaystyle{ x }[/math]. The trick is to let the denominator of the fraction sufficiently large.

Suppose however we restrict the rationals we may select to have denominators bounded by [math]\displaystyle{ n }[/math]. How closely we can approximate [math]\displaystyle{ x }[/math] now?

The following important theorem is due to Dirichlet and his Schubfachprinzip ("drawer principle"). The theorem is fundamental in numer theory and real analysis, but the proof is combinatorial.

Theorem (Dirichlet 1879)
Let [math]\displaystyle{ x }[/math] be an irrational number. For any natural number [math]\displaystyle{ n }[/math], there is a rational number [math]\displaystyle{ \frac{p}{q} }[/math] such that [math]\displaystyle{ 1\le q\le n }[/math] and
[math]\displaystyle{ \left|x-\frac{p}{q}\right|\lt \frac{1}{nq} }[/math].
Proof.

Let [math]\displaystyle{ \{x\}=x-\lfloor x\rfloor }[/math] denote the fractional part of the real number [math]\displaystyle{ x }[/math]. It is obvious that [math]\displaystyle{ \{x\}\in[0,1) }[/math] for any real number [math]\displaystyle{ x }[/math].

Consider the [math]\displaystyle{ n+1 }[/math] numbers [math]\displaystyle{ \{kx\} }[/math], [math]\displaystyle{ k=1,2,\ldots,n+1 }[/math]. These [math]\displaystyle{ n+1 }[/math] numbers (pigeons) belong to the following [math]\displaystyle{ n }[/math] intervals (pigeonholes):

[math]\displaystyle{ \left(0,\frac{1}{n}\right),\left(\frac{1}{n},\frac{2}{n}\right),\ldots,\left(\frac{n-1}{n},1\right) }[/math].

Since [math]\displaystyle{ x }[/math] is irrational, [math]\displaystyle{ \{kx\} }[/math] cannot coincide with any endpoint of the above intervals.

By the pigeonhole principle, there exist [math]\displaystyle{ 1\le a\lt b\le n+1 }[/math], such that [math]\displaystyle{ \{ax\},\{bx\} }[/math] are in the same interval, thus

[math]\displaystyle{ |\{bx\}-\{ax\}|\lt \frac{1}{n} }[/math].

Therefore,

[math]\displaystyle{ |(b-a)x-\left(\lfloor bx\rfloor-\lfloor ax\rfloor\right)|\lt \frac{1}{n} }[/math].

Let [math]\displaystyle{ q=b-a }[/math] and [math]\displaystyle{ p=\lfloor bx\rfloor-\lfloor ax\rfloor }[/math]. We have [math]\displaystyle{ |qx-p|\lt \frac{1}{n} }[/math] and [math]\displaystyle{ 1\le q\le n }[/math]. Dividing both sides by [math]\displaystyle{ q }[/math], the theorem is proved.

[math]\displaystyle{ \square }[/math]

Pigeonhole vs. resolution proofs

Averaging Principle

References

(声明: 资料受版权保护, 仅用于教学.)
(Disclaimer: The following copyrighted materials are meant for educational uses only.)
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=组合数学_(Fall_2011)/Sieve_methods&oldid=4854"