Determine generating series for a subset

Question

Determine the generating series of a subset S of $\{1, 2, 3, ..., n\}$ so that consecutive elements of S differ by no more than 2.

My thinking: Try to use compositions. Essentially we have that each part of a composition can be from the set $\{0, 1, 2\}$ if we define $c_i = s_i - s_{i-1}$ for $s \in S$. That is, since the difference is at more 2 between consecutive terms in S, we can have differences of 0, 1, or 2. So those are our choices for each part.

This means that for each part, we get the function $c(x) = 1 + x + x^2$ so with $n$ choices we have $n-1$ possible parts, since they'll represent the value between the $s_1 and s_2$, then $s_2 and s_3$, all the way to $s_{n-1} and s_n$ term, ie there are $n-1$ differences between $n$ subsequent terms.

So, we can get the formula $\sum_{k=0}^{n}(1+x+x^2)^{k-1}=\frac{1}{1+x+x^2}\sum_{k=0}^n(1+x+x^2)^k$ except this is where I get stuck. How can I find a simple formula for a generating function for this series?

I was thinking that the fact that $(1+x)^n = \sum_{k=0}^n\binom{n}{k}x^k$ may come in handy, with $x$ representing $1+x+x^2$ but I'm not really sure how to "get rid of", or account for, the $\binom{n}{k}$ term.

Any help would be appreciated. Thanks!

Answer 1

We consider the set of binary strings of length $n$ with at most one $0$ between consecutive $1$s. Let $a_n$ be the number of strings that start with $0$, and let $b_n$ be the number of strings that start with $1$. Then $a_1=b_1=1$, $b_2=2$, and \begin{align} a_n &= a_{n-1} + b_{n-1} &&\text{for $n \ge 2$}\\ b_n &= b_{n-1} + b_{n-2} + 1 &&\text{for $n \ge 3$} \end{align} (The three cases for $b_n$ correspond to $1$, $01$, and $0\dots0$.) Let $A(z)=\sum_{n=1}^\infty a_n z^n$ and $B(z)=\sum_{n=1}^\infty b_n z^n$. Then the recurrence relations imply \begin{align} A(z)-a_1 z&=z A(z) + z B(z) \\ B(z)-b_1 z-b_2 z^2&=z (B(z) - b_1 z) + z^2 B(z) + \frac{z^3}{1-z} \end{align} Solving for $B(z)$ yields $$B(z)=\frac{z + z^2 + \frac{z^3}{1-z}}{1-z-z^2}=\frac{z}{(1-z)(1-z-z^2)},$$ and solving for $A(z)$ yields $$A(z) = \frac{z(1 + B(z))}{1-z}=\frac{z(1-z+z^3)}{(1-z)^2(1-z-z^2)}.$$ So the desired generating function (including the $1z^0=1$ term for the empty string) is $$1+A(z)+B(z)=\frac{1-z+z^3}{(1-z)^2(1-z-z^2)},$$ which matches both OEIS A000126 and @awkward's answer.

Answer 2

My initial solution to this problem was oversimplified and incorrect. The following solution strikes me as overly complex, but at least it is correct (I think).

An equivalent set of objects is that of binary strings of length $n$ in which any 1 is followed by at least one more 1 within the next two bits. We break the set of acceptable strings into three disjoint cases, based on the number of 1s in the string.

Case 1: The string contains no 1s, i.e. it is a sequence of 0s. The generating function is $$f_1(z) = \frac{1}{1-z}$$

Case 2: The string contains exactly one 1, so it is a sequence of 0s, followed by a single 1, followed by a sequence of 0s. The generating function is $$f_2(z) = \frac{1}{1-z} \cdot z \cdot \frac{1}{1-z}$$

Case 3: The string contains at least two 1s. It must consist of a sequence of 0s, followed by a single 1, optionally followed by a single 0, followed by a sequence of (1 or 10)s, followed by a single 1, followed by a sequence of 0s. The generating function is $$f_3(z) = \frac{1}{1-z} \cdot z (1+z) \cdot \frac{1}{1-(z+z^2)} \cdot \frac{1}{1-z}$$

(Throughout the above, a "sequence" may have zero length.)

Finally, the solution to the problem is $$g(z) = f_1(z) + f_2(z) + f_3(z)$$ After some simplification, $$g(z) = \frac{1-z+z^3}{(1-z)^2 (1-z-z^2)}$$

---

EDIT: The following is an alternate way of finding $f_3(z)$, the generating function in the third case, which I think is a little simpler than the method given above, although it is longer because we throw in a derivation of a well-known result.

As before, we want to count acceptable bit strings that contain at least two 1s. Any such string starts with a sequence of 0s, followed by a 1, followed by a string of bits with no two consecutive 0s, then a 1 followed by a sequence of 0s. It is well known (we give a derivation below) that the generating function for a bit string without two consecutive 0s is $$B_2(z) = \frac{1+z}{1-z-z^2}$$ so $$f_3(z) = \frac{1}{1-z} \cdot z \cdot \frac{1+z}{1-z-z^2} \cdot z \cdot \frac{1}{1-z}$$ which is the same answer obtained previously.

Here is a derivation of the generating function $B_2(z)$. A bit string with no two consecutive zeros is

• an empty string or 0, followed by
• an empty string, or a 1 followed by a string with no two consecutive zeros.

So $$B_2(z) = (1+z)(1 + z B_2(z))$$ Solving this equation for $B_2(z)$ yields the generating function above.