Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
So 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. –  Mark Bennet May 17 '12 at 22:04
    
@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. –  Gerry Myerson May 17 '12 at 23:52
    
@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. –  Mark Bennet May 18 '12 at 6:30
    
And 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. –  Mark Bennet May 18 '12 at 6:35
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
While the site seems relevant, I don't think it's worth ressurecting a year-old post just for this. –  Goos Jun 9 '13 at 7:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.