A176148 The number of words of length n created with the letters a, b, c with at least as many a's as b's and at least as many b's as c's and no adjacent letters forming the pattern aba or bab.

1, 1, 3, 9, 17, 44, 143, 309, 825, 2641, 6036, 16310, 51451, 121475, 330611, 1031592, 2489179, 6806882, 21058747, 51618081, 141626550, 435164141, 1079460430, 2969133001, 9071871281, 22716623921, 62604444233, 190384667595, 480402101159, 1325982687892

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..200

Example

For n = 0, there is the empty word. For n = 1, there is one word a. For n = 2, there are three words, aa, ab, ba. For n = 3, there are nine words, aaa, aab, baa, bac, cab, acb, cba, abc, bca.

Maple

makeabababavoiders:=proc( n ) local out, tout, i; if n=0 then return([]); end if; if n=1 then return([[0], [1], [2]]); end if; if n=2 then return([[0, 0], [1, 1], [2, 2], [0, 1], [1, 0], [2, 0], [0, 2], [1, 2], [2, 1]]); end if; tout:=makeabababavoiders(n-1); out:=[]; for i from 1 to nops(tout) do if tout[ i ][ -1]=0 and tout[ i ][ -2]=1 then out:=[op(out), [op(tout[ i ]), 0], [op(tout[ i ]), 2]]; elif tout[ i ][ -1]=1 and tout[ i ][ -2]=0 then out:=[op(out), [op(tout[ i ]), 1], [op(tout[ i ]), 2]]; else out:= [op(out), [op(tout[ i ]), 0], [op(tout[ i ]), 1], [op(tout[ i ]), 2]]; end if; end do; return(out); end: count:=proc( lst, val ); return nops(select(x-> x=val, lst)); end: nops(select(w->count(w, 1)>=count(w, 2), select(w-> count(w, 0)>=count(w, 1), makeabababavoiders(5))));
# second Maple program
a:= n-> add (add (w (na, nb, n-na-nb, 0, 0),
        nb=ceil((n-na)/2)..min(n-na, na)), na=ceil(n/3)..n):
w:= proc(a, b, c, x, y) option remember;
      `if`([a, b, c]=[0$3], 1, `if`(a>0 and x<2, w(a-1, b, c, 1,
      `if`(y=1, 2, 0)), 0)+ `if`(b>0 and y<2, w(a, b-1, c,
      `if`(x=1, 2, 0), 1), 0)+ `if`(c>0, w(a, b, c-1, 0, 0), 0))
    end:
seq (a(n), n=0..40);  # Alois P. Heinz, May 22 2012

Mathematica

a[n_] := Sum[Sum[w[na, nb, n - na - nb, 0, 0],
     {nb, Ceiling[(n - na)/2], Min[n - na, na]}], {na, Ceiling[n/3], n}];
w[a_, b_, c_, x_, y_] := w[a, b, c, x, y] =
     If[{a, b, c} == {0, 0, 0}, 1, If[a > 0 && x < 2, w[a - 1, b, c, 1,
     If[y == 1, 2, 0]], 0] + If[b > 0 && y < 2, w[a, b - 1, c,
     If[x == 1, 2, 0], 1], 0] + If[c > 0, w[a, b, c - 1, 0, 0], 0]];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 13 2022, after Alois P. Heinz *)

Crossrefs

Sequence in context: A262466 A128301 A348382 * A206701 A176354 A210337

Adjacent sequences: A176145 A176146 A176147 * A176149 A176150 A176151

Keyword

nonn

Author

Ginger Moorey (gingermoorey(AT)hotmail.com), Apr 10 2010

Extensions

Extended beyond a(11) by Alois P. Heinz, May 22 2012

Status

approved