# Combinatorics (Fall 2010)/Partitions, sieve methods

## Partitions

We count the ways of partitioning ${\displaystyle n}$ identical objects into ${\displaystyle k}$ unordered groups. This is equivalent to counting the ways partitioning a number ${\displaystyle n}$ into ${\displaystyle k}$ unordered parts.

A ${\displaystyle k}$-partition of a number ${\displaystyle n}$ is a multiset ${\displaystyle \{x_{1},x_{2},\ldots ,x_{k}\}}$ with ${\displaystyle x_{i}\geq 1}$ for every element ${\displaystyle x_{i}}$ and ${\displaystyle x_{1}+x_{2}+\cdots +x_{k}=n}$.

We define ${\displaystyle p_{k}(n)}$ as the number of ${\displaystyle k}$-partitions of ${\displaystyle n}$.

For example, number 7 has the following partitions:

{\displaystyle {\begin{aligned}&\{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{aligned}}}

Equivalently, we can also define that A ${\displaystyle k}$-partition of a number ${\displaystyle n}$ is a ${\displaystyle k}$-tuple ${\displaystyle (x_{1},x_{2},\ldots ,x_{k})}$ with:

• ${\displaystyle x_{1}\geq x_{2}\geq \cdots \geq x_{k}\geq 1}$;
• ${\displaystyle x_{1}+x_{2}+\cdots +x_{k}=n}$.

${\displaystyle p_{k}(n)}$ the number of integral solutions to the above system.

Let ${\displaystyle p(n)=\sum _{k=1}^{n}p_{k}(n)}$ be the total number of partitions of ${\displaystyle n}$. The function ${\displaystyle p(n)}$ is called the partition number.

### Counting ${\displaystyle p_{k}(n)}$

We now try to determine ${\displaystyle p_{k}(n)}$. Unlike most problems we learned in the last lecture, ${\displaystyle p_{k}(n)}$ does not have a nice closed form formula. We now give a recurrence for ${\displaystyle p_{k}(n)}$.

 Proposition ${\displaystyle p_{k}(n)=p_{k-1}(n-1)+p_{k}(n-k)\,}$.
Proof.
 Suppose that ${\displaystyle (x_{1},\ldots ,x_{k})}$ is a ${\displaystyle k}$-partition of ${\displaystyle n}$. Note that it must hold that ${\displaystyle x_{1}\geq x_{2}\geq \cdots \geq x_{k}\geq 1}$. There are two cases: ${\displaystyle x_{k}=1}$ or ${\displaystyle x_{k}>1}$. Case 1. If ${\displaystyle x_{k}=1}$, then ${\displaystyle (x_{1},\cdots ,x_{k-1})}$ is a distinct ${\displaystyle (k-1)}$-partition of ${\displaystyle n-1}$. And every ${\displaystyle (k-1)}$-partition of ${\displaystyle n-1}$ can be obtained in this way. Thus the number of ${\displaystyle k}$-partitions of ${\displaystyle n}$ in this case is ${\displaystyle p_{k-1}(n-1)}$. Case 2. If ${\displaystyle x_{k}>1}$, then ${\displaystyle (x_{1}-1,\cdots ,x_{k}-1)}$ is a distinct ${\displaystyle k}$-partition of ${\displaystyle n-k}$. And every ${\displaystyle k}$-partition of ${\displaystyle n-k}$ can be obtained in this way. Thus the number of ${\displaystyle k}$-partitions of ${\displaystyle n}$ in this case is ${\displaystyle p_{k}(n-k)}$. In conclusion, the number of ${\displaystyle k}$-partitions of ${\displaystyle n}$ is ${\displaystyle p_{k-1}(n-1)+p_{k}(n-k)}$, i.e. ${\displaystyle p_{k}(n)=p_{k-1}(n-1)+p_{k}(n-k)\,}$.
${\displaystyle \square }$

Use the above recurrence, we can compute the ${\displaystyle p_{k}(n)}$ for some decent ${\displaystyle n}$ and ${\displaystyle k}$ by computer simulation.

If we are not restricted ourselves to the precise estimation of ${\displaystyle p_{k}(n)}$, the next theorem gives an asymptotic estimation of ${\displaystyle p_{k}(n)}$. Note that it only holds for constant ${\displaystyle k}$, i.e. ${\displaystyle k}$ does not depend on ${\displaystyle n}$.

 Theorem For any fixed ${\displaystyle k}$, ${\displaystyle p_{k}(n)\sim {\frac {n^{k-1}}{k!(k-1)!}}}$, as ${\displaystyle n\rightarrow \infty }$.
Proof.
 Suppose that ${\displaystyle (x_{1},\ldots ,x_{k})}$ is a ${\displaystyle k}$-partition of ${\displaystyle n}$. Then ${\displaystyle x_{1}+x_{2}+\cdots +x_{k}=n}$ and ${\displaystyle x_{1}\geq x_{2}\geq \cdots \geq x_{k}\geq 1}$. The ${\displaystyle k!}$ permutations of ${\displaystyle (x_{1},\ldots ,x_{k})}$ yield at most ${\displaystyle k!}$ many ${\displaystyle k}$-compositions (the ordered sum of ${\displaystyle k}$ positive integers). There are ${\displaystyle {n-1 \choose k-1}}$ many ${\displaystyle k}$-compositions of ${\displaystyle n}$, every one of which can be yielded in this way by permuting a partition. Thus, ${\displaystyle k!p_{k}(n)\geq {n-1 \choose k-1}}$. Let ${\displaystyle y_{i}=x_{i}+k-i}$. That is, ${\displaystyle y_{k}=x_{k},y_{k-1}=x_{k}+1,y_{k-2}=x_{k}+2,\ldots ,y_{1}=x_{k}+k-1}$. Then, it holds that ${\displaystyle y_{1}>y_{2}>\cdots >y_{k}\geq 1}$; and ${\displaystyle y_{1}+y_{2}+\cdots +y_{k}=n+{\frac {k(k-1)}{2}}}$. Each permutation of ${\displaystyle (y_{1},y_{2},\ldots ,y_{k})}$ yields a distinct ${\displaystyle k}$-composition of ${\displaystyle n+{\frac {k(k-1)}{2}}}$, because all ${\displaystyle y_{i}}$ are distinct. Thus, ${\displaystyle k!p_{k}(n)\leq {n+{\frac {k(k-1)}{2}}-1 \choose k-1}}$. Combining the two inequalities, we have ${\displaystyle {\frac {n-1 \choose k-1}{k!}}\leq p_{k}(n)\leq {\frac {n+{\frac {k(k-1)}{2}}-1 \choose k-1}{k!}}}$. The theorem follows.
${\displaystyle \square }$

### Ferrers diagram

A partition of a number ${\displaystyle n}$ 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 ${\displaystyle (x_{1},x_{2},\ldots ,x_{k})}$ with that ${\displaystyle x_{1}\geq x_{2}\geq \cdots x_{k}\geq 1}$ be a partition of ${\displaystyle n}$. Its Ferrers diagram consists of ${\displaystyle k}$ rows, where the ${\displaystyle i}$-th row contains ${\displaystyle x_{i}}$ 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.

${\displaystyle (6,4,4,2,1)}$ conjugate: ${\displaystyle (5,4,3,3,1,1)}$

Clearly,

• different partitions cannot have the same conjugate, and
• every partition of ${\displaystyle n}$ is the conjugate of some partition of ${\displaystyle n}$,

so the conjugation mapping is a permutation on the set of partitions of ${\displaystyle n}$. 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 ${\displaystyle n}$ which have largest summand ${\displaystyle k}$, is ${\displaystyle p_{k}(n)}$. The number of ${\displaystyle n}$ into ${\displaystyle k}$ parts equals the number of partitions of ${\displaystyle n-k}$ into at most ${\displaystyle k}$ parts. Formally, ${\displaystyle p_{k}(n)=\sum _{j=1}^{k}p_{j}(n-k)}$.
Proof.
 For every ${\displaystyle k}$-partition, the conjugate partition has largest part ${\displaystyle k}$. And vice versa. For a ${\displaystyle k}$-partition of ${\displaystyle n}$, remove the leftmost cell of every row of the Ferrers diagram. Totally ${\displaystyle k}$ cells are removed and the remaining diagram is a partition of ${\displaystyle n-k}$ into at most ${\displaystyle k}$ parts. And for a partition of ${\displaystyle n-k}$ into at most ${\displaystyle k}$ parts, add a cell to each of the ${\displaystyle k}$ rows (including the empty ones). This will give us a ${\displaystyle k}$-partition of ${\displaystyle n}$. It is easy to see the above mappings are 1-1 correspondences. Thus, the number of ${\displaystyle n}$ into ${\displaystyle k}$ parts equals the number of partitions of ${\displaystyle n-k}$ into at most ${\displaystyle k}$ parts.
${\displaystyle \square }$

## Principle of Inclusion-Exclusion

Let ${\displaystyle A}$ and ${\displaystyle B}$ be two finite sets. The cardinality of their union is

${\displaystyle |A\cup B|=|A|+|B|-{\color {Blue}|A\cap B|}}$.

For three sets ${\displaystyle A}$, ${\displaystyle B}$, and ${\displaystyle C}$, the cardinality of the union of these three sets is computed as

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

This is illustrated by the following figure.

Generally, the Principle of Inclusion-Exclusion states the rule for computing the union of ${\displaystyle n}$ finite sets ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$, such that

{\displaystyle {\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|&=\sum _{I\subseteq \{1,\ldots ,n\}}(-1)^{|I|-1}\left|\bigcap _{i\in I}A_{i}\right|.\end{aligned}}}

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

Let ${\displaystyle A_{1},A_{2},\ldots ,A_{n}\subseteq U}$ be subsets of some finite set ${\displaystyle U}$. Here ${\displaystyle U}$ is some universe of combinatorial objects, whose cardinality is easy to calculate (e.g. all strings, tuples, permutations), and each ${\displaystyle A_{i}}$ 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 ${\displaystyle n}$ properties. We write ${\displaystyle {\bar {A_{i}}}=U-A}$. The number of objects without any of the properties ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ is

{\displaystyle {\begin{aligned}\left|{\bar {A_{1}}}\cap {\bar {A_{2}}}\cap \cdots \cap {\bar {A_{n}}}\right|=\left|U-\bigcup _{i=1}^{n}A_{i}\right|&=|U|+\sum _{I\subseteq \{1,\ldots ,n\}}(-1)^{|I|}\left|\bigcap _{i\in I}A_{i}\right|.\end{aligned}}}

For an ${\displaystyle I\subseteq \{1,2,\ldots ,n\}}$, we denote

${\displaystyle A_{I}=\bigcap _{i\in I}A_{i}}$

with the convention that ${\displaystyle A_{\emptyset }=U}$. The above equation is stated as:

 Principle of Inclusion-Exclusion Let ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ be a family of subsets of ${\displaystyle U}$. Then the number of elements of ${\displaystyle U}$ which lie in none of the subsets ${\displaystyle A_{i}}$ is ${\displaystyle \sum _{I\subseteq \{1,\ldots ,n\}}(-1)^{|I|}|A_{I}|}$.

Let ${\displaystyle S_{k}=\sum _{|I|=k}|A_{I}|\,}$. Conventionally, ${\displaystyle S_{0}=|A_{\emptyset }|=|U|}$. The principle of inclusion-exclusion can be expressed as

${\displaystyle S_{0}-S_{1}+S_{2}+\cdots +(-1)^{n}S_{n}.}$

### Surjections

In the twelvefold way, we discuss the counting problems incurred by the mappings ${\displaystyle f:N\rightarrow M}$. The basic case is that elements from both ${\displaystyle N}$ and ${\displaystyle M}$ are distinguishable. In this case, it is easy to count the number of arbitrary mappings (which is ${\displaystyle m^{n}}$) and the number of injective (one-to-one) mappings (which is ${\displaystyle (m)_{n}}$), 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 ${\displaystyle n}$-set to an ${\displaystyle m}$-set is given by ${\displaystyle \sum _{k=1}^{m}(-1)^{m-k}{m \choose k}k^{n}}$.
Proof.
 Let ${\displaystyle U=\{f:[n]\rightarrow [m]\}}$ be the set of mappings from ${\displaystyle [n]}$ to ${\displaystyle [m]}$. Then ${\displaystyle |U|=m^{n}}$. For ${\displaystyle i\in [m]}$, let ${\displaystyle A_{i}}$ be the set of mappings ${\displaystyle f:[n]\rightarrow [m]}$ that none of ${\displaystyle j\in [n]}$ is mapped to ${\displaystyle i}$, i.e. ${\displaystyle A_{i}=\{f:[n]\rightarrow [m]\setminus \{i\}\}}$, thus ${\displaystyle |A_{i}|=(m-1)^{n}}$. More generally, for ${\displaystyle I\subseteq [m]}$, ${\displaystyle A_{I}=\bigcap _{i\in I}A_{i}}$ contains the mappings ${\displaystyle f:[n]\rightarrow [m]\setminus I}$. And ${\displaystyle |A_{I}|=(m-|I|)^{n}\,}$. A mapping ${\displaystyle f:[n]\rightarrow [m]}$ is surjective if ${\displaystyle f}$ lies in none of ${\displaystyle A_{i}}$. By the principle of inclusion-exclusion, the number of surjective ${\displaystyle f:[n]\rightarrow [m]}$ is ${\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}}$. Let ${\displaystyle k=m-j}$. The theorem is proved.
${\displaystyle \square }$

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

• Surjection to ordered partition:
For a surjective ${\displaystyle f:[n]\rightarrow [m]}$, ${\displaystyle (f^{-1}(0),f^{-1}(1),\ldots ,f^{-1}(m-1))}$ is an ordered partition of ${\displaystyle [n]}$.
• Ordered partition to surjection:
For an ordered ${\displaystyle m}$-partition ${\displaystyle (B_{0},B_{1},\ldots ,B_{m-1})}$ of ${\displaystyle [n]}$, we can define a function ${\displaystyle f:[n]\rightarrow [m]}$ by letting ${\displaystyle f(i)=j}$ if and only if ${\displaystyle i\in B_{j}}$. ${\displaystyle f}$ is surjective since as a partition, none of ${\displaystyle B_{i}}$ is empty.

Therefore, we have a one-to-one correspondence between surjective mappings from an ${\displaystyle n}$-set to an ${\displaystyle m}$-set and the ordered ${\displaystyle m}$-partitions of an ${\displaystyle n}$-set.

The Stirling number of the second kind ${\displaystyle S(n,m)}$ is the number of ${\displaystyle m}$-partitions of an ${\displaystyle n}$-set. There are ${\displaystyle m!}$ ways to order an ${\displaystyle m}$-partition, thus the number of surjective mappings ${\displaystyle f:[n]\rightarrow [m]}$ is ${\displaystyle m!S(n,m)}$. Combining with what we have proved for surjections, we give the following result for the Stirling number of the second kind.

 Proposition ${\displaystyle S(n,m)={\frac {1}{m!}}\sum _{k=1}^{m}(-1)^{m-k}{m \choose k}k^{n}}$.

