Question from Wilf's generatingfunctionology on ordered representations of $n$ as a sum of $k$ distinct integers.

Question

This is a question from Wilf's generatingfunctionology, Chapter 2, Exercise 21(a) and (b) (p. 71 in the 3rd edition).

(a) Let $T$ be a fixed set of nonnegative integers. Let $f(n,k,T)$ be the number of ordered representations of $n$ as a sum of $k$ integers chosen from $T$. Find $\sum_n f(n,k,T)x^n$.

(b)Let $g(n,k,T)$ be the number of ordered representations of $n$ as a sum of $k$ distinct integers chosen from $T$. Find $\sum_n g(n,k,T)x^n$.

For part (a) I wrote, for $t_i \in T$

$$\begin{align*} f(n,k,T) &= \sum_{t_1 + \cdots + t_k = n} 1 \\ &= \sum_{t_1 + \cdots + t_k =n} a_{t_1} \cdot \cdots \cdot a_{t_k} & \text{where } a_{t_i} = 1 \ \forall \, i\\ \end{align*} $$

Then, by the power rule for ordinary power series generating functions, we have

$$ \left\{ f(n,k,T) \right\}_{n=0}^{\infty} \leftrightarrow \left( \{ 1\}_{t \in T} \right)^k = \left(\sum_{t \in T} x^t \right)^k. $$

This agrees with the answer provided in the book, but I'm a little uncertain that my final steps are justified (I'm mostly concerned about taking the sum over $t \in T$).

For part (b) the book provides the solution

$$ \sum_n g(n,k,T) x^n = [y^k] \prod_{t \in T}(1+yx^t) $$

I'm at a loss how to arrive at this.

Edited: Part (c) of this question was asked here: Find the Generating Function with respect to n, though the answer doesn't seem to shed light on parts (a) and (b) above.

Answer 1

Case (b):

Since we are looking for ordered representations of $n$ as a sum of $k$ distinct integers chosen from $T$, each element $t\in T$ can occur at most once.

To select an element $t\in T$ exactly zero or one times is encoded with $$x^{0\cdot t}+x^{1\cdot t}=1+x^t$$

We observe: The product

$$\prod_{t\in T}(1+x^t)=\sum_{n\geq 0}g(n,T)x^n$$

encodes $g(n,T)$ the number of possibilities $n$ can be represented as sum of elements of $T$, whereby each element occurs zero or one times. Note, the RHS is the expansion according to $x$ and therefore we sum up with respect to the powers of $x$ (i.e. $n\geq 0$).

The number of ordered representations of $n$ as sum of distinct integers is therefore

$$[x^n]\prod_{t\in T}(1+x^t)=[x^n]\sum_{m\geq 0}g(m,T)x^m=g(n,T)\qquad\qquad n\geq 0$$

But this product does not provide any information about the number $k$ of summands which are used. We encode this particular information by counting the number of summands. This is done by multiplying each occurrence of $x^t$ by $y$.

\begin{align*} \prod_{t\in T}(1+yx^t)=\sum_{j\geq 0}\sum_{n\geq 0}g(n,k,T)x^ny^j\tag{1} \end{align*}

Observe, that $y^j$ implies that $j$ elements from $T$ are selected to form a sum. Now we are interested in finding the number of representations with $k$ distinct integers and we therefore select from (1) the series in $x$ corresponding to $y^k$.

\begin{align*} [y^k]\prod_{t\in T}(1+yx^t)=[y^k]\sum_{j\geq 0}\sum_{n\geq 0}g(n,k,T)x^ny^j=\sum_{n\geq 0}g(n,k,T)x^n\qquad\qquad k\geq 0 \end{align*}

A remark to the first part.

Case (a): The series \begin{align*} \sum_{t\in T}x^t \end{align*} represents the selection of exactly one element $t$ from $T$. The $k$-th power means to select $k$ elements from $T$ and summing them up. So, when expanding the series with respect to $x$ we get the representation. \begin{align*} (\sum_{t\in T}x^t)^k=\sum_{n\geq 0}f(n,k,T)x^n \end{align*}