Understanding the partition function I have been trying, as a toy problem, to implement in either the Python or Haskell programming languages functions to calculate the partitions for a number and the count of those partitions. I have no mathematical background, so I'm probably making silly mistakes when trying to understand some of these concepts I've never been exposed to before.
As I understand it from reading about the partition function on Wolfram, the partition function $P(n)$ is what gives the count of partitions for a given number. The function is given as:
$$
P(n) = \sum_{k=1}^n (-1)^{k+1}[P(n-\frac{1}{2}k(3k-1))+P(n-\frac{1}{2}k(3k+1))]
$$
So, I try to solve by hand for $P(1)=1$; but I just can't do it!
$$
P(1) = \sum_{} 1(P(0)+P(-1))
$$$$
P(1) = \sum_{} 0+0
$$$$
P(1) = 0
$$
This is obviously not right. Where am I going wrong?
 A: I'm not at all sure you're interested in this, but it is an alternative formulation that may be more straightforward to understand and possibly to compute.
Let $P(n, m)$ be the number of partitions of the number $n$ into parts that are of size $m$ or larger.  Then $$P(n,m) = \sum_{i=m}^n P(n-i, i)$$ whenever $n>0$.
The idea here is that we can extract from $n$ a single part of size $i$ between $m$ and $n$, and then having done so we need to partition the remainder, $n-i$. To avoid counting any partition more than once, we require that the parts be extracted in order of increasing size, so after extracting a part of size $i$, we require that all subsequent parts be of size at least $i$.
The base cases are only a little tricky: $$\begin{align}
P(n, m) &= 0 & \text{whenever $n<0$}\\
P(0, m) &= 1 & \\
\end{align}
$$
Also, an obvious optimization is
$$\begin{align}
P(n, m) &= 1 & \text{whenever $\frac n2< m< n$}\\
\end{align}
$$ because there is no way to partition a number $n$ into parts strictly larger than $\frac n2$, except by doing so trivially, into exactly one part.
The partition function itself is then simply $P(n,1)$, the number of partitions of $n$ into parts of size at least 1.
Here is $P(n)$ implemented in Haskell:
p :: Int -> Int
p =
  let
    p' m n
      | n < 0  = 0
      | n == 0 = 1
      | otherwise = sum [p' i (n - i) | i <- [m..n]]
  in
    p' 1

A: By convention, $P(0)=1$ and $P(n) = 0$ for $n<0$.