### 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 ${\displaystyle \pi }$ of ${\displaystyle \{1,2,\ldots ,n\}}$, a fixed point is such an ${\displaystyle i\in \{1,2,\ldots ,n\}}$ that ${\displaystyle \pi (i)=i}$. A derangement of ${\displaystyle \{1,2,\ldots ,n\}}$ is a permutation of ${\displaystyle \{1,2,\ldots ,n\}}$ that has no fixed points.

 Theorem The number of derangements of ${\displaystyle \{1,2,\ldots ,n\}}$ given by ${\displaystyle n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}\approx {\frac {n!}{\mathrm {e} }}}$.
Proof.
 Let ${\displaystyle U}$ be the set of all permutations of ${\displaystyle \{1,2,\ldots ,n\}}$. So ${\displaystyle |U|=n!}$. Let ${\displaystyle A_{i}}$ be the set of permutations with fixed point ${\displaystyle i}$; so ${\displaystyle |A_{i}|=(n-1)!}$. More generally, for any ${\displaystyle I\subseteq \{1,2,\ldots ,n\}}$, ${\displaystyle A_{I}=\bigcap _{i\in I}A_{i}}$, and ${\displaystyle |A_{I}|=(n-|I|)!}$, since permutations in ${\displaystyle A_{I}}$ fix every point in ${\displaystyle I}$ and permute the remaining points arbitrarily. A permutation is a derangement if and only if it lies in none of the sets ${\displaystyle A_{i}}$. So the number of derangements is ${\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!}}.}$ By Taylor's series, ${\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)}$. It is not hard to see that ${\displaystyle n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$ is the closest integer to ${\displaystyle {\frac {n!}{\mathrm {e} }}}$.
