% SylvesterBij            22 juin 2000  corrections 2mars01
% PLAIN TEX 
\magnification=1200  
\frenchspacing

\def\s{\scriptstyle }
\def\ff{ f^{\l,n}}
\def\WW{{\cal W}(\l,n)}

\def\ss{\sigma}
\def\a{\alpha}
\def\b{\beta}
\def\c{\gamma}
\def\g{\gamma}
\def\l{\lambda}
\def\L{\Lambda}
\def\e{\epsilon}
\def\d{\partial}

\def\mm{\varphi}
\font\goth=eufm10
\font\sgoth=eufm10 at 7pt
\font\bb=msbm10

\def\N{\hbox{\bb N}}
\def\Z{\hbox{\bb Z}}
\def\C{\hbox{\bb C}}
\def\K{\hbox{\bb K}}
\def\Y{\hbox{\bb Y}}
\def\sS{\hbox{\sgoth S}}
\def\S{\hbox{\goth S}}
\def\Sym{\hbox{\goth Sym}}
\def\NilP{\hbox{\goth NilP}}

\def\PP{{\cal P}}
\def\QQ{{\cal Q}}
\def\Qt{\widetilde{\cal Q}}
\def\Ft{{\widetilde{\cal F}_{n,\l}}}
\def\bu{$\bullet$\quad}
\def\bK{\overline{\! K}}

