Ordinary generating function for nonconsecutive integer selection

Question

I'm trying to understand a problem I came across about ordinary generating functions. The problem is something like this:

How many ways are there to select five integers from $\{1,2,3,...,n\}$ if none of the selected integers can be consecutive? What coefficient do we want to look at?

The given solution is that we want the coefficient of $x^{n-5}$ from the generating function:

$$(1+x+x^2+\cdots)(x+x^2+x^3+...)^4(1+x+x^2+\cdots)$$

I don't understand this generating function or why it is the $x^{n-5}$ coefficient that we look at. I'm guessing that having $6$ terms instead of just $5$ for similar problems like this is what imposes the consecutivity constraint. I know how to solve similar ordinary generating function problems without the nonconsecutive constraint, e.g. the number of ways to select $5$ integers (with replacement) from $\{1,2,...,n\}$ that sum to $K$, if there is no constraint on being nonconsecutive, and looking at $[x^K]$. But I'm not sure how to transfer that problem to this one to set up this generating function, or why we look at the $x^{n-5}$ coefficient.

---

Furthermore, how can I generalize the consecutivity constraint? E.g. instead of just nonconsecutive (spacing of $\ge 2$), what about spacing $\ge M$? So e.g. with $M=3$, if I select the integer $7$, then I cannot choose $[5,6,7,8,9]$.

Answer 1

Reading the generating function left to right:

The $x$ in

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

counts spaces (unchosen numbers) between the smallest chosen number $y_1$ and $0$.

The $x$ in

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

counts spaces between $y_2$ and $y_1$. This is why it starts at $x^1$ because we must have at least $1$ space between consecutive chosen numbers according to the condition in the question. We thus have $x+x^2+x^3+\cdots$ for each consecutive pair from $y_2$, $y_3$, $y_4$ and $y_5$ too. Hence the power of $4$.

Finally the $x$ in

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

counts spaces between $n$ and $y_5$.

The coefficient of $x^{n-5}$ is the number of choices with $n-5$ spaces (unchosen numbers) because

$$\text{#}(\text{chosen numbers from $n$})+\text{#}(\text{unchosen numbers from $n$})=n$$ $$\implies 5+\text{#}(\text{unchosen numbers from $n$})=n$$ $$\implies \text{#}(\text{unchosen numbers from $n$})=n-5$$

So this is why the coefficient of $x^{n-5}$ in

$$(1+x+x^2+\cdots)(x+x^2+x^3+\cdots)^4(1+x+x^2+\cdots)\tag{1}$$

is the number of non-consecutive choices of $5$ consecutive integers from the set $\{1,2,\ldots ,n\}$.

Further, you should now be able to generalise the constraint by starting the "middle" factors of $(1)$ with whatever space size you like e.g. $x^2+x^3+\cdots$ for smallest space size $2$, $x^3+x^4+\cdots$ for smallest space size $3$ etc. You can even tailor the individual gaps!

Answer 2

This is a supplement to @N.Shales nice answer (+1). We write the generating function in a slightly different manner which might be helpful.

We consider all valid $5$-tuples of integers ordered by size. We encode a selected integer with $y$ and we encode an integer which is not selected with $x$.

We are looking for \begin{align*} [x^{n-5}\color{blue}{y^5}](1+x+x^2+\cdots)\color{blue}{y}\left[(x+x^2+x^3+\cdots)\color{blue}{y}\right]^4(1+x+x^2+\cdots) \end{align*}

The interpretation is now:

• Consider $n$ integers $1,2,3,\ldots,n$ increasingly sorted.

• Skip zero or more integers and select an integer: $\qquad\qquad\qquad\ (1+x+x^2+\cdots)\color{blue}{y}$

• Skip at least one integer and select an integer - four times: $\qquad\ \,[(x+x^2+x^3\cdots)\color{blue}{y}]^4$

• Final step: Skip zero or more integers: $\quad\qquad\qquad\qquad\qquad\quad\ (1+x+x^2+\cdots)$

Looking for $[x^{n-5}y^5]$ means we select $5$ integers ($y^5$) skipping $n-5$ integers ($x^{n-5}$).

A generalisation to skip at least two (or more) integers after an integer selection should now be in reach.