The number of ways to write a positive integer as the sum of distinct parts with a fixed length

Question

I am a topologist and not terribly familiar with the combo literature so please forgive me if this is standard. I'm hoping for some sort of reference for this. Given a positive integer $n$, I wish to count the number of ways to write $n$ as a sum of distinct parts with a fixed length. For example, $n=12$ with length $3$ would yield $7$; namely $\{1,2,9\}, \{1,3,8\}, \{1,4,7\}, \{1,5,6\}, \{2,3,7\}, \{2,4,6\}, \{3,4,5\}$. I am aware of this $Q(n)$ function but it looks at all lengths, not a fixed one. Is anything known about this?

Answer 1

Let $q(n,k)$ be the number of partitions of $n$ into $k$ distinct parts. The generating function is $$Q_k(x)=\sum_{n\ge 0}q(n,k)x^n=\frac{x^{k+\binom{k}2}}{(1-x)(1-x^2)\dots(1-x^k)}\;.$$ A fairly terse derivation can be found in these notes. The numbers $q(n,k)$ are sequence A008289 in the Online Encyclopedia of Integer Sequences; the entry has a little more information and a reference.

Added: The $\binom{k}2$ in the exponent in the numerator corresponds naturally to the $\binom{k}2=\frac{k(k-1)}2$ in Zander’s answer; the reason for it can be found in the notes to which I linked.

Answer 2

You can refer to the pages for Partition Function Q and Partition Function P at MathWorld. This comes straight from there.

The quantity you want is $Q(n,k)$, the number of partitions of $n$ into exactly $k$ distinct parts, which has the identity $$ Q(n,k) = P\left(n-\frac{k(k-1)}{2},k\right) $$ where $P(n,k)$ is the number of partitions of $n$ into exactly $k$ not-necessarily-distinct parts. MathWorld gives a recurrence relation for $P(n,k)$ in general and relatively simple formulas for $k\le 4$. In particular for the case in your example $k=3$ $$ P(n,3) = \mathrm{round}(n^2/12) $$ and hence $$ Q(n,3) = \mathrm{round}\left((n-3)^2/12\right) $$ where round is rounding to the nearest integer.