2
$\begingroup$

Let $a_n$ be the number of binary strings of length $n$ with the property that each entry is adjacent to at least one entry of the same type.

ex: $11000111$ is a valid string but $11011000$ is not valid

$\textbf{(a) Find $a_1,a_2,a_3,a_4,a_5,a_6,a_7$}$

If someone can check that my attempt is correct, I would really appreciate it.

$a_1=0$ since we cannot have just $0$ or just $1$ as there will be no adjacent of the same type

$a_2=2$: either $00$ or $11$

$a_3=2$: either $000$ or $111$

$a_4=4$:

Reasoning:

$\textbf{If we start with a $0$}$: For the second entry we have $1$ choice as we are forced to put a $0$ since we started with a $0$. For the third entry we have $2$ choices, and similarly for the fourth entry we have $1$ choice. So there are $2$ such strings.

$\textbf{If we start with a $1$}$: For the second entry we are forced to put a $1$. For the third entry we have $2$ choices, and for the fourth entry we have $1$ choice. So there are $2$ such strings.

So $a_4=2+2=4$ strings.

Following the same method for the remaining:

$a_5=4$

$a_6=8$

$a_7=8$

$\textbf{(b) Find the recurrence relation for $a_n$}$

$$a_n= \begin{cases} 2a_{n-2}&n \text{ even},\\ a_{n-1}&n \text{ odd} \end{cases}$$

$\endgroup$
  • 1
    $\begingroup$ Something is wrong in your solution. Consider $n = 5$ - the possible strings are 11111, 00000, 11000, 00111, 11100, 00011, and $a_5 = 6$. $\endgroup$ – Michael Lugo Nov 13 '18 at 17:48
  • $\begingroup$ Shouldn't $a_6$ be 10 and $a_7$ be 14? $\endgroup$ – Mathaholic24 Nov 14 '18 at 2:01
2
$\begingroup$

Using $z$ for ones and $w$ for zeros we get the generating function

$$F(z, w) = (1+z^2+z^3+\cdots) \times \sum_{q\ge 0} (w^2+w^3+\cdots)^q (z^2+z^3+\cdots)^q \\ \times (1+w^2+w^3+\cdots).$$

This is

$$\left(1+\frac{z^2}{1-z}\right) \times \sum_{q\ge 0} \frac{w^{2q} z^{2q}}{(1-w)^q (1-z)^q} \\ \times \left(1+\frac{w^2}{1-w}\right).$$

Continuing without the distinction between ones and zeros we get

$$\left(1+\frac{z^2}{1-z}\right)^2 \sum_{q\ge 0} \frac{z^{4q}}{(1-z)^{2q}} \\ = \left(1+\frac{z^2}{1-z}\right)^2 \frac{1}{1-z^4/(1-z)^2} \\ = (1-z+z^2)^2 \frac{1}{(1-z)^2-z^4}.$$

The difference of two squares yields $$(1-z+z^2)^2 \frac{1}{(1-z+z^2)(1-z-z^2)}.$$

which simplifies to

$$\bbox[5px,border:2px solid #00A000]{ G(z) = \frac{1-z+z^2}{1-z-z^2}.}$$

From the coefficients of this OGF we get the sequence

$$1, 0, 2, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, \\ 1220, 1974, 3194, 5168, 8362, \ldots$$

which is OEIS A006355 where these data are confirmed. Now for the coefficients we have

$$[z^0] G(z) (1-z-z^2) = G_0 = [z^0] (1-z+z^2) = 1$$

and hence $G_0 = 1.$ Furthermore

$$[z^1] G(z) (1-z-z^2) = G_1-G_0 = [z^1] (1-z+z^2) = -1$$

so $G_1 = 0.$ Next we find

$$[z^2] G(z) (1-z-z^2) = G_2-G_1-G_0 = [z^2] (1-z+z^2) = 1$$

so $G_2 = 2.$ For $n\ge 3$ we get

$$[z^n] G(z) (1-z-z^2) = G_n - G_{n-1} - G_{n-2} = [z^n] (1-z+z^2) = 0$$

so that for $n\ge 3$

$$\bbox[5px,border:2px solid #00A000]{ G_n = G_{n-1} + G_{n-2}.}$$

The following Maple code documents the problem definition that was used.

ENUM :=
proc(n)
option remember;
local ind, d, res, pos;

    if n=0 then return 1 fi;
    if n=1 then return 0 fi;
    if n=2 then return 2 fi;

    res := 0;

    for ind from 2^n to 2*2^n-1 do
        d := convert(ind, base, 2)[1..n];

        if d[1] = d[2] and d[n] = d[n-1] then
            for pos from 2 to n-1 do
                if d[pos-1] <> d[pos] and
                d[pos] <> d[pos+1] then
                    break;
                fi;
            od;

            if pos = n then
                res := res + 1;
            fi;
        fi;
    end;

    res;
end;


X := n-> coeftayl((1-z+z^2)/(1-z-z^2), z=0, n);
$\endgroup$
1
$\begingroup$

Your argument seems wrong to me. In particular the following part.

If we start with a $0$: For the second entry we have one choice as we are forced to put a $0$ since we started with a $0$. For the third entry we have two choices, and similarly for the fourth entry we have one choice.

That last sentence seems to be true for $n=4$, but not in general for $n>4$. In this case it is only true if you choose $1$ for the third entry, but if you've chosen $0$ then you have two choices.

That analogous happens in the case where you start with $1$.

For the recurrence relation I think the following should work. For any $m$ let $b_m$ and $c_m$ denote respectively the strings of the desired form that start with a $0$ and with a $1$ repectively. Note that $b_m=c_m=a_m/2$. So this is all a bit silly, but let's do it for the sake of keeping the argument clear.

Let's fix $n\geq 3$. I'll calculate $b_n$ in terms on $c_m$ for $m<n$.

How many strings are there that have $0< s < n$ zeroes in a row before having a one? As you've noted if $s=1$ then the answer is zero strings. For $s\geq 2$ then observe that the answer is $c_{n-s}$.

Using this show that $b_m=1+ \Sigma_{2\leq s < n} c_{n-s}$.

$\endgroup$
0
$\begingroup$

You can take this as a sequence of stretches of at least two equal symbols. In ordinary generating function terms a sequence of two or more would be represented by:

$\begin{align*} z^2 + z^3 + \dotsb &= \frac{z^2}{1 - z} \end{align*}$

A sequence of the above in turn would be:

$\begin{align*} 1 + \frac{z^2}{1 - z} + \left(\frac{z^2}{1 - z}\right)^2 + \dotsb &= \frac{1}{1 - \frac{z^2}{1 - z}} \\ &= \frac{1 - z}{1 - z - z^2} \end{align*}$

Consider the Fibonacci sequence, defined by $F_{n + 2} = F_{n + 1} + F_n$ with $F_0 = 0, F_1 = 1$. It's generating function is:

$\begin{align*} F(z) &= \sum_{n \ge 0} F_n z^n = \frac{z}{1 - z - z^2} \end{align*}$

But also:

$\begin{align*} \sum_{n \ge 0} F_{n + 1} z^n &= \frac{F(z) - F_0}{z} = \frac{1}{1 - z - z^2} \end{align*}$

We see that our generating function is:

$\begin{align*} \frac{1 - z}{1 - z - z^2} &= \sum_{n \ge 0} (F_{n + 1} - F_n) z^n \\ &= \sum_{n \ge 0} F_{n - 1} z^n \end{align*}$

So the number of sequences of length $n$ is $F_{n - 1}$, where we extend to $F_{-1} = 1$ (as it should be to get one sequence of length 0).

$\endgroup$

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.