Partition Function Q

$Q(n)$ gives the number of ways of writing the Integer $n$ as a sum of Positive Integers without regard to order with the constraint that all Integers in each sum are distinct. The values for $n=1$, 2, ... are 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, ... (Sloane's A000009). The Generating Function for $Q(n)$ is

$$\prod_{m=1}^\infty (1+x^m)={1\over\prod_{m=0}^\infty (1-x^{2m+1})}=1+x+x^2+2x^3+2x^4+3x^5+\ldots.$$

The values of $n$ for which $Q(n)$ is Prime are 3, 4, 5, 7, 22, 70, 100, 495, 1247, 2072, ... (Sloane's A046065), with no others for $n\leq 15,000$.

The number of Partitions of $n$ with $\leq k$ summands is denoted $q(n,k)$ or $q_k(n)$. Therefore, $q_n(n)=P(n)$ and

$$q_k(n)=q_{k-1}(n)+q_k(n-k).$$

See also Partition Function P

References

Abramowitz, M. and Stegun, C. A. (Eds.). ``Partitions into Distinct Parts.'' §24.2.2 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, pp. 823-824, 1972.

Sloane, N. J. A. Sequences A046065 and A000009/M0281 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.