\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \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{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\twolinesum}[2]{\sum_{\substack{{\scriptstyle #1}\\ {\scriptstyle #2}}}} \newcommand{\gmod}[1]{\, ({\rm{mod}} \, #1)} \def\cb {\mathcal{B}} \def\ci {{\cal I}} \def\bfxi {\boldsymbol{\xi}} \def\bfeta {\boldsymbol{\eta}} \begin{center} \vskip 1cm{\LARGE\bf Partitions with Fixed Number of Sizes} \vskip 1cm \large David Christopher\\ Department of Mathematics\\ The American College\\ Madurai\\ Tamil Nadu\\ India\\ \href{mailto:davchrame@yahoo.co.in}{\tt davchrame@yahoo.co.in} \\ \end{center} \vskip .2 in \begin{abstract} Let $t(n,s)$ and $t(n,k,s)$, respectively, be the number of partitions of $n$ with $s$ different sizes, and the number of partitions of $n$ with exactly $k$ parts and $s$ different sizes. In this article, an asymptotic estimate for $t(n,k,s)$ is presented for the following two cases: (i) $s=k-1$ and (ii) when $k$ is a prime number with $s=2$. Further, the enumeration of uniform partitions with exactly 2 sizes is considered and the estimate for its partial sum is derived. Finally, a parity result for $t(n,2)$ is obtained. \end{abstract} \section{Introduction and statement of results} Let $n$ be a positive integer. By a partition of $n$ we mean a finite non-increasing sequence of positive integers $\lambda=(\lambda_1, \lambda_2,\ldots, \lambda_m)$ such that $\lambda_1+\lambda_2+\cdots+\lambda_m=n$. The $\lambda_i$ are called the parts of the partition and each element in the set of parts is called a size of $\lambda$. Let $t(n,s)$ and $t(n,k,s)$, respectively, be the number of partitions of $n$ with $s$ different sizes, and the number of partitions of $n$ with exactly $k$ parts and $s$ different sizes. These two classes of functions are subjects of investigation in the recent past. MacMahon \cite{mac} was the first who considered this kind of partitions. In 2005, Deutsch included the number of partitions of $n$ with exactly two odd sizes (see \seqnum{A117955}) and the number of partitions of $n$ with exactly two sizes, one odd and one even (see \seqnum{A117956}) in the {\it On-Line Encyclopedia of Integer Sequences} (OEIS). Sloane \cite{S1} included the function $t(n,2)$ in the OEIS (see \seqnum{A002133}). Deutsch presented the following generating function of $t(n,2)$ (see \seqnum{A002133}): $$ \sum_{n=1}^{\infty}t(n,2)x^n=\sum_{j=1}^{i-1}\sum_{i=1}^{\infty}\frac{x^{i+j}}{(1-x^i)(1-x^j)}. $$ Andrews \cite{GE} gave the following formula for $t(n,2)$ by means of $q$ series manipulations: $$ t(n,2)=\frac{\sum_{k=1}^{n-1}\tau(k)\tau(n-k)+\tau(n)-\sigma(n)}{2}, $$ where $\tau(n)$ denote the number of positive divisors of $n$ and $\sigma(n)$ denote the sum of the positive divisors of $n$. In 2011, Tani and Bouroubi \cite{tan} found an elegant exact formula for the function $t(n,k,2)$. The purpose of this article is twofold. First, we give an asymptotic estimate for $t(n,k,s)$ for certain cases. \begin{theorem}\label{thm1} We have \begin{equation}\label{est1} t(n,k+1,k)\sim \frac{C_{k-1}}{(k+1)!^{k-1}}n^{k-1}, \end{equation} where $C_{k-1}$ is given by the recurrence relation: \begin{equation}\label{rec2} C_{k-1}=(k-2)!kC_{k-2}(k+1)^{k-2}+k\frac{(k+1)!^{k-2}}{(k-1)!} \end{equation} with $C_1=3$. \end{theorem} \begin{theorem}\label{thm2} For prime $p\geq 3$, we have $$ t(n,p,2)\sim \frac{\sum_{j=1}^{p-1}\frac{(p-1)!}{j}}{p!}n. $$ \end{theorem} The method adopted to arrive at the above estimates is similar to the one used in a recent paper by David Christopher et al. \cite{dav2}. In addition to the estimates above, we consider the uniform partitions with 2 sizes and we derive the estimate for the partial sums of its enumeration function. \begin{definition} A partition $\lambda$ is said to be an {\it uniform partition} (see \cite{dav}) if, the number of occurrences of a size in $\lambda$ is identical with that of all the other sizes in $\lambda$. The enumeration function $U(n,2)$ is defined to be the number of uniform partitions of $n$ with exactly 2 sizes. \end{definition} \begin{theorem}\label{thm3} We have $$ \sum_{m=1}^{n}U(m,2)\sim \frac{\pi^2}{24}n^2. $$ \end{theorem} The next result in this article is a parity expression for $t(n,2)$. \begin{theorem}\label{thm4} Let $n$ be a positive integer. \begin{enumerate} \item If $n \equiv 1\pmod 2$, then we have $$ t(n,2)\equiv \begin{cases} \frac{\tau(n)-1}{2}\pmod 2, & \text{ if $n$ is a square;}\\ \frac{\tau(n)}{2}\pmod 2, & \text{if $n$ is not a square.} \end{cases} $$ \item If $n\equiv 0\pmod 2$ and $\beta$ is the highest power of 2 that divides $n$, then we have $$ t(n,2)\equiv\begin{cases} \frac{(\beta-1)\tau(\frac{n}{2^\beta})-1}{2}\pmod 2, & \text{ if $n$ is a square;}\\ \frac{(\beta-1)\tau(\frac{n}{2^\beta})}{2}\pmod 2, & \text{ if $n$ is not a square.} \end{cases} $$ \end{enumerate} \end{theorem} In the final section, we provide two different proofs for this theorem. \section{Proof of the Estimates} \subsection{Prerequisites} To begin with, we need the following recurrence relation satisfied by $t(n,k,s)$, which has $k-s+2$ preceding terms. Note that, the following recurrence relation is identical to the one given by Tani and Bouroubi \cite{tan}, but it is presented here in a linear form. The method of proof below is bijective whereas the former proof is based upon a simple variation in the system of equations that admits partitions with fixed number of sizes as its solution. \begin{lemma} [Tani and Bouroubi \cite{tan}] \label{lem1} We have $$ t(n,k,s)=t(n-k,k,s)+\sum_{r=1}^{k-s+1}t(n-k,k-r,s-1). $$ \end{lemma} \begin{proof} Let $(\lambda_1,\lambda_2,\ldots,\lambda_k)$ be a partition of $n$ with exactly $k$ parts and $s$ different sizes. \bigskip \noindent Case (i): Assume that $\lambda_k>1$. Consider the mapping $$ (\lambda_1,\lambda_2,\ldots,\lambda_k)\to (\lambda_1-1,\lambda_2-1,\ldots ,\lambda_k-1); $$ this mapping establishes an one-to-one correspondence between the following sets: \begin{itemize} \item The set of all partitions of $n$ with exactly $k$ parts, $s$ different sizes and least part $a_k>1$. \item The set of all partitions of $n-k$ with exactly $k$ parts and $s$ different sizes. \end{itemize} We observe that the cardinality of the latter set is $t(n-k,k,s)$. \bigskip \noindent Case (ii): Assume that $\lambda_k=\lambda_{k-1}=\cdots =\lambda_{k-(r-1)}=1$ and $\lambda_{k-r}>1$ for some positive integer $r\geq 1$. We see that the mapping $$ (\lambda_1,\lambda_2,\ldots ,\lambda_k)\to (\lambda_1-1,\lambda_2-1,\ldots ,\lambda_{k-r}-1) $$ establishes an one-to-one correspondence between the following sets: \begin{itemize} \item The set of all partitions of $n$ with exactly $k$ parts, $s$ different sizes and $\lambda_{k}=\lambda_{k-1}=\cdots =\lambda_{k-(r-1)}=1$ and $\lambda_{k-r}>1$. \item The set of all partitions of $n-k$ with exactly $k-r$ parts and $s-1$ different sizes. \end{itemize} Notice that the cardinality of the latter set is $t(n-k,k-r,s-1)$. Since $r$ varies from $1$ to $k-s+1$, the result follows. \end{proof} \begin{definition} Let $n$ and $k$ be two positive integers with $n\geq\frac{k(k+1)}{2}$ . The enumeration function $q(n,k)$ is defined to be the number of partitions of $n$ with $k$ distinct parts. \end{definition} The following result is required in the proof of Theorem \ref{thm1}. \begin{lemma}[David Christopher and Davamani Christober \cite{dav1}]\label{lem2} Let $k\geq 2$ be a positive integer. For each $ r\in\left\{0,1,\ldots,k!-1\right\}$, the function $q(k!l+r,k)$ is a polynomial in $l$ of degree $k-1$ with the leading coefficient $\frac{k!^{k-2}}{(k-1)!}$. \end{lemma} \subsection{Proof of Theorem \ref{thm1}} Wielding Lemma \ref{lem1} and Lemma \ref{lem2} we will prove the following statements: \begin{enumerate} \item The function $t((k+1)!l+r,k+1,k)$ is a polynomial in $l$ of degree $k-1$ for each $r\in\left\{0,1,\ldots,(k+1)!-1\right\}$. \item The leading coefficient of $t((k+1)!l+r,k+1,k)$, denoted $C_{k-1}$, satisfies the recurrence relation (\ref{rec2}). \end{enumerate} From these statements one can get the following limit: $$ \lim_{l\to \infty}\frac{t((k+1)!l+r,k+1,k)}{\left((k+1)!l+r\right)^{k-1}}=\frac{C_{k-1}}{(k+1)!^{k-1}} $$ for each $r\in\left\{0,1,\ldots,(k+1)!-1\right\}$; which is equivalent to the estimate (\ref{est1}). Now we prove the statements above simultaneously by induction over $k$. We observe that: $t(n,k,k)=q(n,k)$. Put $k=3$ and $s=2$ in Lemma \ref{lem1} to get \begin{align*} t(n,3,2)-t(n-3,3,2) & =t(n-3,2,1)+q(n-3,1)\\ & = \begin{cases} 2, & \text{ if $n\equiv 3\pmod 2$;}\\ 1, & \text{otherwise}. \end{cases} \end{align*} Put $n=3!l+r$ with $0\leq r\leq 3!-1$, where $l$ is a non-negative integer. Then we have \[t(3!l+r,3,2)-t(3!l+r-3,3,2)= \begin{cases} 2, & \text{if $r\equiv1\pmod 2$;}\\ 1, &\text{if $r\equiv 0\pmod 2$,} \end{cases} \] and \[t(3!l+r-3,3,2)-t(3!l+r-6,3,2)= \begin{cases} 2, & \text{if $r\equiv 0\pmod 2$;}\\ 1, & \text{if $r\equiv1\pmod 2$.} \end{cases} \] The sum of the above two expressions can be put as $t(3!l+r,3,2)-t(3!(l-1)+r,3,2)=3 $ for each $ r\in\left\{0,1,\ldots, 3!-1\right\}$. Then substituting $2,3,\ldots ,l$ in place of $l$ gives $t(3!l+r,3,2)=3(l-1)+t(r,3,2) $ for each $ r\in\left\{0,1,\ldots, 3!-1\right\}$. Thus, the statements above hold for $k=2$. Assume that the assertion is true up to some $k\geq 2$. Set $k+1$ as the number of parts, $k$ as the number of sizes and $n=(k+1)!l+r$, where $l$ is a non-negative integer and $r\in\left\{0,1,\ldots,(k+1)!-1\right\}$. Then applying Lemma \ref{lem1} $k!$ times, we get \begin{align*} t((k+1)!l+r,k+1,k)&-t((k+1)!(l-1)+r,k+1,k)& \\ &=\sum_{i=1}^{k!}t((k+1)!l+r-i(k+1),k,k-1)\\ &+\sum_{i=1}^{k!}q((k+1)!l+r-i(k+1),k-1). \end{align*} In view of the division algorithm one can obtain unique pair of integers say $(r_i,q_i)$ for each $i\in\left\{1,2,\ldots,k!\right\}$ satisfying the equality $k!q_i+r_i=r-i(k+1)$ with $0\leq r_i\leq k!-1$. Similarly one can get unique pair of integers say $(r_i',q_i')$ for each $i\in\left\{1,2,\ldots,k!\right\}$ satisfying the equality $(k-1)!q_i'+r_i'=r-i(k+1)$ with $0\leq r_i'\leq (k-1)!-1$. Consequently, the right side of the above equality can be written as \begin{equation}\label{thmeqn1} \sum_{i=1}^{k!}t(k!((k+1)l+q_i)+r_i,k,k-1)+\sum_{i=`1}^{k!}q\left((k-1)!\left(\frac{(k+1)!}{(k-1)!}l+q_i'\right)+r_i',k-1\right). \end{equation} Put $l_i=(k+1)l+q_i$. By induction assumption, the function $t(k!l_i+r_i,k,k-1)$ is a polynomial in $l_i$ of degree $k-2$ with the leading coefficient $C_{k-2}$ as given in the recurrence relation (\ref{rec2}) for each $r_i\in\left\{0,1,\ldots ,k!-1\right\}$ and $i\in\left\{1,2,\ldots,k!\right\}$. Just assuming this polynomial representation, we see that the first summation in (\ref{thmeqn1}) is a sum of $k!$ polynomials in $l$, each of which is of degree $k-2$ with the leading coefficient $C_{k-2}(k+1)^{k-2}$. (At this juncture, we note that $(k+1)l+q_i$ may be negative for some initial values of $l$. In such instances, we assume the extrapolation of the function $t(k!l_i+r_i,k,k-1)$ as a polynomial in $l_i$ and not as an enumeration function.) Thus, the first summation in (\ref{thmeqn1}) is itself a polynomial in $l$ of degree $k-2$ with the leading coefficient $k!C_{k-2}(k+1)^{k-2}$. Put $l_i'=\frac{(k+1)!}{(k-1)!}l+q_i'$. From Lemma \ref{lem2} it follows that $q((k-1)!l'_i+r_i',k-1)$ is a polynomial in $l'_i$ of degree $k-2$ for each $r_i'\in\left\{0,1,\ldots,(k-1)!-1\right\}$ and $i\in\left\{1,2,\ldots,k!\right\}$. Consequently, the second summation in (\ref{thmeqn1}) is itself a polynomial in $l$ of degree $k-2$ with the leading coefficient $k!\frac{(k-1)!^{k-3}}{(k-2)!}\frac{(k+1)!^{k-2}}{(k-1)!^{k-2}}$. Thus, the summation term in (\ref{thmeqn1}) is a polynomial in $l$ of degree $k-2$ with the leading coefficient $k!C_{k-2}(k+1)^{k-2}+k!\frac{(k-1)!^{k-3}}{(k-2)!}\frac{(k+1)!^{k-2}}{(k-1)!^{k-2}}$. Accordingly, $t((k+1)!l+r,k+1,k)-t((k+1)!(l-1)+r,k+1,k)$ is a polynomial in $l$ of degree $k-2$. Put $f(l)=t((k+1)!l+r,k+1,k)-t((k+1)!(l-1)+r,k+1,k)$. Substituting the values $1,2,\ldots,l$ in place of $l$ and adding we get $t((k+1)!l+r,k+1,k)=\sum_{i=1}^{l}f(i)-t(r,k+1,k)$. This equality implies that $t((k+1)!l+r,k+1,k)$ is a polynomial in $l$ of degree $k-1$. If one denotes the leading coefficient of $t((k+1)!l+r,k+1,k)$ by $C_{k-1}$, then from the conclusions above we get $$ (k-1)C_{k-1}=k!C_{k-2}(k+1)^{k-2}+k!\frac{(k-1)!^{k-3}}{(k-2)!}\frac{(k+1)!^{k-2}}{(k-1)!^{k-2}}. $$ This simplifies to the recurrence relation (\ref{rec2}). The proof is now completed. \begin{corollary} From the recurrence relation of $C_n$ given in the Theorem \ref{thm1} we get $$ C_1=3, C_2=72, C_3=24000, C_4=233280000,\ldots $$ From these values of $C_i$, we have the following estimates: \begin{align*} &t(n,3,2)\sim\frac{1}{2}n;\\ &t(n,4,3)\sim \frac{1}{8}n^2;\\ &t(n,5,4)\sim \frac{1}{72}n^3;\\ &t(n,6,5)\sim \frac{1}{1152}n^4 . \end{align*} \end{corollary} \subsection{Proof of Theorem \ref{thm2}} Let $p$ be a prime number. Then from Lemma \ref{lem1} it follows that $$ t(n,p,2)-t(n-p,p,2)=\sum_{j=1}^{p-1}t(n-p,j,1). $$ Put $n=p!l+r$ (where $l$ is a positive integer and $0\leq r\leq p!-1$) and apply Lemma \ref{lem1} $(p-1)!$ times in the above relation to get \begin{equation}\label{thmeqn2} t(p!l+r,p,2)-t(p!(l-1)+r,p,2)=\sum_{j=1}^{p-1}\sum_{i=1}^{(p-1)!}t(p!l+r-pi,j,1). \end{equation} Notice that $$ t(p!l+r-pi,j,1)=\begin{cases} 1, & \text{if $pi\equiv r\pmod j$;}\\ 0, & \text{otherwise,} \end{cases} $$ and the congruence equation $$\text{ $px\equiv r\pmod j$} $$ has unique solution modulo $j$ for each $j\in\left\{1,2,\ldots,p-1\right\}$. Consequently, we get the right side of (\ref{thmeqn2}) as $\sum_{j=1}^{p-1}\frac{(p-1)!}{j}$. Then replacing $l$ by $1,2,\ldots ,l$ in (\ref{thmeqn2}) and adding gives $$ t(p!l+r,p,2)=t(r,p,2)+\left(\sum_{j=1}^{p-1}\frac{(p-1)!}{j}\right)l $$ for each $r\in\left\{0,1,\ldots, p!-1\right\}$. This implies that $$ \lim _{l\to\infty}\frac{t(p!l+r,p,2)}{p!l+r}=\frac{\sum_{j=1}^{p-1}\frac{(p-1)!}{j}}{p!} $$ for each $r\in\left\{0,1,\ldots, p!-1\right\}$. Equivalently, $$ t(n,p,2)\sim \frac{\sum_{j=1}^{p-1}\frac{(p-1)!}{j}}{p!}n; $$ this is the contention of the Theorem \ref{thm2}. \begin{remark} At this juncture, we remark that, the method adopted so far to derive asymptotic estimates may turn futile for some other cases. For instance, from the exact expression for the function $t(n,4,2)$ given in \cite{tan} one can get the following values: \begin{enumerate} \item $t(12l+4,4,2)=7l$ for every non-negative integer $l$. \item $t(12l+5,4,2)=4l+1$ for every non-negative integer $l$. \end{enumerate} This leads to the conclusion that $$ t(n,4,2)\nsim Kn $$ for every real number $K$. \end{remark} \subsection{Proof of Theorem \ref{thm3}} Recall that the function $U(n,2)$ is the number of uniform partitions of $n$ with exactly 2 sizes. We have \begin{align*} U(n,2)&=\sum_{d|n}q\left(d,2\right)\\ &=\sum_{d|n} \left\lfloor\frac{d-1}{2}\right\rfloor\\ & \leq\sum_{d|n}\frac{d-1}{2}\\ &=\frac{1}{2}\left(\sigma(n)-\tau(n)\right). \end{align*} On the other hand, we have \begin{align*} U(n,2)&=\sum_{d|n}q\left(d,2\right)\\ &=\sum_{d|n} \left\lfloor\frac{d-1}{2}\right\rfloor\\ & \geq\sum_{d|n}\frac{d-2}{2}\\ &=\frac{1}{2}\left(\sigma(n)-2\tau(n)\right). \end{align*} Consequently, we have \begin{equation}\label{peqn2} \frac{1}{2}\left(\sum_{m=1}^{n}\sigma(m)-2\sum_{m=1}^{n}\tau(m)\right) \leq \sum_{m=1}^{n}U(m,2)\leq \frac{1}{2}\left( \sum_{m=1}^{n}\sigma(m)- \sum_{m=1}^{n}\tau(m)\right). \end{equation} Since \begin{equation}\label{lim1} \lim_{n\to\infty}\frac{\sum_{m=1}^{n}\sigma(m)}{\frac{\pi^2}{12}n^2}=1 \end{equation} and \begin{equation}\label{lim2} \lim_{n\to\infty}\frac{\sum_{m=1}^{n}\tau(m)}{n\log{n}}=1, \end{equation} dividing the inequality (\ref{peqn2}) by $\frac{\pi^2}{12}n^2$ and letting $n\to \infty$ gives $$ \lim_{n\to\infty}\frac{\sum_{m=1}^{n}U(m,2)}{\frac{\pi^2}{12}n^2}=\frac{1}{2}, $$ which is equivalent to the estimate given in Theorem \ref{thm3}. (The validity of the limits (\ref{lim1}) and (\ref{lim2}) can be seen in \cite[p.\ 57--60]{TA}.) \section{Two proofs of Theorem 5} In this section, we adopt the following notation: if $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_k)$ is a partition of $n$ and $\left\{a_1,a_2,\ldots\right\}$ is the set of all sizes of $\lambda$ with $a_1>a_2>\cdots$, then we denote $\lambda=\left(a_1^{f_1}a_2^{f_2}\cdots\right)$ when the size $a_i$ occurs exactly $f_i$ number of times in $\lambda$. Let $P_2^n$ denote the set of all partitions of $n$ with exactly two sizes. \subsection{A proof using Jacobi's formula} \begin{proof} Let $\lambda=\left(a_1^{f_1}a_2^{f_2}\right)\in P_2^n$. Then we have $a_1f_1+a_2f_2=n$ with $a_1>a_2$. \bigskip \noindent Case (i): $f_1=f_2$. In this case we have $n=f_1a_1+f_2a_2=f(a_1+a_2)$, where $f_1=f_2=f$ (say). Clearly, $f|n$ and the enumeration of the ordered pairs $(a_1,a_2)$ satisfying the equality is $q\left(\frac{n}{f},2\right)$. Thus, the number of partitions belonging to this case is $\sum_{f|n}q\left(\frac{n}{f},2\right)$. \bigskip \noindent Case (ii): $f_1=a_1$ and $f_2=a_2$. We see that the number of partitions belonging to this case equals the number of ways that $n$ can be written as the sum of two distinct nonzero squares; we denote this enumeration by $R_2(n)$. \bigskip \noindent Case (iii): Assume that $f_1\neq f_2$ with either $a_1\neq f_1$ or $a_2\neq f_2$, and either $f_1\neq a_2$ or $f_2\neq a_1$. In this case, consider the mapping $$ T((a_1^{f_1}a_2^{f_2}))= \begin{cases} (f_1^{a_1}f_2^{a_2}), & \text{ if $ f_2