${\displaystyle \square }$

Therefore, there are about ${\displaystyle {\frac {1}{\mathrm {e} }}}$ 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 ${\displaystyle \pi (i)\neq i}$. 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 ${\displaystyle B\subseteq \{1,\ldots ,n\}\times \{1,\ldots ,n\}}$, called a board. As illustrated below, we can think of ${\displaystyle B}$ as a chess board, with the positions in ${\displaystyle B}$ marked by "${\displaystyle \times }$".

 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 ${\displaystyle \pi }$ of ${\displaystyle \{1,\ldots ,n\}}$, define the graph ${\displaystyle G_{\pi }(V,E)}$ as

{\displaystyle {\begin{aligned}G_{\pi }&=\{(i,\pi (i))\mid i\in \{1,2,\ldots ,n\}\}.\end{aligned}}}

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 ${\displaystyle \pi }$ is a permutation. Thus, we can identify each ${\displaystyle G_{\pi }}$ as a placement of ${\displaystyle n}$ rooks (“城堡”，规则同中国象棋里的“车”) without attacking each other.

For example, the following is the ${\displaystyle G_{\pi }}$ of such ${\displaystyle \pi }$ that ${\displaystyle \pi (i)=i}$.

 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

{\displaystyle {\begin{aligned}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{aligned}}}

