Proof using the product lemma

Question

Let $S$ be the set of all finite subsets of $\mathbb N = \{1,2,3,...\}. $ We define a weight function $w$ where for a subset $X$ of $\mathbb N, w(X)$ is the sum of all the elements in $X$, with $w(\emptyset)=0$. Let $\Phi_S(x)$ be the generating series of $S$ with respect to $w$.

a) Use the Product Lemma to prove that for any $n\ge0,$

$$[x^n]\Phi_S(x)= [x^n]\prod_{i=1}^n(1+x^i).$$

And then, using the result from a) to show that

$$\Phi_S(x)= \prod_{i\ge1}(1+x^i).$$

I'm having trouble with this as I don't know where to start from.

Any help is greatly appreciated!!

Answer 1

HINT: For a positive integer $k$ the polynomial $1+x^k$ is the generating function for the sequence whose $n$-th term is the number of ways of writing $n$ as a sum of distinct elements of the set $\{k\}$. If your product lemma is what I think it is, it says that if $k$ and $\ell$ are distinct positive integers, then the product $(1+x^k)(1+x^\ell)$ is the generating function for the sequence whose $n$-th term is the number of ways to write $n=i+j$ as the sum of two non-negative integers and then write $i$ as the sum of distinct elements of $\{k\}$ and $j$ as the sum of distinct elements of $\{\ell\}$. More generally,

$$\prod_{k=1}^n(1+x^k)$$

is the generating function for the sequence whose $m$-th term is the number of ways to write $m=i_1+i_2+\ldots+i_n$ as the sum of $n$ non-negative integers and then write each $i_k$ as the sum of distinct elements of $\{k\}$. Use this to explain why

$$[x^n]\prod_{k=1}^n(1+x^k)$$

is the number of ways to write $n$ as the sum of distinct positive integers and is therefore the number of $s\in S$ such that $w(s)=n$.

Note: I don’t know exactly what form your product lemma takes. I’m assuming, however, that it relates the coefficients of the product of two generating functions to the coefficients of the factors, either abstractly via the Cauchy product or in terms of the things counted by the coefficients, something along the following lines (modified from Miklós Bóna, Introduction to Enumerative Combinatorics):

Product Formula: Let $f_n$ be the number of ways one can carry out a certain task on the set $[n]$. Let $g_n$ be the number of ways one can carry out another task on $[n]$. Let $F(x)$ and $G(x)$ be the ordinary generating functions of the sequences $\langle f_n:n\ge 0\rangle$ and $\langle g_n:n\ge 0\rangle$.

Let $h_n$ be the number of ways to split the set $[n]$ into the intervals $\{1,2,\ldots,i\}$ and $\{i+1,i+2,\ldots,n\}$, and then carry out the first task on the first interval and the second task on the second interval. Let $H(x)$ be the ordinary generating function of the sequence $\langle h_n:n\ge 0\rangle$. Then $H(x)=F(x)G(x)$.

For the second part of your question you just have to verify that

$$[x^n]\prod_{k=1}^n(1+x^k)=[x^n]\prod_{k\ge 1}(1+x^k)$$

for all $n$.