# bijection between number of partitions of 2n satisfying certain conditions with number of partitions of n

Suppose $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_k)$ is a partition of $2n$ where $n\in\mathbb N$ satisfying the following conditions:

• (1) $\lambda_k=1$.

• (2) $\lambda_i−\lambda_{i+1}\leq 1$ for every $i \leq k−1$.

• (3) In the partition $\lambda$, the number of odd parts in odd places & the number of odd parts in even places are equal.

Here a part $\lambda_i$ is said to be in even place if $i$ is even, whereas $\lambda_i$ is said to be in odd place if $i$ is odd. $\lambda_i$ 's are called parts of $\lambda$ and $\lambda_i$ is called an odd part if it is odd & is called even part if it is even.

Now the question is to give a bijection between number of partitions of $2n$ satisfying the above conditions and number of partitions of $n$.

• Posted earlier on MathOverflow: here. It'll likely help answerers if you explain why you find these answers unsatisfying. – Douglas S. Stones Mar 29 '13 at 12:45
• @DouglasS.Stones actually i could not understand any of the answers given in mathoverflow. – Rekha Biswal Mar 29 '13 at 12:52
• I don't have an answer here, but I can sympathise with the question. The answer on MO by Matt Fayers might be helpful if it were explained what conormal $j$-nodes are, probably well known to those who study $p$-regular paritions, but not to me. From a quick Google search I found www.iazd.uni-hannover.de/~bessen/tensalt.ps from which I cite (almost): "an addable node $B$ is called conormal is every node $A$ below $B$ with the same residu there exists an addable node $C(A)$ strictly between $B$ and $A$ with the same residu and such that $A\neq A'$ implies $C(A)\neq C(A')$". – Marc van Leeuwen Mar 30 '13 at 18:40
• @MarcvanLeeuwen could you please explain the last sentence of the answer given by Mat Flayer since substracting n-i from length of the ith column & dividing the length of of the ith column by 2 would not give a prtition of n.? – Rekha Biswal Apr 2 '13 at 12:39
• @RekhaBiswal: I do understand that part. The idea is to gradually "blow up" the $2$-core to a large enough staircase shape $c_i$; the remaining squares will be so that they can be tiled by dominoes. If you add $n$ dominoes to the $2$-core $c_{n-1}$ they must be separated into horizontal ones at the top right, and vertical ones at the bottom left. But with the $2$-restricted condition (no equal columns) the "horizontal" part must be empty. It remains to align the vertical dominoes along their top (subtract $n-i$ from column lengths) and replace the dominoes by squares (divide by $2$). – Marc van Leeuwen Apr 2 '13 at 12:56

I've finally found the proper interpretation of "conormal nodes", which is not the one I cited in the comment (even the corrected with "every node $A$" replaced by "every removable node $A$").

I gave a description of an algorithm in terms of Young diagrams that computes the correspondence in an answer to the corresponding MathOverflow question. What I would like to add here is a more direct description without using diagrams, which may be easier for pencil-and-paper (or computer) computations. For that purpose I will transpose (conjugate) the partitions, as this leads to an easier description.

Call a partition strict if all its nonzero parts are distinct, and black-white balanced if its Young diagram covers equally many black and white squares of a checkerboard pattern, which amounts to the equation $$\sum_i(-1)^i(1-(-1)^{\lambda_i})=0,$$ or to the condition (3) of the question (but the black-white formulation makes the transposition-invariance of the condition more evident).

Central in the description will be the notion of a cyclic parenthesis matching of a word according to attributes attached to its symbols partitioning them into "opening symbols", "closing symbols" and possibly "neutral symbols" (we apply this where symbols are integers, and the attributes are assigned according to parity). This is the usual pairing of matching parentheses, but where one imagines the word repeated periodically, so that an opening symbol at the end may match a closing symbol at the beginning. What will mostly be of interest are the opening (or closing) symbols that remain unmatched in this pairing; if there are $d\geq0$ more opening than closing symbols, there will always be that many unmatched opening symbols (and no unmatched closing symbols). For instance in the word $\def\red{\color{red}}BABB\red AABAABB\red AABAA$ the red letters are the unmatched ones if $A$ is considered opening symbol and $B$ a closing symbol (the two final $A$s respectively match the third and first $B$ due to cyclic repetition).

Proposition. The algorithm below establishes for every $n\in\Bbb N$ a bijection between the black-white balanced strict partitions of $2n$ and the partitions of $n$.

Algorithm. The algorithm operates on finite weakly decreasing sequences of natural numbers $(a_1,a_2,\ldots,a_l)$ that always end with $a_l=0$; there can however be more than one occurrence of $0$, and (unlike in partitions) the number of such occurrences is relevant. The algorithm also maintains a even/odd state, which is always (except maybe at the very beginning) the parity of the majority of the numbers $a_1,\ldots,a_l$ and therefore strictly speaking redundant, but its evolution is explicitly indicated anyway. Given a black-white balanced strict partition $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_k)$ of $2n$ (with $\lambda_k>0$), one starts by setting $l=k+1$ and $a_i=\lambda_i-(l-i)$ for $0<i<l$, and of course $a_l=0$. The initial parity is that of $k$. If $k$ is even then condition (3) ensures that $(a_1,a_2,\ldots,a_k)$ has equally many even and odd terms, and $a_l=0$ gives the majority to the even terms; if $k$ is odd then $l$ is even and $(a_1,a_2,\ldots,a_l)$ has equally many even and odd terms (but the final $0$ will be considered neutral in the first step, giving the effective majority to the odd terms).

