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

Suppose $\lambda = (\lambda_1,\lambda_2,.....,\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$.

-
How do you know (or what makes you expect) this is true? –  Gerry Myerson Mar 27 '13 at 11:39
BY weyl character formula it is proved that multiplicity of the weight $\wedge_{0})- n.\delta$ in the basic representation of $\hat{sl_2}$ is eual to the number pf partitions of n.In paper of Kreiman,Lakshmibai,Magyar & Weyman on standard basis of affine sl_n modules ,they have given a parametrization for the basis of $L(\wedge_{0})$ in terms of semi infinite wedge wedge product.from that parametrization it has been found that the multiplicity of weight $\wedge_{0}-n.\delta$ is exactly equal to the number of partitions $\lambda$ of 2n satisfying the above conditions mentioned in the question. –  Rekha Biswal Mar 27 '13 at 12:29
@Rekha, whenever possible, please provide a link: math.msu.edu/~magyar/papers/AffineSMT-1.pdf -- it saves other people time. –  Barry Cipra Mar 27 '13 at 16:45
@Barry oh Thanks .since you have already provided the link .I will take care of it from next time. –  Rekha Biswal Mar 27 '13 at 17:52

For $j\geqslant0$ let $c_j$ denote the $2$-core partition $(j,j-1,\dots,1)$.

Your conditions on partitions of $2n$ can be re-phrased as asking for $2$-restricted partitions of $2$-weight $n$ and $2$-core $c_0$. Now for any $j$, there is a standard way to biject between $2$-restricted partitions of weight $n$ with $2$-core $c_j$ and $2$-restricted partitions with $2$-core $c_{j+1}$; using the Misra-Miwa model of the crystal of the basic representation of $U_q(\widehat{\mathfrak{sl}}_2)$, this is just reflection of the $j$-strings in that crystal. In terms of partition combinatorics, it's given by adding the $j$ lowest conormal $j$-nodes (though Misra and Miwa don't use this terminology).

Composing these bijections, you can biject to the set of $2$-restricted partitions with $2$-core $c_{n-1}$. Then you can biject from these to partitions of $n$ just by subtracting $n-i$ from the length of the $i$th column, and then dividing the length of the $i$th column by $2$, for $i=1,\dots,n-1$.

See

K. Misra & T. Miwa, 'Crystal base for the basic representation of $U_q(\widehat{\mathfrak{sl}}(n))$', Commun. Math. Phys. 134.

Addendum 1st June 2013: Following Marc van Leeuwen's comment, here's a definition of conormal $j$-nodes, for $j\in\lbrace0,1\rbrace$: a $j$-node is a node $(r,c)$ such that $r+c\equiv j\mod 2$. An addable $j$-node $\mathfrak n$ of a partition is conormal if the number of addable $j$-nodes minus the number of removable $j$-nodes above $\mathfrak n$ is strcitly greater than for any higher addable $j$-node.

-
@Fayers how is c_0 defined here? –  Rekha Biswal Mar 28 '13 at 16:07
@Rekha Biswal: c0 is just the empty partition, or diagram. –  Marc van Leeuwen Mar 30 '13 at 9:23
It would be helpful to have a description of conormal $j$ nodes. Am I correct in assuming that $j$ is to be interpreted modulo $2$ here? Also, with a definition of conormal nodes I found here www.iazd.uni-hannover.de/~bessen/tensalt.ps (where removable nodes below it have to be paired with intermediate addable nodes), it would seem that adding the lowest such nodes would not result in an invertible operation (having become removable, they could pair up with another addable node above). Are you sure you did not mean adding the highest conormal $j$ nodes? –  Marc van Leeuwen Apr 3 '13 at 10:17
@Marc: I meant lowest. There are two competing conventions, in which the same terminology is used. The reference you cite considers $p$-regular partitions rather than $p$-restricted partitions, so everything has to be transposed from there, and in particular, highest becomes lowest. For example, for the partition $(2,1,1)$, both the addable $0$-nodes $(1,3)$ and $(2,2)$ are conormal, and we add the lower one to get the partition $(2,2,1)$; if we instead added the higher conormal node, we'd obtain $(3,1,1)$, which is not $2$-restricted. –  Matt Fayers Jun 1 '13 at 14:52

