View source for Combinatorics (Fall 2010)/Partitions, sieve methods

== Partitions ==
We count the ways of partitioning <math>n</math> ''identical'' objects into <math>k</math> ''unordered'' groups. This is equivalent to counting the ways partitioning a number <math>n</math> into <math>k</math> unordered parts.

A '''<math>k</math>-partition''' of a number <math>n</math> is a multiset <math>\{x_1,x_2,\ldots,x_k\}</math> with <math>x_i\ge 1</math> for every element <math>x_i</math> and <math>x_1+x_2+\cdots+x_k=n</math>.

We define <math>p_k(n)</math> as the number of <math>k</math>-partitions of <math>n</math>.

For example, number 7 has the following partitions:
<div class="center"><math>
\begin{align}
&\{7\}
& p_1(7)=1\\
&\{1,6\},\{2,5\},\{3,4\}
& p_2(7)=3\\
&\{1,1,5\}, \{1,2,4\}, \{1,3,3\}, \{2,2,3\} 
& p_3(7)=4\\
&\{1,1,1,4\},\{1,1,2,3\}, \{1,2,2,2\}
& p_4(7)=3\\
&\{1,1,1,1,3\},\{1,1,1,2,2\}
& p_5(7)=2\\
&\{1,1,1,1,1,2\}
& p_6(7)=1\\
&\{1,1,1,1,1,1,1\}
& p_7(7)=1
\end{align}
</math></div>

Equivalently, we can also define that A <math>k</math>-partition of a number <math>n</math> is a <math>k</math>-tuple <math>(x_1,x_2,\ldots,x_k)</math> with:
* <math>x_1\ge x_2\ge\cdots\ge x_k\ge 1</math>;
* <math>x_1+x_2+\cdots+x_k=n</math>.

<math>p_k(n)</math> the number of integral solutions to the above system.

Let <math>p(n)=\sum_{k=1}^n p_k(n)</math> be the total number of partitions of <math>n</math>. The function <math>p(n)</math> is called the '''partition number'''.

=== Counting <math>p_k(n)</math>===
We now try to determine <math>p_k(n)</math>. Unlike most problems we learned in the last lecture, <math>p_k(n)</math> does not have a nice closed form formula. We now give a recurrence for <math>p_k(n)</math>.

{{Theorem|Proposition|
:<math>p_k(n)=p_{k-1}(n-1)+p_k(n-k)\,</math>.
}}
{{Proof|
Suppose that <math>(x_1,\ldots,x_k)</math> is a <math>k</math>-partition of <math>n</math>. Note that it must hold that
:<math>x_1\ge x_2\ge \cdots \ge x_k\ge 1</math>.
There are two cases: <math>x_k=1</math> or <math>x_k>1</math>.
;Case 1.
:If <math>x_k=1</math>, then <math>(x_1,\cdots,x_{k-1})</math> is a distinct <math>(k-1)</math>-partition of <math>n-1</math>. And every <math>(k-1)</math>-partition of <math>n-1</math> can be obtained in this way. Thus the number of <math>k</math>-partitions of <math>n</math> in this case is <math>p_{k-1}(n-1)</math>. 
;Case 2.
:If <math>x_k>1</math>, then <math>(x_1-1,\cdots,x_{k}-1)</math> is a distinct <math>k</math>-partition of <math>n-k</math>. And every <math>k</math>-partition of <math>n-k</math> can be obtained in this way. Thus the number of <math>k</math>-partitions of <math>n</math> in this case is <math>p_{k}(n-k)</math>. 
In conclusion, the number of <math>k</math>-partitions of <math>n</math> is <math>p_{k-1}(n-1)+p_k(n-k)</math>, i.e.
:<math>p_k(n)=p_{k-1}(n-1)+p_k(n-k)\,</math>.
}}

Use the above recurrence, we can compute the <math>p_k(n)</math>  for some decent <math>n</math> and <math>k</math> by computer simulation.

If we are not restricted ourselves to the precise estimation of <math>p_k(n)</math>, the next theorem gives an asymptotic estimation of <math>p_k(n)</math>. Note that it only holds for '''constant''' <math>k</math>, i.e. <math>k</math> does not depend on <math>n</math>.

{{Theorem|Theorem|
For any fixed <math>k</math>,
:<math>p_k(n)\sim\frac{n^{k-1}}{k!(k-1)!}</math>,
as <math>n\rightarrow \infty</math>.
}}
{{Proof|
Suppose that <math>(x_1,\ldots,x_k)</math> is a <math>k</math>-partition of <math>n</math>. Then <math>x_1+x_2+\cdots+x_k=n</math> and <math>x_1\ge x_2\ge \cdots \ge x_k\ge 1</math>.

The <math>k!</math> permutations of <math>(x_1,\ldots,x_k)</math> yield at most <math>k!</math> many <math>k</math>-compositions (the ''ordered'' sum of <math>k</math> positive integers). There are <math>{n-1\choose k-1}</math> many <math>k</math>-compositions of <math>n</math>, every one of which can be yielded in this way by permuting a partition. Thus,
:<math>k!p_k(n)\ge{n-1\choose k-1}</math>.

Let <math>y_i=x_i+k-i</math>. That is, <math>y_k=x_k, y_{k-1}=x_k+1, y_{k-2}=x_k+2,\ldots, y_{1}=x_k+k-1</math>. Then, it holds that
* <math>y_1>y_2>\cdots>y_k\ge 1</math>; and 
* <math>y_1+y_2+\cdots+y_k=n+\frac{k(k-1)}{2}</math>.
Each permutation of <math>(y_1,y_2,\ldots,y_k)</math> yields a '''distinct''' <math>k</math>-composition of <math>n+\frac{k(k-1)}{2}</math>, because all <math>y_i</math> are distinct.
Thus, 
:<math>k!p_k(n)\le {n+\frac{k(k-1)}{2}-1\choose k-1}</math>.

Combining the two inequalities, we have
:<math>\frac{{n-1\choose k-1}}{k!}\le p_k(n)\le \frac{{n+\frac{k(k-1)}{2}-1\choose k-1}}{k!}</math>.
The theorem follows.
}}

