Manipulating Generating Functions

When we have a generating function for a certain problem, we can manipulate it to solve other combinatorial problems. Consider the following problem:

If you select exactly one element from $\{0, 1, 2, \dots \}$, how many ways are there to select a given number?

---

Since we only select one element, there must be only 1 way to select any given number. This gives us the generating function

$$1 + x + x^2 + \cdots,$$

where each term $x^n$ in the polynomial has a coefficient of 1. Since we will be using this generating function throughout, we will call it $\phi (x)$. Using geometric series, we can express this sum as $\phi (x) = \frac{1}{1-x}$.

We can use this generating function as the basis for other combinatorics problems.

$$\phi (x) = 1 + x + x^2 + \cdots = \frac{1}{1-x}$$

Given some generating function $f(x) = a_0 + a_1x + a_2x^2 + \cdots$, we can shift its coefficients $m$ positions to the right by multiplying it with $x^m:$

$$x^mf(x) = a_0x^m + a_1x^{m+1} + a_2x^{m+2} + \cdots .$$

Using this technique of "shift method" gives us a clean solution to the following problem:

If you select exactly one element from $\{2, 3, 4, \dots \}$, how many ways are there to select a given number? Express your answer as a simplified generating function.

---

As per the problem in the introduction, we will get a generating function where each term $x^n$ for every value $n$ in the set has a coefficient of 1:

$$x^2 + x^3 + x^4 + \cdots .$$

This generating function is similar to the generating function in the introduction, except its coefficients have been shifted right by two spaces. Using this, we may express this generating function more succinctly as

$$x^2 \times \frac{1}{1-x} = \frac{x^2}{1-x}. \ _\square$$

Given some generating function $f(x) = a_0 + a_1x + a_2x^2 + \cdots$, we can scale its exponent by a factor of $m$ by composing it with the function $g(x) = x^m$:

$$f(x^m) = a_0 + a_1x^{m} + a_2x^{2m} + \cdots .$$

Here is an example of the scale method:

If you select exactly one element from the set of even numbers $\{0, 2, 4, \dots \}$, how many ways are there to select a given number?

Express your answer as a simplified generating function.

---

As per the problem in the introduction, we will get a generating function where each term $x^n$ for every even value $n$ has a coefficient of 1:

$$1 + x^2 + x^4 + \cdots .$$

This generating function is similar to the generating function in the introduction, except each exponent has been doubled. Using the scale method, we can get a simple expression for the generating function by using $\phi (x^2)$:

$$\phi (x^2) = \frac{1}{1-x^2}. \ _\square$$