This is the bijection indicated in the answer by Matt Fayers, described more explicitly. Note that I needed to correct the wrong definition of "conormal nodes" that I had found in the document mentioned in my comment to that answer.

Represent partitions by their Young diagram, laid out on a checkerboard pattern that makes the top-left square a black one. Condition (3) means that the diagram covers equally many black and white squares, while conditions (1) and (2) mean that all nonzero column lengths are different.

The procedure below will successively add $1$ black square, then $2$ white squares, then $3$ black squares, and so on with alternating colours and increasing numbers, until at some point a step adds squares to every nonempty column. At that point, if there are now $k$ nonempty columns (and the last step added $k$ squares), remove $k,k-1,\ldots,2,1$ squares respectively from the successive columns (which compensates for all the the squares that had been added); this makes the column lengths (no longer necessarily distinct but) all even (this follows from the colour of the last square added to each column), and dividing them all by $2$ gives the desired partition (or its conjugate). The crux of the definition of the procedure is of course to specify exactly which $i$ squares to add in step $i$; this is done as follows.

From the theory of $2$-quotients, it follows that for any Young diagram, if $d$ is the number of black squares it contains minus the number of white squares, then the number of places (cocorners) where a white square can be added minus the number of places (corners) where a white square can be removed equals $2d$, and then the number of places where a black square can be added minus the number of places where a black square can be removed equals $1-2d$. An elementary proof would be to check it for $2$-cores (staircase diagrams), and check that the mentioned differences do not change when adding a domino to the diagram. In the above description, where the number $d$ takes successive values $0,1,-1,2,-2,\ldots$, one sees that at the point where one must add $i$ squares of some colour, the number of addable squares of that colour exceeds the number of removable squares of that colour by $i$ (so in particular one cannot have a shortage of candidate squares). Now pair up each such removable square with an addable square which it "cancels", as follows. Order all these addable and removable squares of the correct colour cyclically, from the top-right to the bottom left along the border of the diagram, and then "warp around" back to the start. If a removable square pair is immediately followed in this order by an addable square then the two pair up; continue pairing up with the same rule, but ignoring already paired-up squares for the "immediately followed" condition. All removable squares are eventually paired up, and $i$ addable squares remain unpaired. It is these $i$ squares that will be effectively added in this step.

(One can avoid talking about a "wrap around" cyclic order, in which case some number $l$ of removable squares may be left unpaired; then one only adds the $i$ lowest unpaired addable squares and $l$ addable squares before them are not added, although they remained unpaired. However I find it more intuitive to say that every removable square knocks out precisely one addable square, and without cycling there are precisely $l$ unmatched removable squares, which are all below all unmatched addable squares.)

The proof that each step is reversible is easy. Each square that was added has become removable; therefore the pairing for the reverse direction proceeds by having each addable square pair up with a removable square immediately preceding it in the cyclic order (again ignoring previously paired-up squares), and it is the unpaired removable squares that in the end are effectively removed.

Of course one must also show that the construction in both directions preserves the "distinct nonzero column lengths" condition; this is also easy. In the forward direction, one could only make two column lengths equal if both columns had addable squares of the correct colour, but only the rightmost one of them was actually added. But that means the leftmost one must have been paired up with a removable square; but such pairs are never in the same column, and the presence of the rightmost addable square makes such a pairing impossible. The argument in the oppsite direction is quite similar.

-

Bijection to OEIS A064174 "Number of partitions of n with nonnegative rank".

-
@Wouter what is the meaning of bijection to OEIS A064174 here? –  Rekha Biswal Mar 29 '13 at 12:56
@Rekha Biswal: adding the constraint of having an even number of parts produces A064174. –  Wouter Apr 3 '13 at 9:34
Can you explain the relation with that sequence? OP wants a bijection with all partition of $n$. –  Marc van Leeuwen Apr 3 '13 at 10:09