DEFINITION. An involution on a set $X$ is a function $f:X\to X$ such that $f(f(x)), \, \forall x \in X$. An involution is easily shown to be a bijection, and an involution on a set $X$ may alternatively be thought as bijection $f:X\to X$ such that $f$ (as a function) is its own inverse.

Several combinatorial proofs of basic hypergeometric identities depend on various involutions on the set of partitions of an arbitrary integer $n$.

One simple example of an involution on the set of partitions of an integer $n$ is the operation of conjugation, since the conjugate of the conjugate of a partition is the original partition.

Another example of an involution is on the set of Wilf partitions of a positive integer $n$, where a Wilf partition is a partition in which all nonzero multiplicities are distinct. The Wilf involution on the set of such partitions is the operation that interchanges part sizes and multiplicities. For example, under this involution, the partition \begin{multline*} 6+5+5+5+4+4+2+2+2+2+2+1+1+1+1\\ = \underbrace{6}_{1}+\underbrace{5+5+5}_{3}+\underbrace{4+4}_2+\underbrace{2+2+2+2+2}_5+\underbrace{1+1+1+1}_4 \end{multline*} becomes the partition \begin{multline*} \underbrace{1+1+1+1+1+1}_6+\underbrace{3+3+3+3+3}_5+\underbrace{2+2+2+2}_4+\underbrace{5+5}_2+\underbrace{4}_1\\ =5+5+4+3+3+3+3+3+2+2+2+2+1+1+1+1+1+1. \end{multline*}

One of the earliest use of an involution to prove a basic hypergeometric identity was Franklin's involution, defined on the set of partitions of an integer $n$ into distinct parts.
Let $\mathcal{D}_n$ denote the set of partitions of $n$ into distinct parts. For a given partition $\lambda \in \mathcal{D}_n$, let $s=s(\lambda)$ denote the smallest part of $\lambda$, and let $d=d(\lambda)$ denote the size of the largest decreasing sequence of consecutive parts, starting with the largest part (for ease of notation, the diagonal row of dots at the end of these rows in the corresponding Ferrers graph will be referred to as the ``diagonal row''). Franklin's involution is a map $\phi: \mathcal{D}_n\to \mathcal{D}_n$ that acts on a partition $\lambda \in \mathcal{D}_n$ by moving some of the dots in the corresponding Ferrers graph around in a certain prescribed manner.

We first consider the case where bottom row of the Ferrers graph and the diagonal row do not intersect.
If $s\leq d$, $\phi(\lambda)$ is the partition formed by removing the $s$ dots at the bottom of the Ferrers graph and placing one dot at the end of each of the rows corresponding to the $s$ largest parts.

If $s> d$ in the Ferrers graph of $\lambda$, $\phi(\lambda)$ is the partition formed by removing a dot from the right end each of the rows corresponding to the $d$ largest parts of $\lambda$, and placing them at the bottom of the Ferrers graph to create a new smallest part.

When the bottom row and the diagonal row of the Ferrers graph of the partition $\lambda$ do intersect, we consider a number of cases. If $s< d$ or $s > d+1$, then the rule is the same as in the case that bottom row and the diagonal row of the Ferrers graph of the partition $\lambda$ do not intersect.
If $s=d$ or $s=d+1$, then define $\phi(\lambda):= \lambda$. This latter situation occurs if $n=k^2+k(k-1)/2= k(3k-1)/2$ or $n=k^2+k(k+1)/2 =k(3k+1)/2$, where $k$ $(=d)$ is the number of rows in the Ferrers graph (see Figure 3.).

Thus $\phi(\phi(\lambda))=\lambda,\,\forall \, \lambda \in \mathcal{D}_n$, and if $n \not = k(3k\pm 1)/2$, then $n$ has as many partitions into an odd number of distinct parts as it has partitions into an even number of distinct parts, and if $n = k(3k\pm 1)/2$, then $n$ has one additional unmatched partition into $k$ distinct parts. Thus, if $\mathcal{D}_n^o$ denotes the set of partitions of $n$ into an odd number of distinct parts, and $\mathcal{D}_n^e$ denotes the set of partitions of $n$ into an even number of distinct parts, then \begin{equation}\label{doeneq} |\mathcal{D}_n^e|-|\mathcal{D}_n^o| = \begin{cases} (-1)^k, &n=k(3k\pm 1)/2,\\ 0& \text{ otherwise.} \end{cases} \end{equation} This conclusion leads to Franklin's combinatorial proof of the pentagonal number theorem.

Theorem. If $|q| < 1$, then \begin{equation}\label{partepnteq} (q;q)_{\infty}=\sum_{n=-\infty}^{\infty} (-1)^nq^{n(3n-1)/2}= 1+\sum_{n=1}^{\infty} (-1)^n(q^{n(3n-1)/2}+q^{n(3n+1)/2}). \end{equation} This follows from the remarks above and the fact that \begin{equation}\label{partepnteq2} (q;q)_{\infty}= 1+\sum_{n=1}^{\infty} (|\mathcal{D}_n^e|-|\mathcal{D}_n^o|)q^n. \end{equation} Several other examples of proofs that use partition involutions may be found in the paper [1] of Pak.

[1] Pak, I., The nature of partition bijections. I. Involutions. Adv. in Appl. Math. 33 (2004), no. 2, 263–289.

Back to the main Partitions page