1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (+1) That is clearer: $y$'s enumerate choices, $x$'s enumerate gaps between choices. I guess your ogf is just a single term of the expansion of a $2$-indeterminate ogf, one which uses $y$ to count variable numbers of choices from our set. $\endgroup$ – N. Shales Sep 1 '17 at 16:29
  • 1
    $\begingroup$ @NShales: Exactly! Thanks for upvoting and your friendly reply. :-) $\endgroup$ – Markus Scheuer Sep 1 '17 at 16:33
  • 1
    $\begingroup$ You're welcome, a pleasure as always! :) $\endgroup$ – N. Shales Sep 1 '17 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.