1
$\begingroup$

If $p(n)$ is the number of ways in which the number $n$ can be expressed as a sum of positive integers then find $p(200)$.

[I know that] $p(1) = 1$, $p(2) = 2$, $p(3) = 3$, $p(4) = 5$, $p(5) = 7$, $p(6) = 11$.

This question is the toughest question I have ever faced in my school exam. I had tried to use the partition method of combinatorics but failed as the number 200 is too big. Help me to get the answer.

$\endgroup$
8
  • $\begingroup$ Hint: $n=1+1+1+\cdots+1$ ($n$ times) $\endgroup$
    – CIJ
    Commented Mar 24, 2015 at 18:28
  • $\begingroup$ Search for number of partitions in your favorite search-engine (or read this). $\endgroup$
    – barak manos
    Commented Mar 24, 2015 at 18:28
  • $\begingroup$ Just shy of 4 trillion (or rather $4 \cdot 10^{12}$ for those who use -illiards). I see no not-painful way of doing this by hand. $\endgroup$
    – davidlowryduda ♦
    Commented Mar 24, 2015 at 18:31
  • $\begingroup$ Any sort of formulae or general expression for this type of question. $\endgroup$
    – Caratheodory_Enthusiast
    Commented Mar 24, 2015 at 18:47
  • $\begingroup$ Is it possible the problem does not mean the usual partition function? I.e., when you say you know the first six values of $p(n)$, is that because the problem itself gives them, or because you've worked them out for yourself, based on an interpretation of the problem's defintion of $p(n)$? In particular, if the problem actually means ordered sums, so that, for example, $2+1$ and $1+2$ are different sums for $3$, then the answer is simply $2^{199}$. $\endgroup$
    – Barry Cipra
    Commented Mar 24, 2015 at 23:20

2 Answers 2

Reset to default
2
$\begingroup$

When I know the answer for a few small values but I don't know the general formula, I usually turn to Sloane's OEIS. I looked for 1,2,3,5,7,11 and the very first result was Sloane's A000041. These numbers are called the partition numbers. One of the formulas given is $$p(n) = \frac{1}{n} \sum_{k = 0}^{n - 1} \sigma(n - k) p(k).$$ Problem with this of course is that you'd have to compute $p(k)$ for $0 \leq k < 200$. But you can't just say $p(200) = 3972999029388$; I got that answer just by looking in the B-file (see the David Wilson link in Sloane's A000041). Skimming Sloane's entry (it's long), I see no simple formula to get the answer, but I'm not taking an exam.

If you only need a decent approximation, you can use $$p(n) \sim \frac{1}{4n \sqrt{3}} e^{\pi \sqrt{\frac{2n}{3}}}$$ to obtain $p(200) \sim 4100251432187$, which overshoots by little more than 1% (I got this formula from MathWorld but it also appears in Sloane's entry).

$\endgroup$
1
$\begingroup$

There's no general expression for $p(n)$ and, in fact, there's no easy way to calculate something of this magnitude, especially not by hand.

Inputting "partitions of 200" into our friend WolframAlpha gives us $3,972,999,029,388$ partitions.

There's a lot of information about partitions which you an find here. Nothing makes the herculean task of calculating $p(200)$ any easier.

$\endgroup$
1
  • $\begingroup$ I would carefully read this Wikipediocracy post wikipediocracy.com/2013/10/20/… before sending anyone's students to Wikipedia for information on mathematical topics. $\endgroup$
    – Robert Soupe
    Commented Mar 24, 2015 at 22:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .