\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.

\begin{theorem}
Let $n \geq 8$ 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
25 \cdot 3^{m-3} &, & n = 3m+1; \cr
5 \cdot 3^{m-1} &, & n = 3m+2.
} \right . $$ 
\end{theorem}

This sequence has essentially
the same structure and behavior as \seqnum{A000792}, and
the proof follows by the same reasoning, so we do not include it here. The
sequence $(b_n)$  begins as $1,1,3,3,5,9,9,15,27,25,45,81,\ldots$, and after
some initial irregularities falls into the pattern $b_{n+3} = 3b_n$, for 
$n \geq 8$. The sequence is not listed in the {\em On-Line Encyclopedia of
Integer Sequences}.

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.

\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.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in

\end{document}

.