Interpreted in chess game,

• ${\displaystyle B}$: a set of marked positions in an ${\displaystyle [n]\times [n]}$ chess board.
• ${\displaystyle N_{0}}$: the number of ways of placing ${\displaystyle n}$ non-attacking rooks on the chess board such that none of these rooks lie in ${\displaystyle B}$.
• ${\displaystyle r_{k}}$: number of ways of placing ${\displaystyle k}$ non-attacking rooks on ${\displaystyle B}$.

Our goal is to count ${\displaystyle N_{0}}$ in terms of ${\displaystyle r_{k}}$. This gives the number of permutations avoid all positions in a ${\displaystyle B}$.

 Theorem ${\displaystyle N_{0}=\sum _{k=0}^{n}(-1)^{k}r_{k}(n-k)!}$.
Proof.
 For each ${\displaystyle i\in [n]}$, let ${\displaystyle A_{i}=\{\pi \mid (i,\pi (i))\in B\}}$ be the set of permutations ${\displaystyle \pi }$ whose ${\displaystyle i}$-th position is in ${\displaystyle B}$. ${\displaystyle N_{0}}$ is the number of permutations avoid all positions in ${\displaystyle B}$. Thus, our goal is to count the number of permutations ${\displaystyle \pi }$ in none of ${\displaystyle A_{i}}$ for ${\displaystyle i\in [n]}$. For each ${\displaystyle I\subseteq [n]}$, let ${\displaystyle A_{I}=\bigcap _{i\in I}A_{i}}$, which is the set of permutations ${\displaystyle \pi }$ such that ${\displaystyle (i,\pi (i))\in B}$ for all ${\displaystyle i\in I}$. Due to the principle of inclusion-exclusion, ${\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}|}$. The next observation is that ${\displaystyle \sum _{I\in {[n] \choose k}}|A_{I}|=r_{k}(n-k)!}$, because we can count both sides by first placing ${\displaystyle k}$ non-attacking rooks on ${\displaystyle B}$ and placing ${\displaystyle n-k}$ additional non-attacking rooks on ${\displaystyle [n]\times [n]}$ in ${\displaystyle (n-k)!}$ ways. Therefore, ${\displaystyle N_{0}=\sum _{k=0}^{n}(-1)^{k}r_{k}(n-k)!}$.
