Maximum Product Over Partitions Into Distinct Parts

Tomislav Došlić Faculty of Agriculture University of Zagreb Svetošimunska 25 10000 Zagreb Croatia

                         doslic@agr.hr

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 \underline{A034893} in the On-Line Encyclopedia of Integer Sequences).

1 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 [7, 8]. One could safely say that the problem belongs to the standard repertoire of problem collections [4, 5, 6, 3] and problem sections in mathematical magazines [1, 2]. The sequence of the maximum values of products of positive integers whose sum is equal to n appears as \underline{A000792} in the On-Line Encyclopedia of Integer Sequences [9]. 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 On-Line Encyclopedia of Integer Sequences. Sure enough, an entry containing first 45 terms of the sequence appears as \underline{A034893} in the 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.

2 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 [10].

Let n be a positive integer. A partition of n is a sequence λ = (λ_{1}, …, λ_{k}) ∈ ℕ^{k} such that ∑_{i} λ_{i} = n and λ_{1} ≥ … ≥ λ_{k} > 0. Positive integers λ_{1}, …, λ_{k} are parts, and k is the length of the partition. If all inequalities between the parts are strict, we have a partition of n into 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 weak composition of n into k parts is an ordered k-tuple μ = (μ_{1}, …, μ_{k}) such that ∑_{i=1}^{k} μ_{i} = n and μ_{i} ≥ 0, i = 1, …, 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·1 < p+1, valid for all positive integers p. Another observation, p + q < pq, valid for all 2 ≤ 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.

Lemma 2.1. Let a and l be positive integers greater than one, and let μ be a weak partition of l into l parts such that all numbers (a + i − 1 + μ_{i}) are distinct, where 1 ≤ i ≤ l. Then

∏_{i=1}^{l}(a + i − 1 + μ_{i}) ≤ ∏_{i=1}^{l}(a + i).

Proof. We will show that no product of the type ∏_{i=1}^{l}(a + i − 1 + μ_{i}) whose greatest term exceeds a + l can be maximal. So, let us consider a product ∏_{i=1}^{l}(a + i − 1 + μ_{i}) with the greatest term a + l + p, where p ≥ 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 ∏_{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 ∏_{i=1}^{l}(a+i−1+μ_{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_{μ} = (l +1)a+(l +1)p+\binom{l+1}{2}−s. On the other hand, the sum of all terms in ∏_{i=1}^{l}(a + i − 1) is given by S = la + \binom{l}{2}. But these two sums are related by S_{μ} = 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 ∏_{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 ∏_{i=1}^{l}(a + i − 1 + μ_{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.

Before we state and prove our main result, we need another observation. It is concerned with the sequence of 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 \underline{A000217} in the On-Line Encyclopedia of Integer Sequences and to the references therein for more information. We will need the following property of triangular numbers.

Lemma 2.2. Let n > 1 be a positive integer. Then there are unique positive integers m and l such that n = T_{m} + l.

Proof. By starting from the formula T_{m} = \binom{m+1}{2} one easily obtains m = ⌊\frac{\sqrt{8n+1}−1}{2}⌋ as the

greatest positive integer such that T_{m} ≤ n. Now l is uniquely determined by l = n − \binom{m+1}{2}, and the claim of the lemma follows.

3 The main result

Theorem 3.1. Let n ≥ 2 be a positive integer, and let m, l ∈ ℕ 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} = \{ \begin{matrix}\frac{(m+1)!}{m−l} & , & 0 ≤ l ≤ m − 2; \\ \frac{m+2}{2}m! & , & l = m − 1; \\ (m + 1)! & , & l = m. \end{matrix}

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 + … + m + m. The product of the parts will increase if this is written as n = 2 + … + 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 ≤ l ≤ m − 2. We start from the partition n = 1 + 2 + … + 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 + … + l + l + … + (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 ≤ k ≤ 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, …, 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 + … + (m − l − 1) + (m − l + 1) + … + (m − 1) + m + (m + 1). The product of parts is given by \frac{(m+1)!}{m−l}, and the case 0 ≤ l ≤ m − 2 is settled.

The remaining case l = m − 1 follows much along the same lines. By starting from n = 1 + … + m + (m − 1), by splitting m − 1 into 1’s and by adding the ones to the parts 2, …, m, we obtain the partition n = 1 + 3 + … + m + (m + 1). The claim now follows by splicing the part 1 to the part m + 1, thus obtaining the maximizing partition n = 3 + … + m + (m + 2).

Hence, we have established an explicit formula for the n-th term of sequence \underline{A034893}.

4 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 [10]. 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.

Theorem 4.1. Let n ≥ 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} = \{ \begin{matrix}3^{m} & , & n = 3m; \\ 25 · 3^{m−3} & , & n = 3m + 1; \\ 5 · 3^{m−1} & , & n = 3m + 2. \end{matrix}

This sequence has essentially the same structure and behavior as \underline{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, …, and after some initial irregularities falls into the pattern b_{n+3} = 3b_{n}, for n ≥ 8. The sequence is not listed in the On-Line Encyclopedia of Integer Sequences.

Another sequence considered here that is not in the 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 μ of a positive integer n into n parts such that μ_{i+j} − μ_{i} ≠ j, for all i, j = 1, …, 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.

5 Acknowledgments

The support of the Ministry of Science, Education, and Sport of the Republic of Croatia via Grant 0037-117 is gratefully acknowledged.

References

[1] B. R. Barwell, Cutting string and arranging counters, J. Rec. Math. 4 (1971), 1664–168.

[2] B. S. Beevers, The greatest product, Math. Gazette 77 (1993) 91.

[3] S. L. Greitzer, International Mathematical Olympiads 1959–1977, MAA, Washington, 1978.

[4] P. R. Halmos, Problems for Mathematicians Young and Old, MAA, Washington, 1991.

[5] L. C. Larson, Problem-Solving Through Problems, Springer Verlag, Berlin, 1983.

[6] D. J. Newman, A Problem Seminar, Springer Verlag, Berlin, 1982.

[7] J. Scholes,  18th IMO 1976, Problem 4,  available electronically at

    http://http://www.kalva.demon.co.uk/imo/isoln/isol764.html.

[8] J. Scholes,  40th Putnam 1979 Problem A1,  available electronically at

    http://www.kalva.demon.co.uk/putnam/psoln/psol791.html.

[9] N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, available electronically at

    http://www.research.att.com/∼njas/sequences/index.html.

[10] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth, Monterey, 1986.

2000 Mathematics Subject Classification: Primary 05A17; Secondary: 05A10, 05A15 Keywords: partition of an integer, partition into distinct parts, partition into odd parts

(Concerned with sequences \underline{A000217}, \underline{A000792}, and \underline{A034893}.)

Received November 3 2005; revised version received November 9 2005. Published in Journal of Integer Sequences, November 14 2005.

Return to Journal of Integer Sequences home page.