A data structure which is essentially an infinite list of Integer-s, but fast lookup (for reasonable small inputs)

Number of partitions of n (looking up a table built using Euler's algorithm)

This uses the power series expansion of the infinite product. It is slower than the above.

This uses countPartitions', and is (very) slow

This uses Euler's algorithm to compute p(n)

See eg.: NEIL CALKIN, JIMENA DAVIS, KEVIN JAMES, ELIZABETH PEREZ, AND CHARLES SWANNACK COMPUTING THE INTEGER PARTITION FUNCTION http://www.math.clemson.edu/~kevja/PAPERS/ComputingPartitions-MathComp.pdf

An infinite list containing all p(n), starting from p(0).

Infinite list of number of partitions of 0,1,2,...

This uses the infinite product formula the generating function of partitions, recursively expanding it; it is reasonably fast for small numbers.

partitionCountListInfiniteProduct == map countPartitions [0..]

Naive infinite list of number of partitions of 0,1,2,...

partitionCountListNaive == map countPartitionsNaive [0..]

This is very slow.

Count all partitions fitting into a rectangle. # = \binom { h+w } { h }

Number of of d, fitting into a given rectangle. Naive recursive algorithm.

Count partitions of n into k parts.

Naive recursive algorithm.