Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
You can partition $n$ into up to $n$ positive parts, but no more. –  Henry Mar 8 '12 at 18:05
    
Why does this question have three downvotes? This is a well-formed question, and shows some research on the part of the OP. –  rogerl Apr 11 at 3:06
    
@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". –  Gerry Myerson Apr 11 at 3:19
    
@GerryMyerson Fair enough. –  rogerl Apr 11 at 20:04

2 Answers 2

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]
share|improve this answer
    
Thanks, Arthur. –  Gerry Myerson Apr 12 at 9:31

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$

share|improve this answer
    
Does that agree with the number at the OEIS entry? –  Gerry Myerson Apr 11 at 3:03
    
@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. –  Ross Millikan Apr 11 at 3:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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