${\displaystyle \square }$

#### Derangement problem

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

Take ${\displaystyle B=\{(1,1),(2,2),\ldots ,(n,n)\}}$ as the chess board. A derangement ${\displaystyle \pi }$ is a placement of ${\displaystyle n}$ non-attacking rooks such that none of them is in ${\displaystyle B}$.

 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 ${\displaystyle k}$ non-attacking rooks on ${\displaystyle B}$ is ${\displaystyle r_{k}={n \choose k}}$. We want to count ${\displaystyle N_{0}}$, which gives the number of ways of placing ${\displaystyle n}$ non-attacking rooks such that none of these rooks lie in ${\displaystyle B}$.

By the above theorem

${\displaystyle N_{0}=\sum _{k=0}^{n}(-1)^{k}r_{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}}.}$

#### Problème des ménages

Suppose that in a banquet, we want to seat ${\displaystyle n}$ 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 ${\displaystyle n}$ ladies find their seats. They may either sit at the odd numbered seats or even numbered seats, in either case, there are ${\displaystyle n!}$ different orders. Thus, there are ${\displaystyle 2(n!)}$ ways to seat the ${\displaystyle n}$ ladies.

After sitting the wives, we label the remaining ${\displaystyle n}$ places clockwise as ${\displaystyle 0,1,\ldots ,n-1}$. And a seating of the ${\displaystyle n}$ husbands is given by a permutation ${\displaystyle \pi }$ of ${\displaystyle [n]}$ defined as follows. Let ${\displaystyle \pi (i)}$ be the seat of the husband of he lady sitting at the ${\displaystyle i}$-th place.

It is easy to see that ${\displaystyle \pi }$ satisfies that ${\displaystyle \pi (i)\neq i}$ and ${\displaystyle \pi (i)\not \equiv i+1{\pmod {n}}}$, and every permutation ${\displaystyle \pi }$ with these properties gives a feasible seating of the ${\displaystyle n}$ husbands. Thus, we only need to count the number of permutations ${\displaystyle \pi }$ such that ${\displaystyle \pi (i)\not \equiv i,i+1{\pmod {n}}}$.

Take ${\displaystyle B=\{(0,0),(1,1),\ldots ,(n-1,n-1),(0,1),(1,2),\ldots ,(n-2,n-1),(n-1,0)\}}$ as the chess board. A permutation ${\displaystyle \pi }$ which defines a way of seating the husbands, is a placement of ${\displaystyle n}$ non-attacking rooks such that none of them is in ${\displaystyle B}$.

 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 ${\displaystyle r_{k}}$, the number of ways of placing ${\displaystyle k}$ non-attacking rooks on ${\displaystyle B}$. For our choice of ${\displaystyle B}$, ${\displaystyle r_{k}}$ is the number of ways of choosing ${\displaystyle k}$ points, no two consecutive, from a collection of ${\displaystyle 2n}$ points arranged in a circle.

We first see how to do this in a line.

 Lemma The number of ways of choosing ${\displaystyle k}$ non-consecutive objects from a collection of ${\displaystyle m}$ objects arranged in a line, is ${\displaystyle {m-k+1 \choose k}}$.
