Combinatorics (Fall 2010)/Partitions, sieve methods
Partitions
We count the ways of partitioning [math]\displaystyle{ n }[/math] identical objects into [math]\displaystyle{ k }[/math] unordered groups. This is equivalent to counting the ways partitioning a number [math]\displaystyle{ n }[/math] into [math]\displaystyle{ k }[/math] unordered parts.
A [math]\displaystyle{ k }[/math]-partition of a number [math]\displaystyle{ n }[/math] is a multiset [math]\displaystyle{ \{x_1,x_2,\ldots,x_k\} }[/math] with [math]\displaystyle{ x_i\ge 1 }[/math] for every element [math]\displaystyle{ x_i }[/math] and [math]\displaystyle{ x_1+x_2+\cdots+x_k=n }[/math].
We define [math]\displaystyle{ p_k(n) }[/math] as the number of [math]\displaystyle{ k }[/math]-partitions of [math]\displaystyle{ n }[/math].
For example, number 7 has the following partitions:
Equivalently, we can also define that A [math]\displaystyle{ k }[/math]-partition of a number [math]\displaystyle{ n }[/math] is a [math]\displaystyle{ k }[/math]-tuple [math]\displaystyle{ (x_1,x_2,\ldots,x_k) }[/math] with:
- [math]\displaystyle{ x_1\ge x_2\ge\cdots\ge x_k\ge 1 }[/math];
- [math]\displaystyle{ x_1+x_2+\cdots+x_k=n }[/math].
[math]\displaystyle{ p_k(n) }[/math] the number of integral solutions to the above system.
Let [math]\displaystyle{ p(n)=\sum_{k=1}^n p_k(n) }[/math] be the total number of partitions of [math]\displaystyle{ n }[/math]. The function [math]\displaystyle{ p(n) }[/math] is called the partition number.
Counting [math]\displaystyle{ p_k(n) }[/math]
We now try to determine [math]\displaystyle{ p_k(n) }[/math]. Unlike most problems we learned in the last lecture, [math]\displaystyle{ p_k(n) }[/math] does not have a nice closed form formula. We now give a recurrence for [math]\displaystyle{ p_k(n) }[/math].
Proposition - [math]\displaystyle{ p_k(n)=p_{k-1}(n-1)+p_k(n-k)\, }[/math].
Proof. Suppose that [math]\displaystyle{ (x_1,\ldots,x_k) }[/math] is a [math]\displaystyle{ k }[/math]-partition of [math]\displaystyle{ n }[/math]. Note that it must hold that
- [math]\displaystyle{ x_1\ge x_2\ge \cdots \ge x_k\ge 1 }[/math].
There are two cases: [math]\displaystyle{ x_k=1 }[/math] or [math]\displaystyle{ x_k\gt 1 }[/math].
- Case 1.
- If [math]\displaystyle{ x_k=1 }[/math], then [math]\displaystyle{ (x_1,\cdots,x_{k-1}) }[/math] is a distinct [math]\displaystyle{ (k-1) }[/math]-partition of [math]\displaystyle{ n-1 }[/math]. And every [math]\displaystyle{ (k-1) }[/math]-partition of [math]\displaystyle{ n-1 }[/math] can be obtained in this way. Thus the number of [math]\displaystyle{ k }[/math]-partitions of [math]\displaystyle{ n }[/math] in this case is [math]\displaystyle{ p_{k-1}(n-1) }[/math].
- Case 2.
- If [math]\displaystyle{ x_k\gt 1 }[/math], then [math]\displaystyle{ (x_1-1,\cdots,x_{k}-1) }[/math] is a distinct [math]\displaystyle{ k }[/math]-partition of [math]\displaystyle{ n-k }[/math]. And every [math]\displaystyle{ k }[/math]-partition of [math]\displaystyle{ n-k }[/math] can be obtained in this way. Thus the number of [math]\displaystyle{ k }[/math]-partitions of [math]\displaystyle{ n }[/math] in this case is [math]\displaystyle{ p_{k}(n-k) }[/math].
In conclusion, the number of [math]\displaystyle{ k }[/math]-partitions of [math]\displaystyle{ n }[/math] is [math]\displaystyle{ p_{k-1}(n-1)+p_k(n-k) }[/math], i.e.
- [math]\displaystyle{ p_k(n)=p_{k-1}(n-1)+p_k(n-k)\, }[/math].
- [math]\displaystyle{ \square }[/math]
Use the above recurrence, we can compute the [math]\displaystyle{ p_k(n) }[/math] for some decent [math]\displaystyle{ n }[/math] and [math]\displaystyle{ k }[/math] by computer simulation.
If we are not restricted ourselves to the precise estimation of [math]\displaystyle{ p_k(n) }[/math], the next theorem gives an asymptotic estimation of [math]\displaystyle{ p_k(n) }[/math]. Note that it only holds for constant [math]\displaystyle{ k }[/math], i.e. [math]\displaystyle{ k }[/math] does not depend on [math]\displaystyle{ n }[/math].
Theorem For any fixed [math]\displaystyle{ k }[/math],
- [math]\displaystyle{ p_k(n)\sim\frac{n^{k-1}}{k!(k-1)!} }[/math],
as [math]\displaystyle{ n\rightarrow \infty }[/math].
Proof. Suppose that [math]\displaystyle{ (x_1,\ldots,x_k) }[/math] is a [math]\displaystyle{ k }[/math]-partition of [math]\displaystyle{ n }[/math]. Then [math]\displaystyle{ x_1+x_2+\cdots+x_k=n }[/math] and [math]\displaystyle{ x_1\ge x_2\ge \cdots \ge x_k\ge 1 }[/math].
The [math]\displaystyle{ k! }[/math] permutations of [math]\displaystyle{ (x_1,\ldots,x_k) }[/math] yield at most [math]\displaystyle{ k! }[/math] many [math]\displaystyle{ k }[/math]-compositions (the ordered sum of [math]\displaystyle{ k }[/math] positive integers). There are [math]\displaystyle{ {n-1\choose k-1} }[/math] many [math]\displaystyle{ k }[/math]-compositions of [math]\displaystyle{ n }[/math], every one of which can be yielded in this way by permuting a partition. Thus,
- [math]\displaystyle{ k!p_k(n)\ge{n-1\choose k-1} }[/math].
Let [math]\displaystyle{ y_i=x_i+k-i }[/math]. That is, [math]\displaystyle{ 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]\displaystyle{ y_1\gt y_2\gt \cdots\gt y_k\ge 1 }[/math]; and
- [math]\displaystyle{ y_1+y_2+\cdots+y_k=n+\frac{k(k-1)}{2} }[/math].
Each permutation of [math]\displaystyle{ (y_1,y_2,\ldots,y_k) }[/math] yields a distinct [math]\displaystyle{ k }[/math]-composition of [math]\displaystyle{ n+\frac{k(k-1)}{2} }[/math], because all [math]\displaystyle{ y_i }[/math] are distinct. Thus,
- [math]\displaystyle{ k!p_k(n)\le {n+\frac{k(k-1)}{2}-1\choose k-1} }[/math].
Combining the two inequalities, we have
- [math]\displaystyle{ \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.
- [math]\displaystyle{ \square }[/math]
Ferrers diagram
A partition of a number [math]\displaystyle{ 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]\displaystyle{ (x_1,x_2,\ldots,x_k) }[/math] with that [math]\displaystyle{ x_1\ge x_2\ge \cdots x_k\ge 1 }[/math] be a partition of [math]\displaystyle{ n }[/math]. Its Ferrers diagram consists of [math]\displaystyle{ k }[/math] rows, where the [math]\displaystyle{ i }[/math]-th row contains [math]\displaystyle{ x_i }[/math] dots (or squares).
|
|
| ||||||||||||||||||||||||
| Ferrers diagram (dot version) of (5,4,2,1) | Ferrers diagram (square version) of (5,4,2,1) |
- Conjugate partition
The partition we get by reading the Ferrers diagram by column instead of rows is called the conjugate of the original partition.
|
|
| ||||||||||||||||||||||||||||||||||
| [math]\displaystyle{ (6,4,4,2,1) }[/math] | conjugate: [math]\displaystyle{ (5,4,3,3,1,1) }[/math] |
Clearly,
- different partitions cannot have the same conjugate, and
- every partition of [math]\displaystyle{ n }[/math] is the conjugate of some partition of [math]\displaystyle{ n }[/math],
so the conjugation mapping is a permutation on the set of partitions of [math]\displaystyle{ 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.
Proposition - The number of partitions of [math]\displaystyle{ n }[/math] which have largest summand [math]\displaystyle{ k }[/math], is [math]\displaystyle{ p_k(n) }[/math].
- The number of [math]\displaystyle{ n }[/math] into [math]\displaystyle{ k }[/math] parts equals the number of partitions of [math]\displaystyle{ n-k }[/math] into at most [math]\displaystyle{ k }[/math] parts. Formally,
- [math]\displaystyle{ p_k(n)=\sum_{j=1}^k p_j(n-k) }[/math].
Proof. - For every [math]\displaystyle{ k }[/math]-partition, the conjugate partition has largest part [math]\displaystyle{ k }[/math]. And vice versa.
- For a [math]\displaystyle{ k }[/math]-partition of [math]\displaystyle{ n }[/math], remove the leftmost cell of every row of the Ferrers diagram. Totally [math]\displaystyle{ k }[/math] cells are removed and the remaining diagram is a partition of [math]\displaystyle{ n-k }[/math] into at most [math]\displaystyle{ k }[/math] parts. And for a partition of [math]\displaystyle{ n-k }[/math] into at most [math]\displaystyle{ k }[/math] parts, add a cell to each of the [math]\displaystyle{ k }[/math] rows (including the empty ones). This will give us a [math]\displaystyle{ k }[/math]-partition of [math]\displaystyle{ n }[/math]. It is easy to see the above mappings are 1-1 correspondences. Thus, the number of [math]\displaystyle{ n }[/math] into [math]\displaystyle{ k }[/math] parts equals the number of partitions of [math]\displaystyle{ n-k }[/math] into at most [math]\displaystyle{ k }[/math] parts.
- [math]\displaystyle{ \square }[/math]
Principle of Inclusion-Exclusion
Let [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] be two finite sets. The cardinality of their union is
- [math]\displaystyle{ |A\cup B|=|A|+|B|-{\color{Blue}|A\cap B|} }[/math].
For three sets [math]\displaystyle{ A }[/math], [math]\displaystyle{ B }[/math], and [math]\displaystyle{ C }[/math], the cardinality of the union of these three sets is computed as
- [math]\displaystyle{ |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.
Generally, the Principle of Inclusion-Exclusion states the rule for computing the union of [math]\displaystyle{ n }[/math] finite sets [math]\displaystyle{ A_1,A_2,\ldots,A_n }[/math], such that
[math]\displaystyle{ \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]\displaystyle{ A_1,A_2,\ldots,A_n\subseteq U }[/math] be subsets of some finite set [math]\displaystyle{ U }[/math]. Here [math]\displaystyle{ U }[/math] is some universe of combinatorial objects, whose cardinality is easy to calculate (e.g. all strings, tuples, permutations), and each [math]\displaystyle{ 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]\displaystyle{ n }[/math] properties. We write [math]\displaystyle{ \bar{A_i}=U-A }[/math]. The number of objects without any of the properties [math]\displaystyle{ A_1,A_2,\ldots,A_n }[/math] is
[math]\displaystyle{ \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]\displaystyle{ I\subseteq\{1,2,\ldots,n\} }[/math], we denote
- [math]\displaystyle{ A_I=\bigcap_{i\in I}A_i }[/math]
with the convention that [math]\displaystyle{ A_\emptyset=U }[/math]. The above equation is stated as:
Principle of Inclusion-Exclusion - Let [math]\displaystyle{ A_1,A_2,\ldots,A_n }[/math] be a family of subsets of [math]\displaystyle{ U }[/math]. Then the number of elements of [math]\displaystyle{ U }[/math] which lie in none of the subsets [math]\displaystyle{ A_i }[/math] is
- [math]\displaystyle{ \sum_{I\subseteq\{1,\ldots, n\}}(-1)^{|I|}|A_I| }[/math].
- Let [math]\displaystyle{ A_1,A_2,\ldots,A_n }[/math] be a family of subsets of [math]\displaystyle{ U }[/math]. Then the number of elements of [math]\displaystyle{ U }[/math] which lie in none of the subsets [math]\displaystyle{ A_i }[/math] is
Let [math]\displaystyle{ S_k=\sum_{|I|=k}|A_I|\, }[/math]. Conventionally, [math]\displaystyle{ S_0=|A_\emptyset|=|U| }[/math]. The principle of inclusion-exclusion can be expressed as
Surjections
In the twelvefold way, we discuss the counting problems incurred by the mappings [math]\displaystyle{ f:N\rightarrow M }[/math]. The basic case is that elements from both [math]\displaystyle{ N }[/math] and [math]\displaystyle{ M }[/math] are distinguishable. In this case, it is easy to count the number of arbitrary mappings (which is [math]\displaystyle{ m^n }[/math]) and the number of injective (one-to-one) mappings (which is [math]\displaystyle{ (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 - The number of surjective mappings from an [math]\displaystyle{ n }[/math]-set to an [math]\displaystyle{ m }[/math]-set is given by
- [math]\displaystyle{ \sum_{k=1}^m(-1)^{m-k}{m\choose k}k^n }[/math].
- The number of surjective mappings from an [math]\displaystyle{ n }[/math]-set to an [math]\displaystyle{ m }[/math]-set is given by
Proof. Let [math]\displaystyle{ U=\{f:[n]\rightarrow[m]\} }[/math] be the set of mappings from [math]\displaystyle{ [n] }[/math] to [math]\displaystyle{ [m] }[/math]. Then [math]\displaystyle{ |U|=m^n }[/math].
For [math]\displaystyle{ i\in[m] }[/math], let [math]\displaystyle{ A_i }[/math] be the set of mappings [math]\displaystyle{ f:[n]\rightarrow[m] }[/math] that none of [math]\displaystyle{ j\in[n] }[/math] is mapped to [math]\displaystyle{ i }[/math], i.e. [math]\displaystyle{ A_i=\{f:[n]\rightarrow[m]\setminus\{i\}\} }[/math], thus [math]\displaystyle{ |A_i|=(m-1)^n }[/math].
More generally, for [math]\displaystyle{ I\subseteq [m] }[/math], [math]\displaystyle{ A_I=\bigcap_{i\in I}A_i }[/math] contains the mappings [math]\displaystyle{ f:[n]\rightarrow[m]\setminus I }[/math]. And [math]\displaystyle{ |A_I|=(m-|I|)^n\, }[/math].
A mapping [math]\displaystyle{ f:[n]\rightarrow[m] }[/math] is surjective if [math]\displaystyle{ f }[/math] lies in none of [math]\displaystyle{ A_i }[/math]. By the principle of inclusion-exclusion, the number of surjective [math]\displaystyle{ f:[n]\rightarrow[m] }[/math] is
- [math]\displaystyle{ \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]\displaystyle{ k=m-j }[/math]. The theorem is proved.
- [math]\displaystyle{ \square }[/math]
Recall that, in the twelvefold way, we establish a relation between surjections and partitions.
- Surjection to ordered partition:
- For a surjective [math]\displaystyle{ f:[n]\rightarrow[m] }[/math], [math]\displaystyle{ (f^{-1}(0),f^{-1}(1),\ldots,f^{-1}(m-1)) }[/math] is an ordered partition of [math]\displaystyle{ [n] }[/math].
- Ordered partition to surjection:
- For an ordered [math]\displaystyle{ m }[/math]-partition [math]\displaystyle{ (B_0,B_1,\ldots, B_{m-1}) }[/math] of [math]\displaystyle{ [n] }[/math], we can define a function [math]\displaystyle{ f:[n]\rightarrow[m] }[/math] by letting [math]\displaystyle{ f(i)=j }[/math] if and only if [math]\displaystyle{ i\in B_j }[/math]. [math]\displaystyle{ f }[/math] is surjective since as a partition, none of [math]\displaystyle{ B_i }[/math] is empty.
Therefore, we have a one-to-one correspondence between surjective mappings from an [math]\displaystyle{ n }[/math]-set to an [math]\displaystyle{ m }[/math]-set and the ordered [math]\displaystyle{ m }[/math]-partitions of an [math]\displaystyle{ n }[/math]-set.
The Stirling number of the second kind [math]\displaystyle{ S(n,m) }[/math] is the number of [math]\displaystyle{ m }[/math]-partitions of an [math]\displaystyle{ n }[/math]-set. There are [math]\displaystyle{ m! }[/math] ways to order an [math]\displaystyle{ m }[/math]-partition, thus the number of surjective mappings [math]\displaystyle{ f:[n]\rightarrow[m] }[/math] is [math]\displaystyle{ 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.
Proposition - [math]\displaystyle{ 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]\displaystyle{ \pi }[/math] of [math]\displaystyle{ \{1,2,\ldots,n\} }[/math], a fixed point is such an [math]\displaystyle{ i\in\{1,2,\ldots,n\} }[/math] that [math]\displaystyle{ \pi(i)=i }[/math]. A derangement of [math]\displaystyle{ \{1,2,\ldots,n\} }[/math] is a permutation of [math]\displaystyle{ \{1,2,\ldots,n\} }[/math] that has no fixed points.
Theorem - The number of derangements of [math]\displaystyle{ \{1,2,\ldots,n\} }[/math] given by
- [math]\displaystyle{ n!\sum_{k=0}^n\frac{(-1)^k}{k!}\approx \frac{n!}{\mathrm{e}} }[/math].
- The number of derangements of [math]\displaystyle{ \{1,2,\ldots,n\} }[/math] given by
Proof. Let [math]\displaystyle{ U }[/math] be the set of all permutations of [math]\displaystyle{ \{1,2,\ldots,n\} }[/math]. So [math]\displaystyle{ |U|=n! }[/math].
Let [math]\displaystyle{ A_i }[/math] be the set of permutations with fixed point [math]\displaystyle{ i }[/math]; so [math]\displaystyle{ |A_i|=(n-1)! }[/math]. More generally, for any [math]\displaystyle{ I\subseteq \{1,2,\ldots,n\} }[/math], [math]\displaystyle{ A_I=\bigcap_{i\in I}A_i }[/math], and [math]\displaystyle{ |A_I|=(n-|I|)! }[/math], since permutations in [math]\displaystyle{ A_I }[/math] fix every point in [math]\displaystyle{ 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]\displaystyle{ A_i }[/math]. So the number of derangements is
- [math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ n!\sum_{k=0}^n\frac{(-1)^k}{k!} }[/math] is the closest integer to [math]\displaystyle{ \frac{n!}{\mathrm{e}} }[/math].
- [math]\displaystyle{ \square }[/math]
Therefore, there are about [math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ B\subseteq \{1,\ldots,n\}\times \{1,\ldots,n\} }[/math], called a board. As illustrated below, we can think of [math]\displaystyle{ B }[/math] as a chess board, with the positions in [math]\displaystyle{ B }[/math] marked by "[math]\displaystyle{ \times }[/math]".
|
a | b | c | d | e | f | g | h |
|
| 8 | 
|
|
|
|
|
|
|
|
8 |
| 7 |
|
|
|
|
|
|
|
|
7 |
| 6 |
|
|
|
|
|
|
|
|
6 |
| 5 |
|
|
|
|
|
|
|
|
5 |
| 4 |
|
|
|
|
|
|
|
|
4 |
| 3 |
|
|
|
|
|
|
|
|
3 |
| 2 |
|
|
|
|
|
|
|
|
2 |
| 1 |
|
|
|
|
|
|
|
|
1 |
|
|
a | b | c | d | e | f | g | h |
|
For a permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ \{1,\ldots,n\} }[/math], define the graph [math]\displaystyle{ G_\pi(V,E) }[/math] as
- [math]\displaystyle{ \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]\displaystyle{ \pi }[/math] is a permutation. Thus, we can identify each [math]\displaystyle{ G_\pi }[/math] as a placement of [math]\displaystyle{ n }[/math] rooks (“城堡”，规则同中国象棋里的“车”) without attacking each other.
For example, the following is the [math]\displaystyle{ G_\pi }[/math] of such [math]\displaystyle{ \pi }[/math] that [math]\displaystyle{ \pi(i)=i }[/math].
|
|
a | b | c | d | e | f | g | h |
|
| 8 | 
|
|
|
|
|
|
|
|
8 |
| 7 |
|
|
|
|
|
|
|
|
7 |
| 6 |
|
|
|
|
|
|
|
|
6 |
| 5 |
|
|
|
|
|
|
|
|
5 |
| 4 |
|
|
|
|
|
|
|
|
4 |
| 3 |
|
|
|
|
|
|
|
|
3 |
| 2 |
|
|
|
|
|
|
|
|
2 |
| 1 |
|
|
|
|
|
|
|
|
1 |
|
|
a | b | c | d | e | f | g | h |
|
Now define
- [math]\displaystyle{ \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]\displaystyle{ B }[/math]: a set of marked positions in an [math]\displaystyle{ [n]\times [n] }[/math] chess board.
- [math]\displaystyle{ N_0 }[/math]: the number of ways of placing [math]\displaystyle{ n }[/math] non-attacking rooks on the chess board such that none of these rooks lie in [math]\displaystyle{ B }[/math].
- [math]\displaystyle{ r_k }[/math]: number of ways of placing [math]\displaystyle{ k }[/math] non-attacking rooks on [math]\displaystyle{ B }[/math].
Our goal is to count [math]\displaystyle{ N_0 }[/math] in terms of [math]\displaystyle{ r_k }[/math]. This gives the number of permutations avoid all positions in a [math]\displaystyle{ B }[/math].
Theorem - [math]\displaystyle{ N_0=\sum_{k=0}^n(-1)^kr_k(n-k)! }[/math].
Proof. For each [math]\displaystyle{ i\in[n] }[/math], let [math]\displaystyle{ A_i=\{\pi\mid (i,\pi(i))\in B\} }[/math] be the set of permutations [math]\displaystyle{ \pi }[/math] whose [math]\displaystyle{ i }[/math]-th position is in [math]\displaystyle{ B }[/math].
[math]\displaystyle{ N_0 }[/math] is the number of permutations avoid all positions in [math]\displaystyle{ B }[/math]. Thus, our goal is to count the number of permutations [math]\displaystyle{ \pi }[/math] in none of [math]\displaystyle{ A_i }[/math] for [math]\displaystyle{ i\in [n] }[/math].
For each [math]\displaystyle{ I\subseteq [n] }[/math], let [math]\displaystyle{ A_I=\bigcap_{i\in I}A_i }[/math], which is the set of permutations [math]\displaystyle{ \pi }[/math] such that [math]\displaystyle{ (i,\pi(i))\in B }[/math] for all [math]\displaystyle{ i\in I }[/math]. Due to the principle of inclusion-exclusion,
- [math]\displaystyle{ 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]\displaystyle{ \sum_{I\in{[n]\choose k}}|A_I|=r_k(n-k)! }[/math],
because we can count both sides by first placing [math]\displaystyle{ k }[/math] non-attacking rooks on [math]\displaystyle{ B }[/math] and placing [math]\displaystyle{ n-k }[/math] additional non-attacking rooks on [math]\displaystyle{ [n]\times [n] }[/math] in [math]\displaystyle{ (n-k)! }[/math] ways.
Therefore,
- [math]\displaystyle{ N_0=\sum_{k=0}^n(-1)^kr_k(n-k)! }[/math].
- [math]\displaystyle{ \square }[/math]
Derangement problem
We use the above general method to solve the derange problem again.
Take [math]\displaystyle{ B=\{(1,1),(2,2),\ldots,(n,n)\} }[/math] as the chess board. A derangement [math]\displaystyle{ \pi }[/math] is a placement of [math]\displaystyle{ n }[/math] non-attacking rooks such that none of them is in [math]\displaystyle{ B }[/math].
|
|
a | b | c | d | e | f | g | h |
|
| 8 |
|
|
|
|
|
|
|
|
8 |
| 7 |
|
|
|
|
|
|
|
|
7 |
| 6 |
|
|
|
|
|
|
|
|
6 |
| 5 |
|
|
|
|
|
|
|
|
5 |
| 4 |
|
|
|
|
|
|
|
|
4 |
| 3 |
|
|
|
|
|
|
|
|
3 |
| 2 |
|
|
|
|
|
|
|
|
2 |
| 1 |
|
|
|
|
|
|
|
|
1 |
|
|
a | b | c | d | e | f | g | h |
|
Clearly, the number of ways of placing [math]\displaystyle{ k }[/math] non-attacking rooks on [math]\displaystyle{ B }[/math] is [math]\displaystyle{ r_k={n\choose k} }[/math]. We want to count [math]\displaystyle{ N_0 }[/math], which gives the number of ways of placing [math]\displaystyle{ n }[/math] non-attacking rooks such that none of these rooks lie in [math]\displaystyle{ B }[/math].
By the above theorem
- [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ n! }[/math] different orders. Thus, there are [math]\displaystyle{ 2(n!) }[/math] ways to seat the [math]\displaystyle{ n }[/math] ladies.
After sitting the wives, we label the remaining [math]\displaystyle{ n }[/math] places clockwise as [math]\displaystyle{ 0,1,\ldots, n-1 }[/math]. And a seating of the [math]\displaystyle{ n }[/math] husbands is given by a permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [n] }[/math] defined as follows. Let [math]\displaystyle{ \pi(i) }[/math] be the seat of the husband of he lady sitting at the [math]\displaystyle{ i }[/math]-th place.
It is easy to see that [math]\displaystyle{ \pi }[/math] satisfies that [math]\displaystyle{ \pi(i)\neq i }[/math] and [math]\displaystyle{ \pi(i)\not\equiv i+1\pmod n }[/math], and every permutation [math]\displaystyle{ \pi }[/math] with these properties gives a feasible seating of the [math]\displaystyle{ n }[/math] husbands. Thus, we only need to count the number of permutations [math]\displaystyle{ \pi }[/math] such that [math]\displaystyle{ \pi(i)\not\equiv i, i+1\pmod n }[/math].
Take [math]\displaystyle{ 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]\displaystyle{ \pi }[/math] which defines a way of seating the husbands, is a placement of [math]\displaystyle{ n }[/math] non-attacking rooks such that none of them is in [math]\displaystyle{ B }[/math].
|
|
a | b | c | d | e | f | g | h |
|
| 8 |
|
|
|
|
|
|
|
|
8 |
| 7 |
|
|
|
|
|
|
|
|
7 |
| 6 |
|
|
|
|
|
|
|
|
6 |
| 5 |
|
|
|
|
|
|
|
|
5 |
| 4 |
|
|
|
|
|
|
|
|
4 |
| 3 |
|
|
|
|
|
|
|
|
3 |
| 2 |
|
|
|
|
|
|
|
|
2 |
| 1 |
|
|
|
|
|
|
|
|
1 |
|
|
a | b | c | d | e | f | g | h |
|
We need to compute [math]\displaystyle{ r_k }[/math], the number of ways of placing [math]\displaystyle{ k }[/math] non-attacking rooks on [math]\displaystyle{ B }[/math]. For our choice of [math]\displaystyle{ B }[/math], [math]\displaystyle{ r_k }[/math] is the number of ways of choosing [math]\displaystyle{ k }[/math] points, no two consecutive, from a collection of [math]\displaystyle{ 2n }[/math] points arranged in a circle.
We first see how to do this in a line.
Lemma - The number of ways of choosing [math]\displaystyle{ k }[/math] non-consecutive objects from a collection of [math]\displaystyle{ m }[/math] objects arranged in a line, is [math]\displaystyle{ {m-k+1\choose k} }[/math].
Proof. We draw a line of [math]\displaystyle{ m-k }[/math] black points, and then insert [math]\displaystyle{ k }[/math] red points into the [math]\displaystyle{ m-k+1 }[/math] spaces between the black points (including the beginning and end).
- [math]\displaystyle{ \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]\displaystyle{ m }[/math] points, and the red points specifies the chosen objects, which are non-consecutive. The mapping is 1-1 correspondence. There are [math]\displaystyle{ {m-k+1\choose k} }[/math] ways of placing [math]\displaystyle{ k }[/math] red points into [math]\displaystyle{ m-k+1 }[/math] spaces.
- [math]\displaystyle{ \square }[/math]
The problem of choosing non-consecutive objects in a circle can be reduced to the case that the objects are in a line.
Lemma - The number of ways of choosing [math]\displaystyle{ k }[/math] non-consecutive objects from a collection of [math]\displaystyle{ m }[/math] objects arranged in a circle, is [math]\displaystyle{ \frac{m}{m-k}{m-k\choose k} }[/math].
Proof. Let [math]\displaystyle{ f(m,k) }[/math] be the desired number; and let [math]\displaystyle{ g(m,k) }[/math] be the number of ways of choosing [math]\displaystyle{ k }[/math] non-consecutive points from [math]\displaystyle{ m }[/math] points arranged in a circle, next coloring the [math]\displaystyle{ k }[/math] points red, and then coloring one of the uncolored point blue.
Clearly, [math]\displaystyle{ g(m,k)=(m-k)f(m,k) }[/math].
But we can also compute [math]\displaystyle{ g(m,k) }[/math] as follows:
- Choose one of the [math]\displaystyle{ m }[/math] points and color it blue. This gives us [math]\displaystyle{ m }[/math] ways.
- Cut the circle to make a line of [math]\displaystyle{ m-1 }[/math] points by removing the blue point.
- Choose [math]\displaystyle{ k }[/math] non-consecutive points from the line of [math]\displaystyle{ m-1 }[/math] points and color them red. This gives [math]\displaystyle{ {m-k\choose k} }[/math] ways due to the previous lemma.
Thus, [math]\displaystyle{ g(m,k)=m{m-k\choose k} }[/math]. Therefore we have the desired number [math]\displaystyle{ f(m,k)=\frac{m}{m-k}{m-k\choose k} }[/math].
- [math]\displaystyle{ \square }[/math]
By the above lemma, we have that [math]\displaystyle{ r_k=\frac{2n}{2n-k}{2n-k\choose k} }[/math]. Then apply the theorem of counting permutations with restricted positions,
- [math]\displaystyle{ 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]\displaystyle{ n }[/math] husbands after the ladies are seated. Recall that there are [math]\displaystyle{ 2n! }[/math] ways of seating the [math]\displaystyle{ n }[/math] ladies. Thus, the total number of ways of seating [math]\displaystyle{ n }[/math] couples as required by problème des ménages is
- [math]\displaystyle{ 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]\displaystyle{ m, n }[/math] are said to be relatively prime if their greatest common diviser [math]\displaystyle{ \mathrm{gcd}(m,n)=1 }[/math]. For a positive integer [math]\displaystyle{ n }[/math], let [math]\displaystyle{ \phi(n) }[/math] be the number of positive integers from [math]\displaystyle{ \{1,2,\ldots,n\} }[/math] that are relative prime to [math]\displaystyle{ n }[/math]. This function, called the Euler [math]\displaystyle{ \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 (The Euler totient function) Suppose [math]\displaystyle{ n }[/math] is divisible by precisely [math]\displaystyle{ r }[/math] different primes, denoted [math]\displaystyle{ p_1,\ldots,p_r }[/math]. Then
- [math]\displaystyle{ \phi(n)=n\prod_{i=1}^r\left(1-\frac{1}{p_i}\right) }[/math].
Proof. Let [math]\displaystyle{ U=\{1,2,\ldots,n\} }[/math] be the universe. The number of positive integers from [math]\displaystyle{ U }[/math] which is divisible by some [math]\displaystyle{ p_{i_1},p_{i_2},\ldots,p_{i_s}\in\{p_1,\ldots,p_r\} }[/math], is [math]\displaystyle{ \frac{n}{p_{i_1}p_{i_2}\cdots p_{i_s}} }[/math].
[math]\displaystyle{ \phi(n) }[/math] is the number of integers from [math]\displaystyle{ U }[/math] which is not divisible by any [math]\displaystyle{ p_1,\ldots,p_r }[/math]. By principle of inclusion-exclusion,
- [math]\displaystyle{ \begin{align} \phi(n) &=n+\sum_{k=1}^r(-1)^k\sum_{1\le i_1\lt i_2\lt \cdots \lt 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\lt j\le n}\frac{n}{p_i p_j}-\sum_{1\le i\lt j\lt 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\lt j\le n}\frac{1}{p_i p_j}-\sum_{1\le i\lt j\lt 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]
- [math]\displaystyle{ \square }[/math]
Reference
- Stanley, Enumerative Combinatorics, Volume 1, Chapter 2.
- van Lin and Wilson, A course in combinatorics, Chapter 10, 15.