4
$\begingroup$

Let $P(n,k)$ denote the number of partitions of $n$ into $k$ parts. I would like to know for given $n$, which $k$ does maximize $P(n,k)$?

Additionally, information on the maximum of $P(n,k)$, for fixed $n$, would also be of interest.

I'm interested in varied information but please note I'm still not out of high school!

I've done some research on the topic earlier and found out that for $P(100, k)$, it is $7$ that yields the greatest value, even superseding $k=100(1/2)=50$.

I am also aware of an asymptotic formula from an MO question:

$P(n, k)\sim\frac{1}{2\pi n} \left( \frac{e^2 n}{k^2} \right)^k$

Also, I know about that triangular-looking grid for $P(n,k)$. But then, what is derived from it?

Would this PDF be of any help?

  • 0
    @GerryMyerson Fair enough.2015-04-11

2 Answers 2

6

The numbers $\max_k P(n,k)$ are tabulated at http://oeis.org/A002569. This page gives several references.

  • F. C. Auluck, S. Chowla and H. Gupta, On the maximum value of the number of partitions into k parts, J. Indian Math. Soc., 6 (1942), 105-112.
  • T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176 (p. 172, gives a(9) incorrectly as 6).
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

There is also a link to a table that goes out to $n=3000$. (The table is due to Robert Israel and Robert G. Wilson.)

At http://oeis.org/A046155 the value of $k$ maximizing $P(n,k)$ is given for all $n$, $0\le n\le82$:

n  | k maximizing P(n,k) ----------------------- 0  | 0 1  | 1 2  | 1 3  | 1 4  | 2 5  | 2 6  | 2 7  | 3 8  | 3 9  | 3 10 | 4 11 | 4 12 | 4 13 | 4 14 | 4 15 | 5 16 | 5 17 | 5 18 | 6 19 | 6 20 | 6 21 | 6 22 | 6 23 | 7 24 | 7 25 | 7 26 | 7 27 | 7 28 | 7 29 | 8 30 | 8 31 | 8 32 | 8 33 | 8 34 | 8 35 | 9 36 | 9 37 | 9 38 | 9 39 | 9 40 | 10 41 | 10 42 | 10 43 | 10 44 | 10 45 | 10 46 | 10 47 | 11 48 | 11 49 | 11 50 | 11 51 | 11 52 | 11 53 | 11 54 | 12 55 | 12 56 | 12 57 | 12 58 | 12 59 | 12 60 | 13 61 | 13 62 | 13 63 | 13 64 | 13 65 | 13 66 | 13 67 | 13 68 | 14 69 | 14 70 | 14 71 | 14 72 | 14 73 | 14 74 | 14 75 | 15 76 | 15 77 | 15 78 | 15 79 | 15 80 | 15 81 | 15 82 | 15 

There's also a Mathematica program for calculating it, due to Robert G. Wilson:

f[n_] := Block[{k = 1, mk = mx = 0}, While[k < n + 1, a = Length@ IntegerPartitions[n, {k}]; If[a > mx, mx = a; mk = k]; k++ ]; mk]; Array[f, 85] 
2

For the asymptotic, given $n$ we want to maximize $\frac {(n-1)^k}{k^{2k}}$. You probably know how to do that, take the derivative and set to zero. Alpha says this comes at $n=e^2k^2+1$, so $k=\frac{\sqrt{n-1}}e$

  • 0
    @GerryMyerson: I didn't look because I think of OEIS as small values and asymptotics as large values, but it is a good question. At small values, OEIS is *much* larger. At $n=82$ we have $k \approx 3.3$, while the OEIS entry says $k=15$. OEIS doesn't go higher.2015-04-11