4
$\begingroup$

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?

  • 0
    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.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
  • 0
    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.2012-05-18

3 Answers 3