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?
The number of ways to write a positive integer as the sum of distinct parts with a fixed length
-
0And also this observation makes it clear why $\binom{n}2$ might arise in the answer - because the requirement for distinct parts becomes a requirement for at least one part of each size in the 'dual' problem. – 2012-05-18
3 Answers
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.
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.
Have a look to Henry Bottomley's site http://www.se16.info/js/partitionstest.htm I like it very much and I hope it will help you. greetings s.h.
-
0While the site seems relevant, I don't think it's worth ressurecting a year-old post just for this. – 2013-06-09