\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,amssymb,amsthm} \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}}} %\usepackage{epsfig,amsfonts} %\hbadness=190 % ni tako natancen pri novi vrstici %\tolerance=1000 % malo sprosti kriterij za hbadness %\textheight 23cm %\textwidth 17cm %\hoffset -2cm %\voffset -2cm %\parindent=0mm % ni zoba pri novem odstavku %\parskip 6mm % pri odstavku skoci 6mm %\newcommand{\bi}[1]{\hbox{\boldmath{$#1$}}} %\renewcommand{\baselinestretch}{1.5} % 1.5 kratni razmak %\catcode`\"=13 % aktivira znak " %\def"#1{\v{#1}} % sedaj je "c lahko \v{c} %\def\r#1{(\ref{#1})} %\def\be{\begin{equation}} %\def\ee{\end{equation}} %\def\bea{\begin{eqnarray}} %\def\eea{\end{eqnarray}} %\def\bra#1{ \langle #1 |} %\def\ket#1{|#1\rangle} %\def\braket#1{\langle #1 \rangle} %\def\p#1{#1^{ \prime}} %\def\pp#1{#1^{ \prime \prime}} %\def\ppp#1 {#1^{\prime \prime \prime}} %\def\cminv{cm$^{-1}\,$} %\def\comment#1{ \vspace{0.5cm} {\tt #1} \linebreak \vspace{0.5cm} } %\def\hfl#1#2{\smash{\mathop{\hbox to 12 mm{\rightarrowfill}} \limits^{\scriptstyle #1}_{\scriptstyle #2}}} %\def\vfl#1#2{\llap{$\scriptstyle #1$}\left\downarrow\vbox to 6mm{}\right.\rlap{$\scriptstyle #2$}} \def\diagram#1{\def\normalbaselines{\baselineskip=0pt \lineskip=10pt\lineskiplimit=1pt} \matrix{#1}} \def\binom#1#2{\left ( {{#1} \atop {#2}} \right )} \def\eqalign#1{\null\,\vcenter{\openup\jot\moth \ialign{\strut\hfill$\displaystyle{##}$& $\displaystyle{{}##}$\hfill\crcr #1\crcr}}\,} %\newcommand {\qed} {\null \hfill \rule {2.5mm}{2.5mm}} \newcommand {\R} {\ensuremath{\mathbb{R}}} \newcommand {\N} {\ensuremath{\mathbb{N}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Maximum Product Over Partitions \\ \vskip .1in Into Distinct Parts} \vskip 1cm \large Tomislav Do\v{s}li\'c \\ Faculty of Agriculture \\ University of Zagreb \\ Sveto\v{s}imunska 25 \\ 10000 Zagreb \\ Croatia\\ \href{mailto:doslic@agr.hr}{\tt doslic@agr.hr} \\ \end{center} \vskip .2 in \begin{abstract} We establish an explicit formula for the maximum value of the product of parts for partitions of a positive integer into distinct parts (sequence \seqnum{A034893} in the {\em On-Line Encyclopedia of Integer Sequences}). \end{abstract} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}{Proposition}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{lemma}{Lemma}[section] \section{Introduction} If you have ever been interested in recreational mathematics, it is very likely that you came across a variant of the following problem: What is the maximum possible value of the product of positive integers whose sum is equal to $S$? If the problem appears on some competition, the positive integer $S$ is usually set to the value of the year in which the competition takes place \cite{scholes1,scholes2}. One could safely say that the problem belongs to the standard repertoire of problem collections \cite{halmos,larson,newman,greitzer} and problem sections in mathematical magazines \cite{barwell,beevers}. The sequence of the maximum values of products of positive integers whose sum is equal to $n$ appears as \seqnum{A000792} in the {\em On-Line Encyclopedia of Integer Sequences} \cite{sloane}. It appears to be well researched; along with many comments and references, one can find there the generating function and the explicit formula for the $n$-th term of the sequence, and the associated keywords are ``nonn, easy, nice''. The present paper is concerned with a variant of the problem that requires all integers in the sum to be distinct. Although very similar to the original problem, it has attracted much less attention, both in the problem-oriented literature and in the {\em On-Line Encyclopedia of Integer Sequences}. Sure enough, an entry containing first 45 terms of the sequence appears as \seqnum{A034893} in the {\em Encyclopedia}, but there are no comments, no formulas, and no references. Moreover, the word ``easy'' does not appear in the list of keywords for that sequence. Hence, it seemed worthwhile to invest some effort in finding an explicit formula for the $n$-th term of the sequence. An inspection of initial terms revealed that the factorials appear on positions indexed (almost) by the triangular numbers, and from that observation it was not difficult, by a bit of reverse-engineering, to guess an explicit formula. The formal proof of this result is presented in the rest of this paper. \section{Definitions and preliminary observations} In this section we introduce the combinatorial concepts relevant for our problem and lay the groundwork for our main result. We follow the terminology of \cite{stanley1}. Let $n$ be a positive integer. A {\it partition} of $n$ is a sequence $\lambda = (\lambda _1, \ldots , \lambda _k) \in \N ^k$ such that $\sum _i \lambda _i = n$ and $\lambda _1 \geq \ldots \geq \lambda _k > 0$. Positive integers $\lambda _1, \ldots ,\lambda _k$ are {\it parts}, and $k$ is the {\it length} of the partition. If all inequalities between the parts are strict, we have a partition of $n$ into {\it distinct parts}. Hence, a partition of $n$ into distinct part is a way of writing $n$ as a sum of distinct positive integers, disregarding the order of the summands. If the order of the summands is relevant, instead of partitions we have compositions, and if we allow some summands to be zero, we get weak compositions. More formally, a {\it weak composition} of $n$ into $k$ parts is an ordered $k$-tuple $\mu = (\mu _1, \ldots , \mu _k)$ such that $\sum _{i=1}^k \mu _i = n$ and $\mu _i \geq 0$, $i = 1, \ldots , k$. Our problem can be now cast in the terms of partitions: For a given positive integer $n$, what is the maximum value of the product of parts over all partitions of $n$ into distinct parts? A moment's reflection will show that a partition maximizing the product cannot contain $1$ as a part. It follows from the relation $p \cdot 1 < p + 1$, valid for all positive integers $p$. Another observation, $p+q < pq$, valid for all $2 \leq p < q$, implies that a longer partition is preferred over a shorter one. Hence, the product of parts will be maximized by long partitions that do not contain $1$ as a part. The following result will be helpful in discriminating among all such partitions. \begin{lemma} Let $a$ and $l$ be positive integers greater than one, and let $\mu $ be a weak partition of $l$ into $l$ parts such that all numbers $(a+i-1+\mu _i)$ are distinct, where $1 \leq i \leq l$. Then $$ \prod _{i=1}^l (a+i-1+\mu _i) \leq \prod _{i=1}^l (a+i).$$ \end{lemma} \begin{proof} We will show that no product of the type $ \prod _{i=1}^l (a+i-1+\mu _i)$ whose greatest term exceeds $a+l$ can be maximal. So, let us consider a product $ \prod _{i=1}^l (a+i-1+\mu _i)$ with the greatest term $a+l+p$, where $p \geq 1$. It is clear that the elements in this product cannot be consecutive, for if they were, it would imply that all terms of the product $\prod _{i=1}^l (a+i-1)$ were augmented by $p+1$. Then the total sum of the increments would exceed $l$, a contradiction. Hence, the terms in the product $ \prod _{i=1}^l (a+i-1+\mu _i)$ are not consecutive. Let us suppose that only one number is skipped over, and denote this number by $s$. Then the smallest term in the product must be $a+p$. By summing all terms, we get $S_\mu = (l+1)a + (l+1)p + \binom {l+1}{2} -s$. On the other hand, the sum of all terms in $\prod _{i=1}^l (a+i-1)$ is given by $S = la + \binom {l}{2}$. But these two sums are related by $S_\mu = S + l$, and this condition implies $a+(l+1)p-s = 0$, i.e., $s = a+p(l+1)$. For $p > 1$ we get a contradiction, since already $s=a+2l+2$ is beyond the range of values that can be obtained from the terms of $\prod _{i=1}^l (a+i-1)$ by adding a quantity that does not exceed $l$. For $p = 1$, we get $s = a+l+1$ as the number that is skipped over. But the same number is the greatest term in the product, again a contradiction. Hence, there are at least two numbers missing in the sequence of terms of the product $ \prod _{i=1}^l (a+i-1+\mu _i)$. Let $a+q$ be the smallest and $a+r$ the greatest missing number. By replacing $(a+q-1)(a+r+1)$ by $(a+q)(a+r)$ we get another product of distinct terms, and its value is greater than the value of the product we started from. Hence, the maximum value cannot be attained by the product whose greatest term exceeds $a+l$, and the claim of the lemma follows. \end{proof} Before we state and prove our main result, we need another observation. It is concerned with the sequence of {\it triangular numbers} $T_m = \binom {m+1}{2}$. This is one of the most ancient and the best researched sequences, and we refer the reader to entry \seqnum{A000217} in the {\em On-Line Encyclopedia of Integer Sequences} and to the references therein for more information. We will need the following property of triangular numbers. \begin{lemma} Let $n > 1$ be a positive integer. Then there are unique positive integers $m$ and $l$ such that $n = T_m + l$. \end{lemma} \begin{proof} By starting from the formula $T_m = \binom {m+1}{2}$ one easily obtains $m = \left \lfloor \frac{\sqrt{8n+1}-1}{2} \right \rfloor$ as the greatest positive integer such that $T_m \leq n$. Now $l$ is uniquely determined by $l = n - \binom {m+1}{2}$, and the claim of the lemma follows. \end{proof} \section{The main result} \begin{theorem} Let $n \geq 2$ be a positive integer, and let $m,l \in \N$ be such that $n = T_m + l$, where $T_m$ denotes the $m$-th triangular number. Then the maximum value $a_n$ of the product of parts of a partition of $n$ into distinct parts is given by $$a_n = a_{T_m+l} = \left \{ \matrix{ \frac{(m+1)!}{m-l} & , & 0 \leq l \leq m-2; \cr \hfill \frac{m+2}{2} m! & , & \hfill l = m-1; \cr \hfill (m+1)! & , & \hfill l = m . } \right . $$ \end{theorem} \begin{proof} The case $l = m$ is the simplest, and we treat it first. The longest partition of such an $n$ into almost distinct parts is given by $n = 1+2+ \ldots + m + m$. The product of the parts will increase if this is written as $n = 2+ \ldots + m + (m+1)$, and no other partition into distinct parts yields a greater product, since $pq > p+q$ for all integers $p,q > 1$. Let us now consider the case $n = T_m + l$ for $0 \leq l \leq m-2$. We start from the partition $n = 1 + 2 + \ldots +m + l$. There is no point in keeping the part $1$ in the partition, so we add it to the part $m$, thus obtaining the partition $n = 2+3+ \ldots + l + l + \ldots + (m-1) + (m+1)$. This is not a partition into distinct parts; in order to get one, we must somehow split one of two copies of the part $l$ and distribute the fragments among the remaining parts in such a way that the new partition contains only distinct parts. If any of the fragments is added to a part $k$, where $0 \leq k \leq m-l-1$, this will result in a partition with repeated parts, since the new part will not exceed $m-1$, and all integers between $m-l$ and $m-1$ are already in the partition. Hence, we must look for the optimal way of distributing the fragments among the $l$ consecutive integers $m-l, \ldots , m-1$, and this is exactly the situation of Lemma 1. The simplest way is to add $1$ to each of those $l$ integers, thus obtaining the partition $n = 2+ \ldots + (m-l-1) + (m-l+1) + \ldots + (m-1) + m + (m+1)$. The product of parts is given by $\frac{(m+1)!}{m-l}$, and the case $0 \leq l \leq m-2$ is settled. The remaining case $l = m-1$ follows much along the same lines. By starting from $n = 1 + \ldots + m + (m-1)$, by splitting $m-1$ into $1$'s and by adding the ones to the parts $2, \ldots , m$, we obtain the partition $n = 1 + 3 + \ldots + m + (m+1)$. The claim now follows by splicing the part $1$ to the part $m+1$, thus obtaining the maximizing partition $n = 3+ \ldots + m + (m+2)$. \end{proof} Hence, we have established an explicit formula for the $n$-th term of sequence \seqnum{A034893}. \section{Concluding remarks} Among the best known results concerning the partitions of integers is certainly the famous Euler's theorem stating that there are equally many partitions of a positive integer into distinct parts and into odd parts \cite{stanley1}. Hence, it is proper here to consider the maximum possible value of the product of parts over all partitions of a positive integer into odd parts. The sequence of maximum possible values appears as \seqnum{A091916} in the OEIS. \begin{theorem} Let $n \geq 3$ be a positive integer. The maximum value $b_n$ of the product of the parts in a partition of $n$ into odd parts is given by $$b_n = \left \{ \matrix{ 3^m &, & n = 3m; \cr 3^m &, & n = 3m+1; \cr 5 \cdot 3^{m-1} &, & n = 3m+2. } \right . $$ \end{theorem} The proof relies on the well known fact that the maximum product over all partitions is achieved when all parts are equal to $3$, except, maybe, one or two 2's. More precisely, for $n=3m$ the maximum value is equal to $3^m$, for $n=3m+1$ it is $2^2\cdot 3^{m-1}$, and for $n=3m+2$ it is $2 \cdot 3^m$ \cite{beevers}. For the case $n=3m$, all parts are already odd. In the case $n=3m+1$, converting the parts $(3,3,2,2)$ into $(3,3,3,1)$, so that all parts become odd, will result in the greatest possible value of the product, while in the case $n=3m+2$ it suffices to convert the parts $(3,2)$ into the part $5$. Taking this into account, one can easily establish explicit formulas and the conjecture $b_{n+3}=3b_n$ for the sequence \seqnum{A091916} in the OEIS. Another sequence considered here, that is not in the {\em On-Line Encyclopedia}, is the sequence counting the weak compositions of $n$ into $n$ parts that appeared in Lemma 1. The sequence is defined as the number of weak compositions $\mu $ of a positive integer $n$ into $n$ parts such that $\mu _{i+j} - \mu _i \neq j$, for all $i, j = 1, \ldots , n-1$. The first few terms are $1,3,7,17, 37,85,181,399,841,1805,3757,7933$. It might be interesting to investigate the properties of this sequence in more detail. \section{Acknowledgments} The support of the Ministry of Science, Education, and Sport of the Republic of Croatia via Grant 0037-117 is gratefully acknowledged. I am indebted to Professor James A. Sellers of Penn State University for bringing to my attention a mistake in formulation of Theorem 4.1. \begin{thebibliography}{10} \bibitem{barwell} B. R. Barwell, \newblock Cutting string and arranging counters, \newblock {\em J. Rec. Math.} {\bf 4} (1971), 1664--168. \bibitem{beevers} B. S. Beevers, \newblock The greatest product, \newblock {\em Math. Gazette} {\bf 77} (1993) 91. \bibitem{greitzer} S. L. Greitzer, \newblock {\em International Mathematical Olympiads 1959--1977}, \newblock MAA, Washington, 1978. \bibitem{halmos} P. R. Halmos, \newblock {\em Problems for Mathematicians Young and Old}, \newblock MAA, Washington, 1991. \bibitem{larson} L. C. Larson, \newblock {\em Problem-Solving Through Problems}, \newblock Springer Verlag, Berlin, 1983. \bibitem{newman} D. J. Newman, \newblock {\em A Problem Seminar}, \newblock Springer Verlag, Berlin, 1982. \bibitem{scholes1} J. Scholes, \newblock 18th IMO 1976, Problem 4, \newblock available electronically at \href{http://http://www.kalva.demon.co.uk/imo/isoln/isol764.html}{\tt http://http://www.kalva.demon.co.uk/imo/isoln/isol764.html}. \bibitem{scholes2} J. Scholes, \newblock 40th Putnam 1979 Problem A1, \newblock available electronically at \href{http://www.kalva.demon.co.uk/putnam/psoln/psol791.html}{\tt http://www.kalva.demon.co.uk/putnam/psoln/psol791.html}. \bibitem{sloane} N. J. A. Sloane, \newblock {\em On-Line Encyclopedia of Integer Sequences}, \newblock available electronically at \href{http://www.research.att.com/$\sim$njas/sequences/index.html}{\tt http://www.research.att.com/$\sim$njas/sequences/index.html}. \bibitem{stanley1} R. P. Stanley, \newblock {\em Enumerative Combinatorics}, Vol. 1, \newblock Wadsworth, Monterey, 1986. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A17; Secondary: 05A10, 05A15 \noindent \emph{Keywords: } partition of an integer, partition into distinct parts, partition into odd parts \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000217}, \seqnum{A000792}, and \seqnum{A034893}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received November 3 2005; revised version received November 9 2005. Published in {\it Journal of Integer Sequences}, November 14 2005. Revised version (correcting Theorem 4.1), January 22 2007. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}