• In an even state, all even numbers are considered as opening symbols and all odd numbers as closing symbols; then
• if the final zero is matched, $1$ is added to all unmatched (even) symbols, and the new state is odd;
• if the final zero is unmatched, $1$ is subtracted from all matched symbols, an additional $0$ is added, and the new state remains even.
• In an odd state, all odd numbers are considered as opening symbols, the even numbers except the final $0$ are considered closing symbols, but the final $0$ is considered neutral; then $1$ is added to all unmatched (odd) symbols, and the new state is even.

The algorithm terminates when at some point all numbers have become even; at this point the sequence would not change anymore. The partition returned is obtained by dividing all parts by $2$.

Here is an example for the black-white balanced strict partition $(11,10,6,5,2)$ of $2n$ for $n=17$ the states are (with matching symbols indicated by parentheses, neutral ones by a dash, and unmatched ones by a vertical bar):

6 6 3 3 1 0 odd
) ) | ( ( -
6 6 4 3 1 0 even
| ( ( ) ) |
6 5 3 2 0 0 0 even
( ) ) | | | (
6 5 3 3 1 1 0 odd
) | | | | ( -
6 6 4 4 2 1 0 even
| | | | ( ) |
6 6 4 4 1 0 0 0 even
| | | ( ) | | |
6 6 4 3 0 0 0 0 0 even
| | ( ) | | | | |
6 6 3 2 0 0 0 0 0 0 even
| ( ) | | | | | | |
6 5 2 2 0 0 0 0 0 0 0 even
( ) | | | | | | | | |
5 4 2 2 0 0 0 0 0 0 0 0 even
) | | | | | | | | | | (
5 5 3 3 1 1 1 1 1 1 1 0 odd
| | | | | | | | | | | -
6 6 4 4 2 2 2 2 2 2 2 0 terminal


The partition of $n$ obtained here is $(3,3,2,2,1,1,1,1,1,1,1)$.

• The bijection looks scary... Why do you know that "If $k$ is even then condition (3) ensures that $(a_1,a_2,\ldots,a_k)$ has equally many even and odd terms"? Doesn't condition (3) just make a statement about the odd $\lambda_i$ ? – darij grinberg Apr 15 '13 at 1:40
• Meanwhile, my real takeaway from this post is the simple fact that a circular word over a two-letter alphabet can be endowed with matching parentheses uniquely. I assume you prove this using a recursive algorithm which matches each adjacent OC-pair (i. e., each pair consisting of an opening symbol and a closing symbol such that the position of the closing symbol is congruent to the position of the opening symbol plus 1 modulo the length of the word), then removes all the matched symbols and recursively applies itself to the reduced word, etc., until it no longer finds matched symbols. ... – darij grinberg Apr 15 '13 at 1:45
• ... At that point, the removed symbols are reinstated in the order in which they appeared initially in the word. Do you prove the confluence of this algorithm using the diamond lemma, or is there a simpler argument? Also, this makes me wonder what can be said about the operators $e_i$, $f_i$, $h_i$ defined similarly to the standard coplactic operators but for circular words instead of usual words. Do they still form crystal graphs? – darij grinberg Apr 15 '13 at 1:48
• @darijgrinberg To try to understand the bijection, please look at the linked MO answer, whose description is mimics, where $(a_1,\ldots,a_l=0)$ represents a diagram with column lengths $a_1+l, a_2+l-1,\ldots ,a_{l-1}-1$. As for the scariness, condition (3) ensures that the odd $\lambda_i$ contribute equally many even as odd terms $a_i$, but also that they occupy equally many even as odd positions. Then (as $k$ is even) there remain equally many even as odd positions for the even $\lambda_i$, and those as well contribute equally many even as odd terms $a_i$. – Marc van Leeuwen Apr 15 '13 at 4:16
• And for the cyclic matching, I think the easiest way to define it formally is to consider the cyclically repeated word from a given starting position, and define a cumulated sequence of integers that at any position counts the difference between the numbers of opening and closing symbols so far. This sequence quasi-repeats, with a shift for each iteration (extend also for negative positions). Supposing the shift positive, the unmatched positions are those where the cumulation reaches a new maximum-so-far; each other up-step matches the next down-step to attain the same level. – Marc van Leeuwen Apr 15 '13 at 4:24