Bijections on the set of integer partitions of $n$

Question

I am looking for natural bijections from the set of integer partitions of $n$ to itself. Of course, I have no definition of natural, but for the purpose of this question it suffices that it appears in the literature.

I currently know of three families of bijections:

• The Franklin-Glaisher bijections, that map the set of parts divisible by $s$ to the set of parts which occur at least $s$ times, see https://www.findstat.org/MapsDatabase/Mp00312 for the $s=2$ case.

• A family of involutions depending on a positive rational number $r/s$ due to Loehr, Nicholas A.; Warrington, Gregory S., A continuous family of partition statistics equidistributed with length, J. Comb. Theory, Ser. A 116, No. 2, 379-403 (2009). ZBL1188.05012. These involutions can be combined to obtain, for example, a bijection sending the length to the diagonal inversion number of a partition, see https://www.findstat.org/MapsDatabase/Mp00322.

• $s$-conjugation, which maps the number of parts divisible by $s$ to the number of cells in the Ferrers diagram which have leg length $0$ and arm length equal to $s-1$ mod $s$, see https://www.findstat.org/MapsDatabase/Mp00321 for the $s=2$ case. Note that for $s=1$ this is simply conjugation. The general case is current work joint with other members of the Arbeitsgemeinschaft Diskrete Mathematik at the University of Vienna.

Do you know of any other natural bijections on the set of all integer partitions of $n$?

Answer 1

I'm converting my comments to an answer.

Let $\mathrm{Par} = \{\lambda\colon \lambda \vdash n, n \geq 0\}$ denote the set of all integer partitions. You are looking for "natural" bijections $\varphi\colon \mathrm{Par}\to \mathrm{Par}$. Indeed, these seem somewhat rare.

More commonly, we have a certain subset $X \subseteq \mathrm{Par}$ and a bijection $\varphi\colon X \to X$.* I will discuss a couple such examples below. Note that we can always extend such a $\varphi$ to all of $\mathrm{Par}$ by having it act trivially on the partitions not in $X$, but this feels somewhat "unnatural."

Onto the examples with restricted classes of partitions.

Let $p$ be a prime. Taking $X$ to be the set of $p$-regular partitions (those with no part appearing $p$ times or more), there is an involution called the "Mullineux involution" which can be defined purely combinatorially, but which also represents the effect of tensoring with the sign representation an irreducible representation of the symmetric group $S_n$ over $\mathbb{F}_p$. See https://doi.org/10.1112/jlms/s2-20.1.60 for the original definition of this involution.

Let $n \geq 1$, and let $X=Y_n$ be the set of partitions whose hull (smallest containing rectangle) is contained in the staircase partition $(n-1,n-2,\ldots,1)$. Note that $\#Y_n = 2^{n-1}$. Suter defined an action of the dihedral group $D_n$ on $Y_n$ in https://doi.org/10.1006/eujc.2001.0541. One generator of this action is just conjugation, but the other is an interesting order $n$ bijection. In fact, this dihedral group action respects the restriction of the Hasse diagram of Young's lattice to $Y_n$.

An even more basic example is if we let $a,b \geq 1$ and let $X$ be the set of partitions contained in the $a\times b$ rectangle. Then we can consider the involution on $X$ which is the complement inside this $a\times b$ rectangle. This involution is highly significant in symmetric function theory, Schubert calculus, et cetera.

*Perhaps even more commonly, we have two subsets $X,Y\subseteq \mathrm{Par}$ and a bijection $\varphi\colon X \to Y$. But already the case when the domain and codomain of the bijection are the same has plenty of examples, as we saw.

Answer 2

Carla Savage (Journal of Algorithms 10 (1989) 577-595) established that, for each $n$, there is a Gray code on $P(n)$ where adjacent partitions are connected if one part increases by 1 and another part decreases by 1 (including to or from 0). Here are some examples.

$$ 11111, 2111, 311, 221, 32, 41, 5 $$

$$ 111111, 21111, 3111, 2211, 222, 321, 33, 42, 411, 51, 6 $$

$$ 1111111, 211111, 31111, 22111, 2221, 322, 3211, 331, 43, 421, 4111, 511, 52, 61, 7$$

The path always begins at $1^n$ and ends at $n$. Each of these can be made into a bijection by connecting those two partitions to make a cycle. The procedure for determining the list is a bit complicated, but it's certainly in the literature.

Answer 3

Let $P_{DO}(n)$ be the partitions of $n$ consisting of distinct odd parts. On Mathematics StackExchange, Marc van Leeuwen gave a bijection on $P(n) \setminus P_{DO}(n)$ establishing that the count of partitions in the set with even length equals the count of partitions in the set with odd length. It can be extended to a bijection on $P(n)$ by fixing partitions in $P_{DO}(n)$.

His map uses a more subtle merge-split operation than Glaisher's; see the MSE post for details. Here's the correspondence on $P(5)$ (with the addition that $(5)$ is fixed).

$$ 5, \quad 41 \longleftrightarrow 221, \quad 32 \longleftrightarrow 311, \quad 2111 \longleftrightarrow 11111.$$

As to whether this is "natural": A collaborator and I are using this in a project, so hopefully it will be in the literature soon. Van Leeuwen told me in email that he has not published it and is not aware of it being in the literature; in the MSE post, he modestly calls it "exercise grade."

Answer 4

Here is a different class of examples. These are bijections genuinely on the set of all partitions, but it is up to you to decide if they are "natural."

Let $\lambda$ be a partition. If its first part is $\lambda_1=b+1$ and its length is $\ell(\lambda)=a+1$, then notice the part of the Young diagram which is not in the first row or column fits inside an $a\times b$ rectangle. So the idea is we can apply any bijection on the partitions that fit inside an $a\times b$ rectangle, and this gives a bijection on all partitions. We just fix the first row/column of our Young diagram, and apply the desired bijection to the part "inside." There are many bijections on the partitions that fit inside an $a\times b$ rectangle: for example, conjugation; but also, as I mentioned in my other answer, complement; and there are bijections that are not involutions too (think rowmotion/promotion).

If you know about the Maya diagram representation of a partition, this class of examples can also be described as: we fix the first 1 and last 0 of the Maya diagram of our partition, and apply some bijection on binary strings with a given number of 0's and 1's to the part between that first 1 and last 0. Natural such bijections on binary strings are reversal (= complement), rotation (= promotion), etc.