Proof.
 We draw a line of ${\displaystyle m-k}$ black points, and then insert ${\displaystyle k}$ red points into the ${\displaystyle m-k+1}$ spaces between the black points (including the beginning and end). {\displaystyle {\begin{aligned}&\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{aligned}}} This gives us a line of ${\displaystyle m}$ points, and the red points specifies the chosen objects, which are non-consecutive. The mapping is 1-1 correspondence. There are ${\displaystyle {m-k+1 \choose k}}$ ways of placing ${\displaystyle k}$ red points into ${\displaystyle m-k+1}$ spaces.
${\displaystyle \square }$

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 ${\displaystyle k}$ non-consecutive objects from a collection of ${\displaystyle m}$ objects arranged in a circle, is ${\displaystyle {\frac {m}{m-k}}{m-k \choose k}}$.
Proof.
 Let ${\displaystyle f(m,k)}$ be the desired number; and let ${\displaystyle g(m,k)}$ be the number of ways of choosing ${\displaystyle k}$ non-consecutive points from ${\displaystyle m}$ points arranged in a circle, next coloring the ${\displaystyle k}$ points red, and then coloring one of the uncolored point blue. Clearly, ${\displaystyle g(m,k)=(m-k)f(m,k)}$. But we can also compute ${\displaystyle g(m,k)}$ as follows: Choose one of the ${\displaystyle m}$ points and color it blue. This gives us ${\displaystyle m}$ ways. Cut the circle to make a line of ${\displaystyle m-1}$ points by removing the blue point. Choose ${\displaystyle k}$ non-consecutive points from the line of ${\displaystyle m-1}$ points and color them red. This gives ${\displaystyle {m-k \choose k}}$ ways due to the previous lemma. Thus, ${\displaystyle g(m,k)=m{m-k \choose k}}$. Therefore we have the desired number ${\displaystyle f(m,k)={\frac {m}{m-k}}{m-k \choose k}}$.
${\displaystyle \square }$

By the above lemma, we have that ${\displaystyle r_{k}={\frac {2n}{2n-k}}{2n-k \choose k}}$. Then apply the theorem of counting permutations with restricted positions,

${\displaystyle N_{0}=\sum _{k=0}^{n}(-1)^{k}r_{k}(n-k)!=\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(n-k)!.}$

This gives the number of ways of seating the ${\displaystyle n}$ husbands after the ladies are seated. Recall that there are ${\displaystyle 2n!}$ ways of seating the ${\displaystyle n}$ ladies. Thus, the total number of ways of seating ${\displaystyle n}$ couples as required by problème des ménages is

${\displaystyle 2n!\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(n-k)!.}$

### The Euler totient function

Two integers ${\displaystyle m,n}$ are said to be relatively prime if their greatest common diviser ${\displaystyle \mathrm {gcd} (m,n)=1}$. For a positive integer ${\displaystyle n}$, let ${\displaystyle \phi (n)}$ be the number of positive integers from ${\displaystyle \{1,2,\ldots ,n\}}$ that are relative prime to ${\displaystyle n}$. This function, called the Euler ${\displaystyle \phi }$ 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 ${\displaystyle n}$ is divisible by precisely ${\displaystyle r}$ different primes, denoted ${\displaystyle p_{1},\ldots ,p_{r}}$. Then ${\displaystyle \phi (n)=n\prod _{i=1}^{r}\left(1-{\frac {1}{p_{i}}}\right)}$.
Proof.
 Let ${\displaystyle U=\{1,2,\ldots ,n\}}$ be the universe. The number of positive integers from ${\displaystyle U}$ which is divisible by some ${\displaystyle p_{i_{1}},p_{i_{2}},\ldots ,p_{i_{s}}\in \{p_{1},\ldots ,p_{r}\}}$, is ${\displaystyle {\frac {n}{p_{i_{1}}p_{i_{2}}\cdots p_{i_{s}}}}}$. ${\displaystyle \phi (n)}$ is the number of integers from ${\displaystyle U}$ which is not divisible by any ${\displaystyle p_{1},\ldots ,p_{r}}$. By principle of inclusion-exclusion, {\displaystyle {\begin{aligned}\phi (n)&=n+\sum _{k=1}^{r}(-1)^{k}\sum _{1\leq i_{1}
${\displaystyle \square }$

## Reference

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