# Find the Generating Function with respect to n

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.

Thanks

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.
• 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? – Pavelshu Apr 28 '14 at 3:26
• @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. – blue Apr 28 '14 at 3:38