Sylvester’s bijection between strict and odd partitions

Alain Lascoux

Sylvester [Syl] produced a bijection between strict partitions λ and odd ones ν, preserving the weight and exchanging the number of “strings” of λ with the number of different parts of ν (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 λ and ν : 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 λ and ν. 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]).

A strict partition λ = [λ_{1}, λ_{2}, …, λ_{ℓ}, 0], λ_{ℓ} ≠ 0, is a decreasing partition with distinct parts, with a 0 added, ℓ being the length of λ.

Write boxes between parts of λ, alternatively up and down, beginning with a down box between (λ_{2}, λ_{3}):

λ ⟶ λ_{1} λ_{2}  λ_{3}  λ_{4}  λ_{5}  λ_{6}  ⋯

Fill the top boxes with repeated letters, 1^{λ_{3}−λ_{4}}, 2^{λ_{5}−λ_{6}}, 3^{λ_{7}−λ_{8}}, … respectively. Fill the bottom boxes, from right to left, with strings of consecutive integers of respective lengths …, λ_{4} − λ_{5}, λ_{2} − λ_{3}, each string beginning at the last value in the preceding one, the first string beginning with ⌊ℓ/2⌋. 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 λ = [11, 10, 7, 5, 4, 1, 0], one has :

11 10  7  5  4  1  0_{345  3  3}^{11  222} ↦ \begin{matrix}1 \\ 1 & 2 \\ · & 2 \\ · & 2 & 3 \\ · & · & 3 \\ · & · & 3 & 4 & 5 \end{matrix} ↦  = μ

The ribbon itself is the border of a partition μ. Doubling μ (i.e. doubling each part), adding to it a first column of length k(λ) := λ_{1} − λ_{2} + λ_{3} − λ_{4} − ⋯, one gets a partition ν with odd parts.

Now, the parameters k, λ_{2} −λ_{3}, λ_{3} −λ_{4}, … code bijectively λ as well as μ. Given them, one gets a pair : λ is strict and ν is odd. The only point to check is that k(λ) 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 ν (apart from the part 1). By construction, they correspond to the indices i > 1 such that λ_{i} − λ_{i+1} > 1, that is to the decomposition of [λ_{2}, λ_{3}, …] into maximal strings of consectutive integers. Moreover, λ_{1} − λ_{2} = 1 is exactly the case when ℓ(μ) = ℓ(ν), i.e. when ν does not have 1 as a part.

The above ribbon, for λ = [11, 10, 7, 5, 4, 1], gives

μ = [5, 3, 3, 2, 2, 1] , ν = [10, 6, 6, 4, 4, 2] + 1^{6} = [11, 7, 7, 5, 5, 3] .

From this construction, one can easily deduce a little more than Sylvester’s statement. To each odd partition ν ↔ (k, μ) attach the monomial y^{ℓ(μ)}q^{|ν|}x_{1}^{ϵ_{1}}x_{2}^{ϵ_{2}}x_{3}^{ϵ_{3}} ⋯ with ϵ_{i} = 1

or 0 whether 2i + 1 is a part of μ or not (↔ i is a part of ν or not).

The generating function of odd partitions with such statistics is

\frac{1}{1 − yq} ∏_{1}^{∞} (1 + x_{i} \frac{yq^{2i+1}}{1 − yq^{2i+1}} )

and the above bijection shows that it is equal to

∑ q^{|λ|}y^{k(λ)}x_{1}^{ϵ_{1}}x_{2}^{ϵ_{2}} ⋯,

sum on all strict partitions λ, the ϵ_{i}’s being 0 or 1 whether λ_{j} − λ_{j+1} = 1 or not, the correspondence between j and i being given by the bijection.

In particular, for x_{1} = x_{2} = ⋯ = x, one recovers the statistics which can be deduced from Sylvester’s theorem :