\def\qed{\quad\raise -2pt\hbox{\vrule
\vbox to 10pt{\hrule width 4pt \vfill\hrule}\vrule}}
\def\carrel#1#2#3{{\vcenter{\hrule height .#2pt
                       \hbox{\vrule height #1pt width .#2pt \kern #3pt
                             \vrule width .#2pt}
                       \hrule height .#2pt}}}
\def\carre{\mathchoice\carrel54{5.4}\carrel54{5.4}
                      \carrel33{3.3}\carrel23{2.3}}

\catcode`\@=11
\def\s{\scriptstyle }
\def\petitematrice#1{\null\vcenter {\normalbaselines \m@th
\ialign {\hfil $\s ##$\hfil &&\thinspace  \hfil $\s ##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } \s #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}}


\def\m@th{\mathsurround=\z@}

\def\moyennematrice#1{\null\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$\hfil &&\   \hfil $##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}}

\catcode`\@=12
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\bf Sylvester's bijection between strict and odd partitions}

\medskip
\centerline{Alain Lascoux}

\bigskip

Sylvester [Syl] produced a bijection between strict partitions $\l$ 
and odd ones $\nu$, preserving the weight and exchanging the number
of \lq\lq strings" of $\l$ with  the number of different parts of
$\nu$ (see below for definitions).

Major Mac Mahon [Ma1, vol.2,p.14] 
prudently stated that the proof of Sylvester's statement
was to long for him to write it. A modern proof was provided by
Kim and Yee [KY] who described a simple diagram from which one easily
recovers $\l$ and $\nu$ : their construction is a true two-sided bijection,
but it requires some proof of validity (though a short one).
Previously, Bessenrodt [Bes] had used  2-modular Young diagrams to 
prove and extend Sylvester's bijection.

We argue that there is no need of a proof,  
the canonical bijection 
between strict and odd partitions resulting from reading the same parameters
from $\l$ and $\nu$.  As a by-product, one obtains a statistics on odd
partitions which generalizes the restriction of an identity of Bousquet-Melou 
and Eriksson to strict partitions (cf [BE]). 

\medskip
A {\it strict partition} $\l=[\l_1,\l_2,\ldots, \l_{\ell},0]$, 
$\l_{\ell}\neq 0$,
is a decreasing partition with distinct parts, with a 0 added, 
$\ell$ being the {\it length} of $\l$.

Write boxes between parts of $\l$, alternatively up and down, beginning
with a down box between $(\l_2,\l_3)$: 

$$\l \ \longrightarrow \
\matrix{ &&&& \carre &&&& \carre   \cr
\l_1 & \l_2 && \l_3 && \l_4 &&\l_5 &&\l_6 &&\cdots \cr 
&& \carre &&&& \carre &&&&\carre 
}$$


Fill the top boxes with repeated letters, $1^{\l_3-\l_4}$, 
$2^{\l_5-\l_6}$, $3^{\l_7-\l_8}$, $\ldots$ respectively.
Fill the bottom boxes, from right to left, with strings of consecutive
integers of respective lengths $ \ldots, \l_4-\l_5, \l_2-\l_3$, each string
beginning at the last value in the preceding one, the first string beginning
with $\lfloor \ell/2\rfloor$.  The contents of the boxes may be considered as 
materializing a ribbon made of two parts, the top one being described by its
vertical steps, the bottom one, by its horizontal steps,
each number being the horizontal coordinate of
the box of the ribbon which contains it. For $\l=[11,10,7,5,4,1,0]$, one
has~:

$$
\matrix{ &&&& {\s 11} &&&& {\s 222}   \cr
11 & 10 && 7 && 5 &&4 &&1 &&0 \cr 
&& {\s 345} &&&& {\s 3} &&&& {\s 3  }
} \ \mapsto \ 
\moyennematrice{1\cr 1&2\cr \cdot &2\cr \cdot &2&3\cr
\cdot &\cdot &3\cr \cdot &\cdot &3 &4&5   } 
\mapsto\  \moyennematrice{\carre\cr\carre&\carre\cr
\carre &\carre\cr \carre &\carre&\carre\cr
\carre &\carre &\carre\cr \carre &\carre &\carre &\carre&\carre   }
=\mu $$

The ribbon itself is the border of a partition $\mu$.  Doubling $\mu$ (i.e.
doubling each part), adding to it a first column of length 
$k(\l):= \l_1- \l_2+\l_3-\l_4-\cdots $, one gets a partition $\nu$
with odd parts.

Now, the parameters $k,\l_2-\l_3,\l_3-\l_4,\ldots$ code bijectively $\l$ as
well as $\mu$. Given them, one gets a pair : $\l$ is strict and $\nu$ is odd.
The only point to check is that $k(\l)$ is at least equal to the height of the
ribbon. 


The numbers in the upper corners of the ribbon tell 
 which are the different parts of $\nu$
(apart from the part 1). By construction, they  correspond to the 
indices $i>1$ such that $\l_i-\l_{i+1}>1$, that is to the decomposition 
of $[\l_2,\l_3,\ldots]$ into maximal {\it strings} of 
consectutive integers. Moreover, $\l_1-\l_2=1$ is exactly the case when 
$\ell(\mu)=\ell(\nu)$, i.e. when $\nu$ does not have 1 as a part.

\smallskip
The above ribbon, for $\l=[11,10,7,5,4,1]$,
 gives 
$$\mu=[5,3,3,2,2,1] \ ,\ \nu=[10,6,6,4,4,2]+1^6= [11,7,7,5,5,3] \ .$$

\medskip 
From this construction, one can easily deduce a little more than 
Sylvester's statement.

To each odd partition $\nu \leftrightarrow (k,\mu)$ attach the monomial
$y^{\ell(\mu)} q^{|\nu|} x_1^{\e_1}  x_2^{\e_2} x_3^{\e_3}\cdots$
with $\e_i=1$ or 0 whether $2i+1$ is a part of $\mu$ or not 
($\leftrightarrow i$  is a part of $\nu$ or not).

The generating function of odd partitions with such statistics is
$$  {1\over 1-yq} \prod_1^\infty \left(1+x_i {yq^{2i+1}\over 1-yq^{2i+1}}
    \right) $$
and the above bijection shows that it is equal to 
$$\sum q^{|\l|} y^{k(\l)} x_1^{\e_1}  x_2^{\e_2}\cdots \ ,$$
sum on all strict partitions $\l$, the $\e_i$'s being 0 or 1
whether $\l_j-\l_{j+1}=1$ or not, the correspondence between $j$ and $i$
being given by the bijection.

In particular, for $x_1=x_2=\cdots=x$, one recovers the statistics
which can be deduced from Sylvester's  theorem~:
$$ \sum_\l q^{|\l|} y^{k(\l)} x^{str} = 
   {1\over 1-yq} \prod_1^\infty \left(1+x {yq^{2i+1}\over 1-yq^{2i+1}} 
    \right) \ ,  \eqno(\star) $$
with $str=$ number of maximal strings 
of consecutive integers in $[\l_2,\l_3,\ldots, \l_\ell]$.

We have eliminated the occurence of $1$ in $\nu$, replacing it by the 
invariant\hfill\break
 $k(\l)=\l_1-\l_2+\l_3-\cdots$ which is fundamental in the work
of [BE].  These authors give a finite version of $(\star)$, for 
$x=1$, by making use of a refinement of the notion of
strictness for partitions ({\it Lecture hall partitions}). 

The number of corners of a partition is an invariant which is not very
often exploited, according to Alladi, who shows that it can be put into use
to give a six-parameter extension to Heine transformation [All]. 
We would like to mention, however, that decomposing the diagram of a partition
into its maximal subrectangles is a key point in the description of
singularites of Schubert subvarieties of Grassmann varieties, or in the
description of the associated Kazhdan-Lusztig polynomials.  For what concerns
the theory of partitions proper, we refer to [Ma2] who studies the arithmetic
properties of  generating functions of partitions according to their number
of corners.

As an example of the statistics, here are the seven strict partitions
of weight $|\l|=17$, with $k(\l)=7$~:
$$\matrix{ 
{\s strict}\ \l  & {\s odd}\ \mu &{\s half\!-\!odd}\ \nu & {\s statistics} \cr
 [12,5]  & [11,1^6]  &[5]  & x_5  \ y^7\cr
 [11,5,1] & [9,3,1^5] & [4,1] & x_1x_4 \ y^7\cr
 [10,5,2] & [7,3,3,1^4] &[3,1,1] & x_1x_3\ y^7\cr
 [10,4,2,1] & [7,5,1^5] &[3,2] &x_2x_3 \ y^7\cr
 [9,5,3]   &[5,3^3,1^3] & [2,1,1,1] & x_1x_2  \ y^7\cr
  [9,4,3,1] & [5,5,3,1^4] &[2,2,1] & x_1x_2\ y^7\cr
 [8,5,4] &[3^5,1,1] & [1^5] & x_1 \ y^7\cr
}$$ 

\medskip
The bijection between strict and odd partitions can be made even more 
straightforward by making use of the two natural graphs having these partitions
as vertices.  Indeed, an elementary operation (an edge of the graph)
on strict partitions is adding $[0,\ldots,1,1,0,\ldots,0]$ 
(when it gives a strict partition).  This operation does not change 
the invariant $k(\l)$ and therefore the set of strict partitions decompose
into disjoint graphs having a one part partition $[k]$ at the origin.
Similarly, adding 2 at a part of an odd partition, when it gives a partition,
gives an odd partition and does not change the length of the partition.
Taking the reduced partitions $\mu$ instead of $\nu$, we thus see that
Sylvester's bijection is a bijection between the graph of strict partitions
with a fixed $k(\l)$ and the restriction of Young graph to partitions 
with no more than  $k$ parts.

For example, 
$$\l=[11,10,7,5,4,2,1] \leftrightarrow \left(\, k=6,\, 
\mu=[5,3,3,3,2,1],\, \nu=[11, 7, 7, 7, 5, 3]  \, \right)$$
has 4 neighbours which are

$$[12, 11, 7, 5, 4, 2, 1] \leftrightarrow \left(k=6,\, \mu=[6, 3, 3, 3, 2,
1]\right)$$
$$[11, 10, 8, 6, 4, 2, 1]\leftrightarrow \left(k=6,\, \mu=[5, 4, 3, 3, 2,
1]\right)$$
$$[11, 10, 7, 6, 5, 2, 1] \leftrightarrow \left(k=6,\, \mu=[5, 3, 3, 3, 2, 2]
\right)$$
$$      [11, 10, 7, 5, 4, 3, 2]\leftrightarrow \left(k=6,\, 
\mu=[5, 3, 3, 3, 3, 1]\right)$$

The only subtlety is that boxes are not added in the same order to
$\l$ or to $\mu$.

\medskip
\centerline{\bf References}

\medskip \parindent 0mm
[All]\  K. Alladi. {\it A fundamental invariant in theory of partitions},
Topics in Number Theory 

[And]\ G. Andrews. {The Theory of partitions}, Encycl. Math. {\bf 2},
Addison-Wesley (1996). 

[Bes]\ C. Bessenrodt. {\it A bijection for Lebesgue's partition identity
in the spirit of Sylvester}, Discrete Math. {\bf 132} (1994) 1--10. 

[BE]  M. Bousquet-Melou, K. Eriksson. {\it Lecture hall partitions},
  Ramanujan J. {\bf 1} (1997) 101--111.

[KY]\ D. Kim, A. Yee. {\it A note on partitions into distinct parts
and odd parts}, Ramanujan J. {\bf 3} (199) 227--231. 

[Ma1]\  P.A. MacMahon. {\it Combinatory Analysis}, Chelsea Reprints (1984). 

[Ma2]\  P.A. MacMahon. {\it Divisors of numbers in the theory of partitions},
 Proc. London M.S. {\bf 19} (1920) 75--113.

[Syl]\   J.J. Sylvester. {\it Three acts, and interact and an exodion},
  Collected Work, vol {IV}, Chelsea reprints, 1973, (1882) 1--96. 



\vskip 15mm
{\obeylines
\hfill                  C.N.R.S., Institut Gaspard Monge   \hfill
\hfill                  Universit\'e de Marne-la-Vall\'ee,  \hfill
\hfill                   5 Bd Descartes, Champs sur Marne,   \hfill
\hfill                   77454 Marne La Vall\'ee Cedex 2 FRANCE  \hfill
\hfill \tt                      Alain.Lascoux@univ-mlv.fr
\hfill                http://phalanstere.univ-mlv.fr/$\sim$al
}

  
\end
