Recurrence Relation - # of binary strings with given property











up vote
2
down vote

favorite












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










share|cite|improve this question




















  • 1




    Something is wrong in your solution. Consider $n = 5$ - the possible strings are 11111, 00000, 11000, 00111, 11100, 00011, and $a_5 = 6$.
    – Michael Lugo
    Nov 13 at 17:48










  • Shouldn't $a_6$ be 10 and $a_7$ be 14?
    – Mathaholic24
    Nov 14 at 2:01

















up vote
2
down vote

favorite












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










share|cite|improve this question




















  • 1




    Something is wrong in your solution. Consider $n = 5$ - the possible strings are 11111, 00000, 11000, 00111, 11100, 00011, and $a_5 = 6$.
    – Michael Lugo
    Nov 13 at 17:48










  • Shouldn't $a_6$ be 10 and $a_7$ be 14?
    – Mathaholic24
    Nov 14 at 2:01















up vote
2
down vote

favorite









up vote
2
down vote

favorite











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










share|cite|improve this question















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







combinatorics recurrence-relations






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 13 at 16:55

























asked Nov 13 at 16:47









rover2

757212




757212








  • 1




    Something is wrong in your solution. Consider $n = 5$ - the possible strings are 11111, 00000, 11000, 00111, 11100, 00011, and $a_5 = 6$.
    – Michael Lugo
    Nov 13 at 17:48










  • Shouldn't $a_6$ be 10 and $a_7$ be 14?
    – Mathaholic24
    Nov 14 at 2:01
















  • 1




    Something is wrong in your solution. Consider $n = 5$ - the possible strings are 11111, 00000, 11000, 00111, 11100, 00011, and $a_5 = 6$.
    – Michael Lugo
    Nov 13 at 17:48










  • Shouldn't $a_6$ be 10 and $a_7$ be 14?
    – Mathaholic24
    Nov 14 at 2:01










1




1




Something is wrong in your solution. Consider $n = 5$ - the possible strings are 11111, 00000, 11000, 00111, 11100, 00011, and $a_5 = 6$.
– Michael Lugo
Nov 13 at 17:48




Something is wrong in your solution. Consider $n = 5$ - the possible strings are 11111, 00000, 11000, 00111, 11100, 00011, and $a_5 = 6$.
– Michael Lugo
Nov 13 at 17:48












Shouldn't $a_6$ be 10 and $a_7$ be 14?
– Mathaholic24
Nov 14 at 2:01






Shouldn't $a_6$ be 10 and $a_7$ be 14?
– Mathaholic24
Nov 14 at 2:01












2 Answers
2






active

oldest

votes

















up vote
1
down vote













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 $ngeq 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 $sgeq 2$ then observe that the answer is $c_{n-s}$.



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






share|cite|improve this answer






























    up vote
    1
    down vote













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



    $$F(z, w) = (1+z^2+z^3+cdots)
    times sum_{qge 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_{qge 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_{qge 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 $nge 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 $nge 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);





    share|cite|improve this answer























      Your Answer





      StackExchange.ifUsing("editor", function () {
      return StackExchange.using("mathjaxEditing", function () {
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
      });
      });
      }, "mathjax-editing");

      StackExchange.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "69"
      };
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function() {
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled) {
      StackExchange.using("snippets", function() {
      createEditor();
      });
      }
      else {
      createEditor();
      }
      });

      function createEditor() {
      StackExchange.prepareEditor({
      heartbeatType: 'answer',
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader: {
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      },
      noCode: true, onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      });


      }
      });














       

      draft saved


      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2996975%2frecurrence-relation-of-binary-strings-with-given-property%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes








      up vote
      1
      down vote













      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 $ngeq 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 $sgeq 2$ then observe that the answer is $c_{n-s}$.



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






      share|cite|improve this answer



























        up vote
        1
        down vote













        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 $ngeq 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 $sgeq 2$ then observe that the answer is $c_{n-s}$.



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






        share|cite|improve this answer

























          up vote
          1
          down vote










          up vote
          1
          down vote









          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 $ngeq 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 $sgeq 2$ then observe that the answer is $c_{n-s}$.



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






          share|cite|improve this answer














          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 $ngeq 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 $sgeq 2$ then observe that the answer is $c_{n-s}$.



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







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Nov 13 at 18:27

























          answered Nov 13 at 17:57









          Anguepa

          1,234719




          1,234719






















              up vote
              1
              down vote













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



              $$F(z, w) = (1+z^2+z^3+cdots)
              times sum_{qge 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_{qge 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_{qge 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 $nge 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 $nge 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);





              share|cite|improve this answer



























                up vote
                1
                down vote













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



                $$F(z, w) = (1+z^2+z^3+cdots)
                times sum_{qge 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_{qge 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_{qge 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 $nge 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 $nge 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);





                share|cite|improve this answer

























                  up vote
                  1
                  down vote










                  up vote
                  1
                  down vote









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



                  $$F(z, w) = (1+z^2+z^3+cdots)
                  times sum_{qge 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_{qge 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_{qge 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 $nge 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 $nge 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);





                  share|cite|improve this answer














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



                  $$F(z, w) = (1+z^2+z^3+cdots)
                  times sum_{qge 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_{qge 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_{qge 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 $nge 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 $nge 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);






                  share|cite|improve this answer














                  share|cite|improve this answer



                  share|cite|improve this answer








                  edited Nov 13 at 19:14

























                  answered Nov 13 at 18:34









                  Marko Riedel

                  38.2k338106




                  38.2k338106






























                       

                      draft saved


                      draft discarded



















































                       


                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2996975%2frecurrence-relation-of-binary-strings-with-given-property%23new-answer', 'question_page');
                      }
                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      Popular posts from this blog

                      Probability when a professor distributes a quiz and homework assignment to a class of n students.

                      Aardman Animations

                      Are they similar matrix