1

The question is as follows. Partition an integer $n$ into $r$ distintc parts with each part ranges from $[1,m]$ and the parts order is irrelevant. How many ways of different partitions are there?

Note here it is different from the classic partition quesiton which has no restraints on ranges of each part.

Thanks.

user85356
  • 388
  • There is a straightforward generating function $(1-yx)(1-yx^2)\ldots(1-yx^k)$, but I don't see any nice way of getting it into closed form. – user7530 Aug 11 '13 at 15:26
  • I don't see the rational behind it. Can you explain a bit? – user85356 Aug 11 '13 at 18:35
  • Sorry, the signs should be $+$: $(1+yx)(1+yx^2)\ldots(1+yx^m)$. You want the coefficient of $y^rx^n$. At each term you choose either $1$ (excluding that term) or $yx^k$ (including that term). $y^r$ guarantees the partition contains exactly $r$ parts. – user7530 Aug 11 '13 at 21:40
  • I see your point now. I thought there is no such generating function but it seems the one you provided is right and quite elegant. Thanks. – user85356 Aug 11 '13 at 22:09
  • Even though there is no closed form for the general case, I thought I should mention that there is a very nice closed form when $m$ is an odd prime. See Section 4 question 3 of: http://zacharyabel.com/papers/Multi-GF_A06_MathRefl.pdf (if the link breaks in the future, you want to look up Zachary R. Abel's Multivariate Generating Functions and Other Tidbits. This product appears in the solution question 6 in the IMO of 1995). – Xin Yuan Li Aug 30 '20 at 21:29

0 Answers0