%%%%%%%%%%%%%%%%%%%%% CUT HERE %%%%%%%%%%%%%%%%%%%%%%%%%%%%% \magnification\magstep 1 \input amstex \documentstyle{amsppt} \input epsf.tex \define\A{\operatorname{A}} \define\dd{d} \define\BB{\operatorname{B}} \define\CA{\operatorname{\Cal A}} \define\CB{\operatorname{\Cal B}} \define\la{\lambda} \define\al{\alpha} \define\be{\beta} \topmatter \title A Generalization of Sylvester's Identity \endtitle \rightheadtext{A Genaralization of Sylvester's Identity} \leftheadtext{Igor~Pak and Alexander~Postnikov} \author Igor Pak\smallskip {\rm Department of Mathematics\\ Harvard University, Cambridge, MA 02138\\ E-mail address: pak\@math.harvard.edu} \bigskip Alexander Postnikov\smallskip {\rm Department of Mathematics\\ Massachusetts Institute of Technology\\ Cambridge, MA 02139\\ E-mail address: apost\@math.mit.edu} \endauthor %\affil Harvard University \\ %Massachusetts Institute of Technology \endaffil %\address Department of Mathematics, Harvard University, Cambridge MA 02138 %\endaddress %\email pak\@math.harvard.edu \endemail %\address Department of Mathematics, Mass. Inst. %of Tech., Cambridge, MA 02139 \endaddress %\email apost\@math.mit.edu \endemail \date January 15, 1995 \enddate %\dedicatory \enddedicatory %\thanks \endthanks %\keywords \endkeywords %\subjclass \endsubjclass \abstract We consider a new generalization of Euler's and Sylvester's identities for partitions. Our proof is based on an explicit bijection. \endabstract \endtopmatter \document %\toc\widestnumber\head{10} %\endtoc \head 1. Main Results \endhead A {\it partition\/} $\la$ of $n$ is a sequence $(\la_1,\la_2,\dots,\la_l)$ of positive integers such that $\la_1\ge\la_2\ge\dots\ge\la_l>0$ and $\sum\la_i=n$. The numbers $\la_i$ are called {\it parts\/} of $\la$. Denote by $l(\la)$ the number $l$ of parts in $\la$. One of the well-known facts in the theory of partitions is Euler's identity. \proclaim{Theorem (Euler, 1748)} The number of partitions of $n$ with odd parts is equal to the number of partitions of $n$ with distinct parts. \endproclaim There exist several generalizations of Euler's identity (e.g.\ see \cite{A2}, \cite{C}). One of them is Sylvester's identity. By $\CA(n,k)$ denote the set of partitions of $n$ into odd parts (repetitions allowed) with exactly $k$ different parts. By $\CB(n,k)$ denote the set of partitions $\lambda=(\la_1>\la_2>\dots>\la_l)$ of $n$ such that the sequence $(\la_1{-}l,\la_2{-}l{+}1,\dots,\la_l{-}1)$ has exactly $k$ different elements. Let $\A(n,k)=\#\CA(n,k)$ and $\BB(n,k)=\#\CB(n,k)$. \proclaim{Theorem (Sylvester, 1882)} $\A(n,k)=\BB(n,k)$. \endproclaim \example{Example} Let $n=13$, $k=3$. Then $\CA(13,3)=\{(9,3,1),(7,5,1),(7,3,1^3),\allowmathbreak(5,3^2,1^2),(5,3,1^5)\}$ and $\CB(13,3)=\{(9,3,1),(8,4,1),(7,4,2),(7,5,1),(6,4,2,1)\}$. Hence $\A(13,3)=\BB(13,3)=5$. \endexample We present a generalization of these identities. By $\CA(n,m,c)$ denote the set of all partitions of $n$ with parts $\equiv c \text{ mod } m$; $\A(n,m,c)=\#\CA(n,m,c)$. We say that $\la$ is a {\it partition of type\/} $(h_1,h_2,\dots)$, if $\la$ has exactly $h_1\ge1$ parts of maximal length, $h_2\ge1$ second by length parts, etc. Let $1\le c0)$ we associate its {\it Young diagram\/} which is the set of pairs $(i,j)\in\Bbb Z^2$ such that $1\le i\le l$, $1\le j\le \la_i$. Pairs $(i,j)$ are arranged on the plane $\Bbb R^2$ with $i$ increasing downward and $j$ increasing from left to right. The diagram will be presented in form of a set of $1\times 1$-boxes centered at $(i,j)$. A partition $\la'=(\la_1'\ge\la_2'\ge\dots\ge\la_s'>0)$ is called {\it conjugate\/} to a partition $\la=(\la_1\ge\la_2\ge\dots\ge\la_l>0)$ if their Young diagrams are symmetric to each other with respect to the principal diagonal. Note that $\la_1'=l(\la)$ is the number of parts of $\la$ and $(\la')'=\la$. The {\it sum\/} of partitions $\la$ and $\mu$ is a partition $\la+\mu$ such that $(\la{+}\mu)_i=\la_i+\mu_i$. The {\it union\/} of partitions $\la$ and $\mu$ is a partition $\la\cup\mu$ such that its parts are the union of parts of $\la$ and $\mu$ arranged in nonincreasing order. It is easy to see that $(\la\cup\mu)'=\la'+\mu'$. Let $m\cdot\la=\la+\la+\dots+\la$ ($m$ times) and $\la/m=\mu$ if $\la=m\cdot\mu$. The {\it Generalized Frobenius Representation\/} $(\alpha,\beta)$ of $\la\in\CA(n,m,c)$ is defined as follows. Let $d=\dd(\la,m,c)$ be $(m,c)$-depth of $\la$. Let $\alpha_i=\la_i{-}m\,i{+}m{-}c$, $1\le i\le d$ be the number of boxes in the $i$th row of $\la$ to the right of the point $(i,m\,i{-}m{+}c)$. Let $\be_j=\la_j'-\lfloor(j{-}a)/m\rfloor)$, $1\le j\le m\,c{+}d$ be the number of boxes in the $j$th column of $\la$ below the point $(\lfloor(j{-}a)/m\rfloor,j)$, (here $\lfloor x\rfloor$ denotes the maximal integer such that $\lfloor x\rfloor\le x$). Then $\alpha=(\alpha_1>\alpha_2>\dots>\alpha_d>0)$, $\alpha_i\equiv 0 \text{ mod } m$; and $\be=(\be_1\ge\be_2\ge\dots)$. Define a map $\psi$ by $\psi(\la):=\be+\gamma$, where $\gamma= (m\cdot(\alpha/m)')'$. Prove that $\psi$ is a bijection between $\CA(n,m,c)$ and $\CB(n,m,c)$. It is clear that $\be$ is a partition of type $(c,m,m,\dots)$ and $\gamma$ is of type $(m,m,m,\dots)$. Hence $\be+\gamma$ is of type $(c,m{-}c,c,m{-}c,\dots)$, i.e.\ $\psi(\la)\in \CB(n,m,c)$. Conversely, for each $\mu\in\CB(n,m,c)$ there is a unique decomposition $\mu=\delta+\nu$, where $\delta$ is a partition of type $(c,m,m,\dots)$ and $\nu$ of type $(m,m,m,\dots)$. Indeed, $\delta'$ consists of all parts of $\mu'$ congruent with $c \text{ mod } m$ and $\nu'$ consists of all parts of $\mu'$ congruent with $0\text{ mod }m$. Then $\mu=(\delta'\cup\nu')'=\delta+\nu$. Therefore $\psi$ is a bijection between $\CA(n,m,c)$ and $\CB(n,m,c)$ and we have proved Theorem 1. \example{Example} Let $\la=(10,7^2,4^3,1)\in\CA(37,3,1)$. Then $\alpha=(9,3)$; $\be=(7,5^3,1^3)$; $\gamma=(3\cdot(\alpha/3)')'=(3\cdot(3,1)')'=(3\cdot(2,1^2))'=(6,3^2)'= (3^3,1^3)$; $\psi(\la)=\be+\gamma=(10,8^2,6,2^2,1)\in\CB(37,3,1)$ (See Fig.~1). \midinsert \vskip 10pt \line{\hfil\epsfysize=5cm\epsfbox{sylv1.eps}\hfil} \vskip 10pt \botcaption{Fig.~1} \endcaption \endinsert Note that $\la\in\CA(37,3,1,4)$, because $\la $ has exactly 4 different parts 11, 7, 4, 1; and $\psi(\la)\in\CB(37,3,1,4)$, because $\psi(\la)$ has exactly 4 maximal chains $(10)$, $(8,8)$, $(6)$, $(2,2,1)$. Note also that $\dd(\la,3,1)=2$. \endexample In order to prove Theorems~2 and 3 we shall verify the corresponding properties of the bijection $\psi$. \proclaim{Lemma 1} If $\la\in\CA(n,m,c,k)$ then $\psi(\la)\in\CB(n,m,c,k)$. \endproclaim \demo{Proof} Let $d=\dd(\la,m,c)$. Note that the number of parts $l(\psi(\la))$ of $\psi(\la)$ is equal to $\max(l(\beta),l(\gamma)) =m\,d+m$ if $l(\beta)l(\gamma)$. Let $$\align Q&=\{1\le q\le l(\psi(\la)):\psi(\la)_q-\psi(\la)_{q{+}1}>1\};\\ Q_1&=\{1\le q\le l(\beta):\beta_q-\beta_{q{+}1}>1\};\\ Q_2&=\{1\le q\le l(\gamma):\gamma_q-\gamma_{q{+}1}>1\}. \endalign $$ Clearly, if $q\in Q_1$ (or $q\in Q_2$) then $q\equiv c$ (or $q\equiv 0$) mod $m$. Hence $Q_1\cup Q_2=Q$, $Q_1\cap Q_2=\emptyset$, and $\#Q=\#Q_1+\#Q_2$. Then $\#Q=k-1$, i.e.\ $\psi(\la)$ has exactly $k$ maximal chains. Therefore $\psi(\la)\in\CB(n,m,c,k)$. \enddemo Theorem~2 immediately follows from Lemma~1. \proclaim{Lemma 2} If $\la\in\CA(n,m,c,k)$ and $\mu=\psi(\la)\in\CB(n,m,c,k)$ then $\la_1+m\,l(\la)=m\, \mu_1+c$. \endproclaim \demo{Proof} Clearly $\mu_1=\psi(\la)_1=\beta_1+\gamma_1=l(\la)+\alpha_1/m= l(\la)+(\la_1-c)/m$. Hence $\la_1+m\,l(\la)=m\, \mu_1+c$. \enddemo This lemma completes the proof of Theorem~3. \smallskip \head 3. Conclusion \endhead \proclaim{Proposition 1} If $m=2$ and $c=1$ then the bijection $\psi:\CA(n,2,1)\to\CB(n,2,1)$ coincides with Sylvester's bijection. \endproclaim \midinsert \vskip 10pt \line{\hfil\epsfysize=5cm\epsfbox{sylv2.eps}\hfil} \vskip 10pt \botcaption{Fig.~2} \endcaption \endinsert We do not present here the original Sylvester's construction (see \cite{S}). There exists a simple inductive proof of this proposition. \example{Example} Let $\la=(7,5,3^2)$. Then $\alpha=(6,2)$; $\beta=(4,3^2)$; $\gamma=(3^2,2)$; and $\psi(\la)=(7,6,4,1)$. The idea of Sylvester's bijection is clear from Fig.~2. \endexample Note also that for $m=1$ and $c=0$ the Generalized Frobenius Representation is exactly Frobenius Representation (see \cite{M}) and $(1,0)$-depth is the size of {\it Durfee's Square\/} (see \cite{A2}). We are grateful to Andrei Zelevinsky for helpful remarks and to George Andrews for interest in this paper and help with the references. \Refs \widestnumber\key{A3} \ref\key A1\by G. E. Andrews \paper On basic hypergeometric series, mock theta functions and partitions \rom{1} \jour Quart. J. Math. Oxford Ser. \vol 17 \yr 1966 \pages 132--143 \endref \ref\key A2\by G. E. Andrews \book The Theory of Partitions, Encyclopedia of Mathematics and its Applications \vol 2 \publ Addison-Wesley \publaddr Reading, Massachusetts \yr 1976 \endref \ref\key A3\by G. E. Andrews \paper On a partition theorem of N.~J.~Fine \jour J. Nat. Acad. Math. \vol 1 \yr 1983 \pages 105--107 \endref \ref\key A4\by G. E. Andrews \paper Use and extension of Frobenius representation of partitions \inbook Enumeration and Design \eds D.~M.~Jackson and S.~A.~Vanston \publ Academic Press %\publaddr Toronto \yr 1984 \pages 51--65 \endref \ref\key C \by D.~I.~A.~Cohen \paper PIE-sums: a combinatorial tool for partition theory \jour J. Comb. Theory, Ser. A \vol 31\yr 1981 \pages 223--236 \endref \ref\key F1\by N.~J.~Fine \paper Some new results on partitions \jour Proc. Nat. Acad. Sci. USA \vol 34 \yr 1948 \pages 616--618 \endref \ref\key F2\by N.~J.~Fine \book Some Basic Hypergeometric Series and Applications \bookinfo Unpublished monograph \endref \ref\key M\by I.~G.~Macdonald \book Symmetric Functions and Hall Polynomials \publ Claredon Press \publaddr Oxford \yr 1979 \endref \ref\key S\by J.~J.~Sylvester \paper A constructive theory of partitions, arranged in three acts, an interact and an exodin \jour Amer. J. Math. \vol 5\yr 1882 \pages 251--330 \moreref \vol 6\yr 1884\pages 334--336 \endref \endRefs \enddocument