∑_{λ} q^{|λ|}y^{k(λ)}x^{str} = \frac{1}{1 − yq} ∏_{1}^{∞} (1 + x\frac{yq^{2i+1}}{1 − yq^{2i+1}} ) ,  (⋆)

with str = number of maximal strings of consecutive integers in [λ_{2}, λ_{3}, …, λ_{ℓ}].

We have eliminated the occurence of 1 in ν, replacing it by the invariant k(λ) = λ_{1} − λ_{2} + λ_{3} − ⋯ which is fundamental in the work of [BE]. These authors give a finite version of (⋆), for x = 1, by making use of a refinement of the notion of strictness for partitions (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 |λ| = 17, with k(λ) = 7 :

\begin{matrix}strict λ & odd μ & half−odd ν & statistics \\ [12, 5] & [11, 1^{6}] & [5] & x_{5} y^{7} \\ [11, 5, 1] & [9, 3, 1^{5}] & [4, 1] & x_{1}x_{4} y^{7} \\ [10, 5, 2] & [7, 3, 3, 1^{4}] & [3, 1, 1] & x_{1}x_{3} y^{7} \\ [10, 4, 2, 1] & [7, 5, 1^{5}] & [3, 2] & x_{2}x_{3} y^{7} \\ [9, 5, 3] & [5, 3^{3}, 1^{3}] & [2, 1, 1, 1] & x_{1}x_{2} y^{7} \\ [9, 4, 3, 1] & [5, 5, 3, 1^{4}] & [2, 2, 1] & x_{1}x_{2} y^{7} \\ [8, 5, 4] & [3^{5}, 1, 1] & [1^{5}] & x_{1} y^{7} \end{matrix}

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, …, 1, 1, 0, …, 0] (when it gives a strict partition). This operation does not change the invariant k(λ) 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 μ instead of ν, we thus see that Sylvester’s bijection is a bijection between the graph of strict partitions with a fixed k(λ) and the restriction of Young graph to partitions with no more than k parts.

For example,

λ = [11, 10, 7, 5, 4, 2, 1] ↔ ( k = 6, μ = [5, 3, 3, 3, 2, 1], ν = [11, 7, 7, 7, 5, 3] )

has 4 neighbours which are

[12, 11, 7, 5, 4, 2, 1] ↔ (k = 6, μ = [6, 3, 3, 3, 2, 1])
[11, 10, 8, 6, 4, 2, 1] ↔ (k = 6, μ = [5, 4, 3, 3, 2, 1])
[11, 10, 7, 6, 5, 2, 1] ↔ (k = 6, μ = [5, 3, 3, 3, 2, 2])
[11, 10, 7, 5, 4, 3, 2] ↔ (k = 6, μ = [5, 3, 3, 3, 3, 1])

The only subtlety is that boxes are not added in the same order to λ or to μ.

References

[All] K. Alladi. A fundamental invariant in theory of partitions, Topics in Number Theory [And] G. Andrews. The Theory of partitions, Encycl. Math. 2, Addison-Wesley (1996).

[Bes] C. Bessenrodt. A bijection for Lebesgue’s partition identity in the spirit of Sylvester, Discrete Math. 132 (1994) 1–10.

[BE] M. Bousquet-Melou, K. Eriksson. Lecture hall partitions, Ramanujan J. 1 (1997) 101–111.

[KY] D. Kim, A. Yee. A note on partitions into distinct parts and odd parts, Ramanujan J. 3 (199) 227–231.

[Ma1] P.A. MacMahon. Combinatory Analysis, Chelsea Reprints (1984).

[Ma2] P.A. MacMahon. Divisors of numbers in the theory of partitions, Proc. London M.S. 19 (1920) 75–113.

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

C.N.R.S., Institut Gaspard Monge Université de Marne-la-Vallée,

5 Bd Descartes, Champs sur Marne, 77454 Marne La Vallée Cedex 2 FRANCE

                                                  Alain.Lascoux@univ-mlv.fr
                                        http://phalanstere.univ-mlv.fr/∼al