Creating a generating function for weak compositions

93 Views Asked by At

As far as I know, generating functions are just formal power series, with each $x$ term being a placeholder for the coefficient that I actually care about. This is simple(?) for certain problems, like the generating functions to find k-sized subsets:

$$ (1 + x)^n = \sum^{n}_{k \ge 0} {n \choose k}x^k \ \ \textrm{(Binomial Theorem)}\implies \sum_{k \ge 0} {n \choose k}x^k= (1 + x)^n \ \ \textrm{(Power Series)} $$

However, I can't figure out the derivation for weak composition. According to my class, the generating function is... $$ \sum_{k \ge 0} {{n + k - 1} \choose {n - 1}}x^k= \frac{1}{(1 - x)^n} $$

But I have no idea how, or why this even makes sense (since as far as I know, the coefficient for weak composition should be ${n + k - 1} \choose {k - 1}$ instead of $n - 1$ in the bottom index).

1

There are 1 best solutions below

4
On BEST ANSWER

First off, the coefficients for the weak composition are correct since the $k$-th coefficient represents the number of $\mathbf{n}$-tuples of non-negative numbers that sum up to exactly $\mathbf{k}$. In other words, the roles of $k$ and $n$ are switched up in the above formula.

Now, concerning the derivation of that generating function, I think it should actually say $$\sum_{k \geq 0} \binom{n + k - 1}{n-1} x^k = \frac{1}{(1 - x)^n}.$$

This would be the derivation: Note that we have $$\frac{1}{1 - x} = \sum_{k \geq 0} x^k.$$

So,

$$\frac{1}{(1 - x)^n} = \prod_{l = 1}^n \frac{1}{1 - x} = \left(\sum_{k_1 \geq 0} x^{k_1} \right) \cdot \ldots \cdot \left(\sum_{k_n \geq 0} x^{k_n} \right).$$

Now, let's consider the coefficient in front of $x^k$ on the right hand side: A product of those $x^{k_i}$'s "contributes" to that coefficient if and only if we have $$x^{k_1} \cdot \ldots \cdot x^{k_n} = x^k \iff k_1 + \dots + k_n = k.$$ As the powers $k_i$ are non-negative, this means that it corresponds exactly to the number of tuples in $(\mathbb{Z}_{\geq 0})^n$ that sum up to $k$.