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

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$?

-
The answer shouldn't be in terms of n; you want a single fixed function f(x) such that the coefficient of x^n is the number you want (for n). Also, is this homework? – Qiaochu Yuan Dec 4 '10 at 18:55
Er, maybe that series is infinite – Tony B Dec 4 '10 at 19:00
So it's really $x^8/(1-x)^6$, though this is actually off-by-one and should be $x^9/(1-x)^6$ (consider that the first non-zero combination is $1,3,5,7,9$). – Yuval Filmus Dec 4 '10 at 19:24
You've got the right idea with dividing it into six sections, and your answer is almost the same as the book's. But do you really need that n in there? – Qiaochu Yuan Dec 4 '10 at 19:28
ogfcounting.weebly.com/uploads/4/3/7/0/43704337/…, p. 20 explains how to solve this kind of problems. – Artyom Dmitriev Nov 23 '15 at 18:31

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?

-
I'm fairly sure this isn't what the question is asking me to do, as none of what you said makes any sense to me. The answer at the back of the book is (1+x+x^2+...)(x+x^2+...)^4(1+x+x^2+...). – Tony B Dec 4 '10 at 19:15
Ah, I see. I'm using a more general method, but I guess the book's method is simpler for this problem. Do you understand how the answer at the back of the book works? – Qiaochu Yuan Dec 4 '10 at 19:19
Not exactly, which is my main problem. Its similar to the answer I came up with. – Tony B Dec 4 '10 at 19:21

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}.$$

-