The following is a problem from Chapter 2 of Herbert Wilf's generatingfunctionology:

Let $S$ and $T$ be two fixed sets of nonnegative integers. Let $f(n,k,S,T)$ denote the number of ordered representations of $n$ as a sum of $k$ integers chosen from $T$, each being chosen with multiplicity that belongs to $S$. Find $\sum_{n}f(n,k,S,T)x^n$.

I believe the answer to be: $$[y^k]\prod_{t\in T} (\sum_{s\in S} y^s x^{st}).$$

However, in the back of the book where he provides solutions, he states that it is rather the following: $$\left[\frac{y^k}{k!}\right]\prod_{t\in T}\left(\sum_{s\in S} \frac{y^sx^{st}}{s!}\right)$$ Can anyone explain to me why this is the case? Per my understanding, exponential generating functions are more convenient for labelled structures but I'm having hard time seeing why and if this is the case here.



Your answer counts unordered representations; the question was for ordered representations.

How many ways are there to order a multiset of $k$ elements with multiplicities $s_1,s_2,\cdots$? You should be able to count $k!/(s_1!s_2!\cdots)$ orderings, which leads to the desired answer.

  • $\begingroup$ If so, then I have a follow up question: >Let $g(n,k,T)$ be the number of ordered representations of $n$ as a sum of $k$ distinct integers chosen from a fixed set of nonnegative integers $T$. Find $\sum_n g(n,k,T)x^n$. My solution for this agrees with the solution in the back, namely: $$[y^k]\prod_{t\in T}(1+yx^{t}).$$ Based on your solution, is this wrong? $\endgroup$ – Pavelshu Apr 28 '14 at 3:26
  • 1
    $\begingroup$ @Pavelshu The sum $\sum_n g(n,k,T)x^n=\sum_n f(n,k,\{0,1\},T)x^n$ should be $$\left[\frac{y^k}{k!}\right]\prod_{t\in T}(1+yx^t).$$ You can check with small examples that this is the correct form. $\endgroup$ – blue Apr 28 '14 at 3:38
  • $\begingroup$ I see, I'll have to contemplate about this a bit more. Thank you for your replies. $\endgroup$ – Pavelshu Apr 28 '14 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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