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
-
0So your example is equal to the number of ways of expressing 12 as the sum of parts of size 3, including at least one "3". For "n" instead of "3" there is a recurrence relation - you might see it will depend on the last "n-1" terms. That restricts the simplicity go the any formula. – 2012-05-17
-
0@Mark, I think your "parts of size 3" is a typo for "parts of size at most three." But I don't think you capture the "distinct parts" requirement. – 2012-05-17
-
0@GerryMyerson: You are right of course. It was late. So you need at least one part of size 1, one of size 2 and one of size 1 - and are looking then at the number of partitions of $n-6$ into parts of size at most 3. And all I wanted that for in a comment was to use it to get some idea of the nature of a recurrence relation or generating function, which I think can be helpful - though the solutions are elegant. – 2012-05-18
-
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