%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% pars_nonpolys - Version 6 - May 2004 %%%% Final version submitted to JIS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage{amsthm} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Partitions Excluding Specific Polygonal Numbers As Parts} \vskip 1cm \large James A. Sellers\\ Department of Mathematics\\ The Pennsylvania State University\\ University Park, PA 16802\\ \href{mailto:sellersj@math.psu.edu}{\tt sellersj@math.psu.edu} \\ \end{center} \begin{abstract} Many results appear in the literature involving partitions of an integer $n$ into parts which are certain polygonal numbers (such as triangular numbers or squares). However, few results appear which deal with partition functions that exclude specific polygonal numbers as parts. We consider such functions in this note, and prove two families of partition identities. \end{abstract} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}{Proposition}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{lemma}{Lemma}[section] %\usepackage{hyperref} %\usepackage{amssymb} %\setlength{\topmargin}{-.5in} % %\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \newtheorem{Lemma}{Lemma}[section] \newtheorem{Theorem}[Lemma]{Theorem} \newtheorem{Prop}[Lemma]{Proposition} \newtheorem{Corollary}[Lemma]{Corollary} \newcommand{\N}[2]{N^{\#}_{#1}(#2)} \newtheorem{Notation}[Lemma]{Notation} \newtheorem{Remark}[Lemma]{Remark} \newtheorem{Table}[Lemma]{Table} \newtheorem{Definition}[Lemma]{Definition} %\renewcommand{\baselinestretch}{1.2} %\renewcommand{\arraystretch}{.7} \begin{section}{Introduction} A {\bf partition} $\lambda$ of the nonnegative integer $n$ is a sequence of nonnegative integers $\lambda_1\geq \lambda_2\geq \dots \geq \lambda_r$ with $\lambda_1+ \lambda_2+\dots+ \lambda_r = n.$ Each value $\lambda_i,$ $1\leq i\leq r,$ is called a {\bf part} of the partition. In this note, we consider partitions of $n$ with parts related to $k$-gonal numbers for some fixed integer $k\ge 3.$ Various works have appeared involving partitions into polygonal parts. For example, M. D. Hirschhorn and the author have written a number of papers on partitions into a specified number of triangular numbers or squares \cite{HS1}--\cite{HS3}. Also, Andrews \cite[Theorem 4.1]{AndII} considers partitions into an unlimited number of triangular numbers. (Several sequences related to such partitions appear in Sloane's Online Encyclopedia of Integer Sequences \cite{Sloane}, including \seqnum{A001156}, \seqnum{A002635}, \seqnum{A002636}, and \seqnum{A007294}.) In contrast, few results appear in the literature in which polygonal numbers are {\it excluded} as parts. Andrews \cite[Corollary 8.5]{And1} highlights one such instance when he considers the number of partitions of $n$ with no square parts. Interestingly enough, Sloane \cite{Sloane} recently published this sequence of values (\seqnum{A087153}) in August 2003. Our goal here is two-fold. First, we consider Andrews' result above and extend it to all $2k$-gons for $k\geq 2.$ Afterwards, we prove a similar result for $2k+1$-gons. Some brief comments on polygonal numbers, or $k$-gons, are in order. For a fixed integer $k\geq 3,$ the $n^{th}$ $k$-gonal number is given by $$\left( \frac{k-2}{2}\right)n^2 - \left(\frac{k-4}{2}\right)n.$$ So, for example, the 3-gonal numbers, or triangular numbers (\seqnum{A000217}), are given by $$\left( \frac{3-2}{2}\right)n^2 - \left(\frac{3-4}{2}\right)n = \frac{n^2}{2} + \frac{n}{2}$$ while the 4-gons, or squares (\seqnum{A000290}), are given by $$\left( \frac{4-2}{2}\right)n^2 - \left(\frac{4-4}{2}\right)n = n^2.$$ \end{section} \begin{section}{Partitions Excluding $2k$--gons as Parts} We now state Andrews' result \cite[Corollary 8.5]{And1}. \begin{Theorem} \label{And-nonsquares} Let $p_1(n)$ be the number of partitions of $n$ wherein each part $i$ appears at most $i-1$ times and let $p_2(n)$ be the number of partitions of $n$ with no square parts. Then, for all nonnegative integers $n,$ $p_1(n) = p_2(n).$ \end{Theorem} Before proving this result, which involves a straightforward generating function argument, we consider one example to confirm our result. The partitions of the integer 6 (with no restrictions on the parts) are given by $$6,\ 5+1,\ 4+2,\ 4+1+1,\ 3+3,\ 3+2+1,\ 3+1+1+1,\ 2+2+2, $$ $$2+2+1+1,\ 2+1+1+1+1, \textrm{\ \ and\ \ } 1+1+1+1+1+1.$$ Note that those partitions above with no square parts are $$6, 3+3, \textrm{\ and\ } 2+2+2, $$ while those wherein each part $i$ appears at most $i-1$ times are $$6, 4+2, \textrm{\ and\ } 3+3.$$ Thus, $p_1(6) = p_2(6) =3.$ We now turn to a generating function proof of Theorem \ref{And-nonsquares}. \begin{proof} First, it is clear that \begin{eqnarray*} \sum_{n=0}^\infty p_2(n)q^n &=& \prod_{i=1}^\infty \frac{1-q^{i^2}}{1-q^i}\\ &=& \frac{1-q^1}{1-q^1}\cdot\frac{1-q^4}{1-q^2}\cdot\frac{1-q^9}{1-q^3}\cdot\frac{1-q^{16}}{1-q^4}\cdots \end{eqnarray*} Next, we note that each of the ratios in the product above can be rewritten as a finite geometric series thanks to the following fact: \begin{equation} \label{finitegeom} \frac{1-x^{aj}}{1-x^a} = 1+x^a+x^{2a}+\dots +x^{(j-1)a} \end{equation} Hence, we see that $\sum\limits_{n=0}^\infty p_2(n)q^n$ can be written as $$(1)(1+q^2)(1+q^3+q^6)(1+q^4+q^8+q^{12})(1+q^5+q^{10}+q^{15}+q^{20})\cdots$$ or $$\prod_{i=1}^\infty (1+q^i+q^{2i}+\dots+q^{i(i-1)}).$$ This is the generating function for $p_1(n)$, which yields the result. \end{proof} What fundamentally drives the proof above is the fact that $i\,|\,i^2$ for each positive integer $i$, as this allows for the use of (\ref{finitegeom}) in our proof. This insight allows us to extend Theorem \ref{And-nonsquares} in a natural fashion. \begin{Theorem} \label{2k-gons} Let $k\geq 2$ be a fixed integer. Let $p_3(n,k)$ be the number of partitions of $n$ wherein each part $i$ appears at most $(k-1)(i-1)$ times and let $p_4(n,k)$ be the number of partitions of $n$ wherein no $2k$--gons can be used as parts. Then, for all nonnegative integers $n,$ $p_3(n,k) = p_4(n,k).$ \end{Theorem} Note that Theorem \ref{And-nonsquares} is just a corollary of Theorem \ref{2k-gons} upon setting $k=2.$ \begin{proof} As above, the proof we provide here is simply a generating function manipulation. From (\ref{finitegeom}) we see that \[ \frac{1-q^{\left( \frac{2k-2}{2}\right)i^2 - \left(\frac{2k-4}{2}\right)i}}{1-q^i} = 1+q^i+q^{2i}+\dots + q^{i[(k-1)i-(k-2)-1]}. \] Hence, \begin{eqnarray*} \sum_{n=0}^\infty p_4(n,k)q^n &=& \prod_{i=1}^\infty \frac{1-q^{\left( \frac{2k-2}{2}\right)i^2 - \left(\frac{2k-4}{2}\right)i}}{1-q^i} \\ &=& \prod_{i=1}^\infty \left( 1+q^i+q^{2i}+\dots + q^{i[(k-1)i-(k-2)-1]} \right)\\ &=& \prod_{i=1}^\infty \left( 1+q^i+q^{2i}+\dots + q^{i(k-1)(i-1)} \right) \textrm{\ \ after simplification}. \end{eqnarray*} This last infinite product is, by definition, the generating function for $p_3(n,k),$ which proves the theorem. \end{proof} \end{section} \begin{section}{Partitions Excluding $2k+1$--gons as Parts} One may naturally ask whether a similar result exists for partitions of $n$ which contain no $2k+1$--gons as parts. Unfortunately, a perfect analogue does not exist, because it is not the case that $i$ divides $$\left( \frac{2k+1-2}{2}\right)i^2 - \left( \frac{2k+1-4}{2}\right)i$$ for all positive integers $i.$ However, it {\bf is} the case that such divisibility occurs when $i$ is odd. Indeed, \begin{eqnarray*} &&\left( \frac{2k+1-2}{2}\right)(2j-1)^2 - \left( \frac{2k+1-4}{2}\right)(2j-1)\\ \qquad &=& (2j-1)\left[\left( \frac{2k-1}{2}\right)(2j-1) - \left( \frac{2k-3}{2}\right)\right]\\ \qquad &=& (2j-1)(j(2k-1)-(2k-2)) \end{eqnarray*} so that $2j-1$ divides the $(2j-1)$st $2k+1$--gon. This observation leads to the following result. \begin{Theorem} \label{2k+1-gons} Let $p_5(n,k)$ be the number of partitions of $n$ wherein the part $2i-1 \ (i\geq 1)$ appears at most $(2k-1)(i-1)$ times (and the frequency of the even parts is unbounded). Let $p_6(n,k)$ be the number of partitions of $n$ wherein no odd--subscripted $2k+1$--gons can be used as parts. Then, for all nonnegative integers $n,$ $p_5(n,k) = p_6(n,k).$ \end{Theorem} An example may be beneficial before proving Theorem \ref{2k+1-gons}. We consider the case where $n=10$ and $k=1.$ The partitions enumerated by $p_5(10,1)$ are those wherein no 1s and at most one 3, two 5s, and three 7s can appear as parts (and even parts can appear with no restrictions on their number of occurrences). These partitions are as follows: $$10,\ 8+2,\ 7+3,\ 6+4,\ 6+2+2,\ 5+5,$$ $$5+3+2,\ 4+4+2,\ 4+2+2+2, \textrm{\ \ and\ \ } 2+2+2+2+2$$ On the other hand, those partitions enumerated by $p_6(10,1)$ are those in which odd--subscripted triangular numbers are not allowed as parts. (These unallowed parts would be $1,6,15,\dots.$) These partitions are as follows: $$10,\ 8+2,\ 7+3,\ 5+5,\ 5+3+2,\ 4+4+2,$$ $$4+3+3,\ 4+2+2+2,\ 3+3+2+2, \textrm{\ \ and\ \ } 2+2+2+2+2$$ Hence, $p_5(10,1) = p_6(10,1).$ \begin{proof} It is clear that $$ \sum_{n=0}^\infty p_6(n,k)q^n = \prod_{i=1}^\infty \left( \frac{1-q^{\left( \frac{2k+1-2}{2}\right)(2i-1)^2 - \left(\frac{2k+1-4}{2}\right)(2i-1)}}{1-q^i} \right). $$ This can be manipulated to yield \begin{eqnarray*} && \prod_{i=1}^\infty \left( \frac{1-q^{(2i-1)\left[\left( \frac{2k+1-2}{2}\right)(2i-1) - \left(\frac{2k+1-4}{2}\right)\right]}}{(1-q^{2i-1})(1-q^{2i})} \right)\\ \qquad &=& \prod_{i=1}^\infty \frac{1}{(1-q^{2i})} \cdot \left( 1+q^{2i-1} + q^{(2i-1)2} + \dots + q^{(2i-1)(2ik-i-2k+2-1)} \right)\\ \qquad &=& \prod_{i=1}^\infty \frac{1}{(1-q^{2i})} \cdot \left( 1+q^{2i-1} + q^{(2i-1)2} + \dots + q^{(2i-1)(2k-1)(i-1))} \right). \end{eqnarray*} This last infinite product is the generating function for $p_5(n,k),$ which completes the proof of Theorem \ref{2k+1-gons}. \end{proof} \end{section} \begin{section}{Closing Thoughts} Several thoughts are fitting as we close. First, for those dissatisfied with the concise generating function proofs given above for Theorems \ref{And-nonsquares}, \ref{2k-gons}, and \ref{2k+1-gons}, we offer a combinatorial proof of Theorem \ref{And-nonsquares} which is generalizable to proofs of Theorems \ref{2k-gons} and \ref{2k+1-gons}. \begin{proof}[Combinatorial Proof of Theorem \ref{And-nonsquares}.] We provide a bijection between the partitions counted by $p_1(n)$ and those counted by $p_2(n).$ The bijection is described as follows. Let $\lambda$ be a partition counted by $p_2(n),$ and assume that the part $\lambda_i$ appears in $\lambda$ exactly $\ell_i$ times. If $\ell_i < \lambda_i,$ then we map these $\ell_i$ occurrences of $\lambda_i$ to themselves. Next, we consider those parts $\lambda_i$ such that $\ell_i \geq \lambda_i.$ This means that we can sum many of these copies of $\lambda_i$ to obtain at least one copy of $\lambda_i^2.$ We build as many copies of $\lambda_i^2$ as possible in this fashion. If there are some ``leftover'' copies of $\lambda_i$ which could not be used to build an additional copy of $\lambda_i^2,$ then these copies of $\lambda_i$ are simply mapped to themselves. Now we iterate the process. If there are fewer than $\lambda_i^2$ copies of $\lambda_i^2$ at this stage, then we map them to themselves. However, if there are at least $\lambda_i^2$ copies of $\lambda_i^2,$ then we sum them to obtain as many copies of $\lambda_i^4$ as possible. We continue in this iterative fashion until it is no longer possible to create additional squares of the form $\lambda_i^{2^j}$. The result is the corresponding partition counted by $p_1(n).$ The inverse of this function is straightforward. Namely, the nonsquare parts in the partition $\lambda^*$ counted by $p_1(n)$ are mapped to themselves. Then each of the square parts in $\lambda^*$ are reduced (via square roots) in an iterative fashion until no squares are present. The result is the original partition counted by $p_2(n).$ \end{proof} An example of this bijection may prove useful. First, note the following partitions of the integer 36: $$2+2+2+2+2+2+2+2+2+2+2+2+2+2+2+2+2+2$$ $$3+3+3+3+3+3+3+3+3+3+3+3$$ $$6+6+6+6+6+6$$ All three of these partitions are counted by $p_2(36).$ Their corresponding partitions via the above bijection are $$16+16+4, \ 9+9+9+9, \textrm{\ and\ } 36$$ respectively. Moreover, it is clear from the proof given above that these three partitions counted by $p_1(36)$ are mapped back to the appropriate partitions via the inverse map described. As a more complete example, we provide a list of some of the partitions counted by $p_1(18)$ and $p_2(18).$ Note that those partitions counted by $p_1(18)$ which do {\bf not} contain any square parts are simply mapped to themselves, so these partitions have been omitted from this table. In the left--hand column below, we present the 22 partitions counted by $p_1(18)$ which contain at least one square part, and we write these in lexicographical order. In the right--hand column we present the corresponding partitions counted by $p_2(18)$ as generated by the bijection described above. \begin{eqnarray*} 16+2 &\longleftrightarrow& 2+2+2+2+2+2+2+2+2\\ 14+4&\longleftrightarrow& 14+2+2 \\ 12+4+2&\longleftrightarrow& 12+2+2+2 \\ 11+4+3&\longleftrightarrow& 11+3+2+2 \\ 10+4+4&\longleftrightarrow& 10+2+2+2+2 \\ 9+9&\longleftrightarrow& 3+3+3+3+3+3 \\ 9+7+2&\longleftrightarrow& 7+3+3+3+2 \\ 9+6+3&\longleftrightarrow& 6+3+3+3+3 \\ 9+5+4&\longleftrightarrow& 5+3+3+3+2+2 \\ 9+4+3+2&\longleftrightarrow& 3+3+3+3+2+2+2 \\ 8+6+4&\longleftrightarrow& 8+6+2+2 \\ 8+4+4+2&\longleftrightarrow& 8+2+2+2+2+2 \\ 8+4+3+3&\longleftrightarrow& 8+3+3+2+2 \\ 7+7+4&\longleftrightarrow& 7+7+2+2 \\ 7+5+4+2&\longleftrightarrow& 7+5+2+2+2 \\ 7+4+4+3&\longleftrightarrow& 7+3+2+2+2+2 \\ 6+6+4+2&\longleftrightarrow& 6+6+2+2+2 \\ 6+5+4+3&\longleftrightarrow& 6+5+3+2+2 \\ 6+4+4+4&\longleftrightarrow& 6+2+2+2+2+2+2 \\ 6+4+3+3+2&\longleftrightarrow& 6+3+3+2+2+2 \\ 5+5+4+4&\longleftrightarrow& 5+5+2+2+2+2 \\ 5+4+4+3+2&\longleftrightarrow& 5+3+2+2+2+2+2 \\ \end{eqnarray*} We close by noting that Andrews treats Theorem \ref{And-nonsquares} as a special case of a broader theorem on partition ideals of order one. Indeed, all the theorems in this paper fall into this genre, so that they can be proven with his technique as well. \end{section} \begin{section}{Acknowledgements} The author gratefully acknowledges the referee's insightful comments with regard to the combinatorial proof of Theorem \ref{And-nonsquares}. \end{section} \begin{thebibliography}{99} \bibitem{And1} G.E. Andrews, {\it The Theory of Partitions}, Addison-Wesley, 1976. \bibitem{AndII} G. E. Andrews, MacMahon's partition analysis. II. Fundamental theorems, \emph{Ann. Comb.} \textbf{4} (2000), no. 3-4, 327--338. \bibitem{HS1} M. D. Hirschhorn and J. A. Sellers, Some relations for partitions into four squares, in {\it Proceedings of the International Workshop on Special Functions, Asymptotics, Harmonic Analysis, and Mathematical Physics}, World Scientific, 2000, pp. 118-124. \bibitem{HS2} M. D. Hirschhorn and J. A. Sellers, On a problem of Lehmer on partitions into squares, to appear in \emph{Ramanujan J}. \bibitem{HS3} M. D. Hirschhorn and J. A. Sellers, Partitions into three triangular numbers, to appear in \emph{Australas. J. Combin}. \bibitem{Sloane} N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically at \htmladdnormallink{http://www.research.att.com/$\sim $njas/sequences/}{http://www.research.att.com/~njas/sequences/}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: \ \ 05A17 \noindent \emph{Keywords:} partition, polygonal number, generating function, geometric series. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000217}, \seqnum{A000290}, \seqnum{A001156}, \seqnum{A002635}, \seqnum{A002636}, \seqnum{A007294}, and \seqnum{A087153}.) \bigskip \hrule \bigskip \noindent Received September 13 2003; revised version received May 10 2004. Published in {\it Journal of Integer Sequences} June 8 2004. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}. \end{document}