Generating function for modeling the number of ways to select five integers from 1 to n where no two are consecutive

Question

So, I guess divide it into six sections representing the difference between the numbers, so the first is $0\rightarrow n$, the second through fifth are $1\rightarrow n$ and the sixth is $0\rightarrow n$ again, and that becomes a generating function of $((1+x+x^2+\cdots+x^n)^2)((x^2+\cdots+x^n)^4)$. Does this make sense, and what coefficient represents what value of $n$?

Answer 1

Let $f_{k,n}$ be the number of ways to select $k$ integers in $\{ 1, 2, ... n \}$ such that no two are consecutive. There are two ways to do this: either the largest one is not $n$, and then you choose $k$ integers in $\{ 1, 2, ... n-1 \}$, or the largest one is $n$, and then you choose $k-1$ integers in $\{ 1, 2, ... n-2 \}$. This gives

$$f_{k,n} = f_{k,n-1} + f_{k-1, n-2}.$$

The generating function you want is $\sum_{n \ge 0} f_{5,n} x^n$, but I think it will be easier to find the bivariate generating function $\sum_{n,k \ge 0} f_{k, n} y^k x^n$ first. Do you know how to do this from a recursion?

Answer 2

I don't understand why this question is asked in the language of generating functions. The easy way to solve the problem is to take any subset $\{a,b,c,d,e\}$ of $\{1,\dots,n-4\}$, and choose the subset $\{a,b+1,c+2,d+3,e+4\}$. In particular, there are $\binom{n-4}{5}$ ways to do this. We can recover the generating function using basic generating function knowledge:

$$\sum_{n\geq 0} \binom{n-4}{5}x^n =\sum_{n\geq 0} \binom{n-9+5}{5}x^n=x^9\sum_{n\geq 0} \binom{n-9+5}{5}x^{n-9}$$ Changing indices and recognizing the form of the generating function, we have $$=x^9\sum_{N\geq -9} \binom{N+5}{5}x^N=\frac{x^9}{(1-x)^6}.$$