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?

$\endgroup$
4
  • $\begingroup$ You can partition $n$ into up to $n$ positive parts, but no more. $\endgroup$ – Henry Mar 8 '12 at 18:05
  • $\begingroup$ Why does this question have three downvotes? This is a well-formed question, and shows some research on the part of the OP. $\endgroup$ – rogerl Apr 11 '15 at 3:06
  • $\begingroup$ @rogerl, some of the downvotes may be attributable to the history of the question, which you may be able to see if you click on "edited". $\endgroup$ – Gerry Myerson Apr 11 '15 at 3:19
  • $\begingroup$ @GerryMyerson Fair enough. $\endgroup$ – rogerl Apr 11 '15 at 20:04
6
$\begingroup$

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]
$\endgroup$
0
2
$\begingroup$

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$

$\endgroup$
2
  • $\begingroup$ Does that agree with the number at the OEIS entry? $\endgroup$ – Gerry Myerson Apr 11 '15 at 3:03
  • $\begingroup$ @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. $\endgroup$ – Ross Millikan Apr 11 '15 at 3:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.