% Article submitted to INTEGERS, August 27, 2002 %%%%%%%%%%%%%%%%%%%%%% \documentclass[12pt]{article} \textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt \evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \usepackage{amssymb} \usepackage{amsthm} \usepackage{amsmath} %\usepackage{cite} \makeatletter \newfont{\footsc}{cmcsc10 at 8truept} \newfont{\footbf}{cmbx10 at 8truept} \newfont{\footrm}{cmr10 at 10truept} \newcommand{\Om}{\underset{\geqq}\Omega} \newtheorem{Lemma}{Lemma}[section] \newtheorem{Theorem}[Lemma]{Theorem} \newtheorem{Proposition}[Lemma]{Proposition} \newtheorem{Corollary}[Lemma]{Corollary} \newtheorem{Notation}[Lemma]{Notation} \newtheorem{Remark}[Lemma]{Remark} \newtheorem{Definition}[Lemma]{Definition} \newtheorem{Table}[Lemma]{Table} %pagestyle{plain} %%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \begin{center} {\bf EXTENDING A RECENT RESULT OF SANTOS ON PARTITIONS INTO ODD PARTS} \vskip 20pt {\bf James A. Sellers}\\ {\smallit Department of Mathematics, The Pennsylvania State University, University Park, PA 16802, USA}\\ {\tt sellersj@math.psu.edu}\\ \vskip 10pt \end{center} \vskip 30pt \centerline{\smallit Received:8/27/02, Accepted: 4/7/03, Published: 4/9/03 } \vskip 30pt \centerline{\bf Abstract} \noindent In a recent note, Santos proved that the number of partitions of $n$ using only odd parts equals the number of partitions of $n$ of the form $p_1+p_2+p_3+p_4+\dots$ such that $p_1\geq p_2\geq p_3\geq p_4\geq\dots \geq 0$ and $p_1\geq 2p_2+p_3+p_4+\dots.$ Via partition analysis, we extend this result by replacing the last inequality with $p_1\geq k_2p_2+k_3p_3+k_4p_4+\dots,$ where $k_2, k_3, k_4, \dots$ are nonnegative integers. Several applications of this result are mentioned in closing. \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 3 (2003), \#A04\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt %%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{section}{Background} One of the most celebrated identities in the theory of partitions is attributed to Leonhard Euler and reads as follows: \begin{Theorem} Let $d(n)$ be the number of partitions of $n$ into distinct parts and let $o(n)$ be the number of partitions of $n$ into odd parts. Then, for all $n\geq 0,$ $d(n) = o(n).$ \end{Theorem} In a recent paper, Santos \cite{Santos} proved via a bijection that $o(n)$ also equals the number of partitions of $n$ of the form $p_1+p_2+p_3+p_4+\dots$ such that $p_1\geq p_2\geq p_3\geq p_4\geq\dots \geq 0$ and $p_1\geq 2p_2+p_3+p_4+\dots.$ Our goal in this note is to prove Santos' result via generating functions. Actually, we will prove a much more general result using the technique of partitions analysis, introduced by Percy MacMahon \cite[Vol. II, Section VIII]{Macmahon} and heavily utilized recently by G. Andrews, P. Paule, A. Riese and others \cite{APR1,APR2,APR3,APR4,APR5,APR6,APR7,APR8,APR9}. Our main theorem is as follows: \begin{Theorem} \label{mainthm} Let $K = (k_2, k_3, k_4, \dots)$ be an infinite vector of nonnegative integers. Define $p(n;K)$ as the number of partitions of $n$ of the form $p_1+p_2+p_3+p_4+\dots$ with $p_1\geq p_2\geq p_3\geq p_4\dots \geq 0$ and $p_1\geq k_2p_2+k_3p_3+k_4p_4+\dots.$ Then, for all $n\geq 0,$ $p(n;K)$ equals the number of partitions of $n$ whose parts must be 1's or of the form $\left(\sum_{i=2}^m k_i\right) + (m-1)$ for some integer $m\geq 2.$ \end{Theorem} Before turning to the proof of Theorem \ref{mainthm}, we briefly mention a few key items from partition analysis. First, we define the Omega operator $\underset{\geqq}\Omega.$ \begin{Definition} The operator $\underset{\geqq}\Omega$ is given by %\begin{equation} %\label{omegadef} $$ \underset{\geqq}\Omega \sum_{s_1=-\infty}^\infty \dots \sum_{s_j=-\infty}^\infty A_{s_1, \dots, s_j}\lambda_1^{s_1}\dots \lambda_j^{s_j} := \sum_{s_1=0}^\infty \dots \sum_{s_j=0}^\infty A_{s_1, \dots, s_j}, $$ %\end{equation} where the domain of the $A_{s_1, \dots, s_j}$ is the field of rational functions over ${\Bbb C}$ in several complex variables and the $\lambda_i$ are restricted to annuli of the form $1-\varepsilon < \vert \lambda_i \vert< 1+\varepsilon.$ \end{Definition} In the work below, we will also use the symbol $\mu$ as a parameter like $\lambda_j$ for some $j$. Finally, we need the following lemma involving the Omega operator. \begin{Lemma} \label{thmbasic} \begin{equation*} \Om \frac{1}{\left(1 - \lambda x \right)\left(1 - \frac{y}{\lambda} \right)} = \frac{1}{(1-x)(1-xy)}. \end{equation*} \end{Lemma} A proof of this result can be found in \cite[Lemma 1.1]{APR3}. \end{section} \vskip 30pt \begin{section}{Main Result} Now we are in position to prove Theorem \ref{mainthm} via generating function manipulations. \begin{proof} Note that \begin{eqnarray*} \sum_{n=0}^\infty p(n;K) q^n &=& \sum_{ \begin{tiny} \begin{array}{c} p_1 \geq p_2 \geq p_3 \geq \dots \geq 0 \\ p_1 \geq k_2p_2 + k_3p_3 + \dots \end{array} \end{tiny}} q^{p_1+p_2+p_3+\dots} \\ &=& \Om \sum_{ \begin{tiny} \begin{array}{c} p_1, p_2, p_3, \dots \geq 0 \\ \end{array} \end{tiny} } q^{p_1+p_2+p_3+\dots } \left( \lambda_1^{p_1-p_2}\lambda_2^{p_2-p_3}\lambda_3^{p_3-p_4} \dots \right)\mu^{p_1-k_2p_2-k_3p_3-\dots} \\ \end{eqnarray*} by the definition of the Omega operator. Hence, after rewriting the above and applying Lemma \ref{thmbasic} multiple times, we find that \begin{eqnarray*} \sum_{n=0}^\infty p(n;K) q^n &=& \Om \frac{1}{\left(1-q\lambda_1\mu \right)\left( 1 -\frac{q\lambda_2}{\lambda_1\mu^{k_2}}\right)\left( 1 -\frac{q\lambda_3}{\lambda_2\mu^{k_3}}\right)\dots}\\ &=& \Om \frac{1}{\left(1-q\mu \right)\left( 1 -\frac{q^2\lambda_2}{\mu^{k_2-1}}\right)\left( 1 -\frac{q\lambda_3}{\lambda_2\mu^{k_3}}\right)\dots}\\ &=& \Om \frac{1}{\left(1-q\mu \right)\left( 1 -\frac{q^2}{\mu^{k_2-1}}\right)\left( 1 -\frac{q^3\lambda_3}{\mu^{k_3+k_2-1}}\right)\dots}\\ \end{eqnarray*} We continue to apply Lemma \ref{thmbasic} to eliminate all parameters $\lambda_j$ to obtain $$ \sum_{n=0}^\infty p(n;K) q^n = \Om \left(\frac{1}{1-q\mu}\right) \left(\frac{1}{1-\frac{q^2}{\mu^{k_2 - 1}}} \right) \left(\frac{1}{1-\frac{q^3}{\mu^{k_2+k_3 - 1}}} \right) \dots $$ At this point, the only parameter to eliminate is $\mu.$ We now rewrite the generating function above in terms of geometric series and annilihate $\mu$ based on the definition of the Omega operator. Thus, \begin{eqnarray*} \sum_{n=0}^\infty p(n;K) q^n &=& \Om \sum_{a_1\geq 0} (q\mu )^{a_1}\sum_{a_2\geq 0} (q^2\mu^{-k_2+1})^{a_2} \sum_{a_3\geq 0} (q^3\mu^{-k_3-k_2+1})^{a_3} \dots \\ &=& \Om \sum_{a_1, a_2, a_3, \dots \geq 0} q^{a_1+2a_2+3a_3+\dots} \mu^{a_1+(-k_2+1)a_2 + (-k_3-k_2+1)a_3 +\dots} \\ &=& \Om \sum_{ \begin{tiny} \begin{array}{c} a_2, a_3,\dots \geq 0 \\ a_1 \geq (k_2-1)a_2 + (k_3+k_2-1)a_3 + \dots \end{array} \end{tiny}} \hspace{-.5in} q^{a_1+2a_2+3a_3+\dots} \mu^{a_1 - \left[ (k_2-1)a_2 + (k_3+k_2-1)a_3 + \dots \right]} \\ &=& \sum_{a_2\geq 0}q^{2a_2}\times \sum_{a_3\geq 0}q^{3a_3} \times \dots \times \sum_{a_1 \geq (k_2-1)a_2 + (k_3+k_2-1)a_3 + \dots } q^{a_1} \\ &=& \sum_{a_2\geq 0}q^{2a_2}\times \sum_{a_3\geq 0}q^{3a_3} \times \dots \times \frac{q^{(k_2-1)a_2 + (k_3+k_2-1)a_3 + \dots }}{1-q} \\ &=& \frac{1}{(1-q)(1-q^{k_2+1})(1-q^{k_3+k_2+2})(1-q^{k_4+k_3+k_2+3})\dots}. \end{eqnarray*} The result follows. \end{proof} \end{section} \vskip 30pt \begin{section}{Applications} We close with several comments related to Theorem \ref{mainthm}. First off, Santos' result is clearly proven via Theorem \ref{mainthm} using the vector $K = (2,1,1,1,\dots).$ Next, note that the vector $K = (1,0,0,0,\dots)$ also yields an obvious result. Namely, the number of partitions of $n$ of the form $p_1+p_2+p_3+\dots$ with $p_1\geq p_2\geq p_3\geq \dots \geq 0$ and $p_1\geq p_2$ is simply $p(n),$ whose generating function is $$ \frac{1}{(1-q)(1-q^2)(1-q^3)\dots}, $$ which is what we obtain in Theorem \ref{mainthm} with $K = (1,0,0,0,\dots).$ A third example of Theorem \ref{mainthm} arises in connection with the vector $K=(1,1,1,1,\dots).$ From Theorem \ref{mainthm} we find that the number of partitions of $n$ with $p_1\geq p_2+p_3+p_4+\dots$ equals the number of partitions of $n$ using 1's and even integers as parts. This means $$\sum_{n=0}^\infty p(n;(1,1,1,1,\dots)) q^n = \frac{1}{(1-q)(1-q^2)(1-q^4)(1-q^6)\dots}. $$ Note that, by generating function dissection, we have \begin{eqnarray*} &&\sum_{n=0}^\infty p(2n;(1,1,1,1,\dots)) q^{2n}\\ &=& \frac{1}{2}\left[ \sum_{n=0}^\infty p(n;(1,1,1,1,\dots)) q^n + \sum_{n=0}^\infty p(n;(1,1,1,1,\dots)) (-q)^n \right] \\ &=& \frac{1}{2}\left(\frac{1}{(1-q^2)(1-q^4)(1-q^6)\dots}\right)\left( \frac{1}{1-q}+\frac{1}{1+q}\right) \\ &=& \frac{1}{2}\left(\frac{1}{(1-q^2)(1-q^4)(1-q^6)\dots}\right)\left( \frac{2}{(1-q)(1+q)}\right) \\ &=& \frac{1}{(1-q^2)^2(1-q^4)(1-q^6)\dots}. \end{eqnarray*} Thus, $$ \sum_{n=0}^\infty p(2n;(1,1,1,1,\dots)) q^{n} = \frac{1}{(1-q)^2(1-q^2)(1-q^3)\dots}. $$ Similar analysis shows that $p(2n+1;(1,1,1,1,\dots))$ has the same generating function. A variant of this generating function recently arose in the context of graphical forest partitions \cite{FSS}. Namely, let $gf(2k)$ be the number of partitions of $2k$ such that each partition, when viewed as the degree sequence of a graph, has a graphical representation which is a tree or union of trees (forest). Since the generating function for $gf(2n),$ as shown in \cite{FSS}, is $$ \frac{q}{(1-q)^2(1-q^2)(1-q^3)\dots}, $$ we now know that $$p(2n-2; (1,1,1,1,\dots)) = gf(2n)$$ for all $n\geq 1.$ We close with one last well-known partition function which is related to the Rogers-Ramanujan identities. Namely, let $p_5^{*}(n)$ be the number of partitions of $n$ into parts congruent to $\pm 1 \pmod{5}.$ Then it is clear that $p_5^{*}(n) = p(n; (3,1,2,1,2,1,2,\dots))$ for all $n$. By way of generalization, let $p_m^{*}(n)$ be the number of partitions of $n$ into parts congruent to $\pm 1 \pmod{m}$ (for $m\geq 3$). Then, for all $n\geq 0,$ $$p_m^{*}(n) = p(n;(m-2,1,m-3,1,m-3,1,m-3,\dots)).$$ Of course, the case $m=4$ returns us to Santos' result, the original motivation for this note. \end{section} \vskip 30pt \begin{thebibliography}{99} \footnotesize \bibitem{APR1} G. Andrews, {\it MacMahon's partition analysis: I. The lecture hall partition theorem}, in Mathematical Essays in Honor of Gian-Carlo Rota, B.E. Sagan and R.P. Stanley, eds, pp. 1-22. Boston, Birkhäuser, 1998. \bibitem{APR2} G. Andrews, {\it MacMahon's partition analysis: II. Basic theorems}, Ann. Comb. 4 (2000), 327-338. \bibitem{APR3} G. Andrews, P. Paule and A. Riese, {\it MacMahon's partition analysis: The omega package}, Europ J. Combinatorics 22, no. 7 (2001), 887-904. \bibitem{APR4} G. Andrews and P. Paule, {\it MacMahon's partition analysis IV: Hypergeometric multisums}, Paper B42i, Issue 42, S\a'eminaire Lotharingien de Combinatoire (electronic journal). \bibitem{APR5} G. Andrews, P. Paule, A. Riese and V. Strehl, {\it MacMahon's partition analysis V: Bijections, recursions and magic squares}, Algebraic Combinatorics and Applications, proccedings of Euroconference Alcoma99, September 12-19, 1999, Goessweistein, Germany, A. Betten, A. Kohnert, R. Laue and A. Wassermann, eds., pp. 1-39. Berlin, Springer, 2001. \bibitem{APR6} G. Andrews, P. Paule and A. Riese, {\it MacMahon's partition analysis VI: A new reduction algorithm}, Ann. Comb. 5, no. 3-4 (2001), 251--270. \bibitem{APR7} G. Andrews, P. Paule and A. Riese, {\it MacMahon's partition analysis VII: Constrained compositions}, AMS Contemporary Mathematics 291 (2001), 11-27. \bibitem{APR8} G. Andrews, P. Paule and A. Riese, {\it MacMahon's partition analysis VIII: Plane partition diamonds}, Advances in Appl. Math. 27 (2001), 231-242. \bibitem{APR9} G. Andrews, P. Paule and A. Riese, {\it MacMahon's partition analysis IX: k-gon partitions}, Bull. Austral. Math. Soc. 64 (2001), 321-329. \bibitem{FSS} D. Frank, C. Savage and J. Sellers, {\it On the number of graphical forest partitions}, to appear in Ars Comb. \bibitem{Macmahon} P. MacMahon, {\it Combinatory Analysis}, 2 Volumes, Cambridge University Press, Cambridge, 1915-1916 (Reprinted: Chelsea, New York, 1960). \bibitem{Santos} J. P. De O. Santos, {\it On a new combinatorial interpretation for a theorem of Euler}, Adv. Stud. Contemp. Math. (Pusan) 3, no. 2 (2001), 31-38. \end{thebibliography} \end{document}