=== Ferrers diagram ===
A partition of a number <math>n</math> can be represented as a diagram of dots (or squares), called a '''Ferrers diagram''' (the square version of Ferrers diagram is also called a '''Young diagram''', named after a structured called Young tableaux). 

Let <math>(x_1,x_2,\ldots,x_k)</math> with that <math>x_1\ge x_2\ge \cdots x_k\ge 1</math> be a partition of <math>n</math>. Its Ferrers diagram consists of <math>k</math> rows, where the <math>i</math>-th row contains <math>x_i</math> dots (or squares).

<div class="center">
{|border="0"
|
{|border="0"
|[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]
|-
|[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]
|-
|[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]
|-
|[[File:Chess xot45.svg|22px]]
|}
|
[[File:Chess t45.svg|120px]]
|align=center|
{|border="2"  cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]
|}
|-
|align=center|Ferrers diagram (''dot version'') of (5,4,2,1)||
|align=center|Ferrers diagram (''square version'') of (5,4,2,1)
|}
</div>

;Conjugate partition
The partition we get by reading the Ferrers diagram by column instead of rows is called the '''conjugate''' of the original partition.
<div class="center">
{|border="0"
|align=center|
{|border="2"  cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]
|}
|
[[File:Chess t45.svg|120px]]
|align=center|
{|border="2"  cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]
|}
|-
|align=center|<math>(6,4,4,2,1)</math>||
|align=center|conjugate: <math>(5,4,3,3,1,1)</math>
|}
</div>

Clearly, 
* different partitions cannot have the same conjugate, and 
* every partition of <math>n</math> is the conjugate of some partition of <math>n</math>,
so the conjugation mapping is a permutation on the set of partitions of <math>n</math>. This fact is very useful in proving theorems for partitions numbers.

Some theorems of partitions can be easily proved by representing partitions in Ferrers diagrams.

{{Theorem|Proposition|
# The number of partitions of <math>n</math> which have largest summand <math>k</math>, is <math>p_k(n)</math>. 
# The number of <math>n</math> into <math>k</math> parts equals the number of partitions of <math>n-k</math> into at most <math>k</math> parts. Formally,
::<math>p_k(n)=\sum_{j=1}^k p_j(n-k)</math>.
}}
{{Proof|
# For every <math>k</math>-partition, the conjugate partition has largest part <math>k</math>. And vice versa.
# For a <math>k</math>-partition of <math>n</math>, remove the leftmost cell of every row of the Ferrers diagram. Totally <math>k</math> cells are removed and the remaining diagram is a partition of <math>n-k</math> into at most <math>k</math> parts. And for a partition of <math>n-k</math> into at most <math>k</math> parts, add a cell to each of the <math>k</math> rows (including the empty ones). This will give us a <math>k</math>-partition of <math>n</math>. It is easy to see the above mappings are 1-1 correspondences. Thus, the number of <math>n</math> into <math>k</math> parts equals the number of partitions of <math>n-k</math> into at most <math>k</math> parts.
}}

== Principle of Inclusion-Exclusion ==
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
{{Equation|
<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.

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</math>. The number of objects without any of the properties <math>A_1,A_2,\ldots,A_n</math> is
{{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
{{Equation|<math>
S_0-S_1+S_2+\cdots+(-1)^nS_n.
</math>
}}

=== Surjections ===
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.
{{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>.

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>.

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
:<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.

* 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|
:<math>S(n,m)=\frac{1}{m!}\sum_{k=1}^m(-1)^{m-k}{m\choose k}k^n</math>.
}}

=== 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 <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>.
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|
:The number of derangements of <math>\{1,2,\ldots,n\}</math> given by
::<math>n!\sum_{k=0}^n\frac{(-1)^k}{k!}\approx \frac{n!}{\mathrm{e}}</math>.
}}
{{Proof|
Let <math>U</math> be the set of all permutations of <math>\{1,2,\ldots,n\}</math>. So <math>|U|=n!</math>.

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
:<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>.

{{Theorem|Theorem|
:<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>.

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,
:<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>.

The next observation is that 
:<math>\sum_{I\in{[n]\choose k}}|A_I|=r_k(n-k)!</math>,
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====
We use the above general method to solve the derange problem again.

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>. 
{{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
:<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====
Suppose that in a banquet, we want to seat <math>n</math> 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 <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.

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.

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>.

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>. 
{{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.

{{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>.
}}
{{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>.

But we can also compute <math>g(m,k)</math> as follows:
* Choose one of the <math>m</math> points and color it blue. This gives us <math>m</math> ways.
* 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>.
}}

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,
:<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 
:<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 know 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|
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>. 

<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>.
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>
}}

== Reference ==
* ''Stanley,'' Enumerative Combinatorics, Volume 1, Chapter 2.
* "van Lin and Wilson", A course in combinatorics, Chapter 10, 15.