|
|
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.
|
|
3
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
|
|
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:
|
|
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]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Ginger Moorey (gingermoorey(AT)hotmail.com), Apr 10 2010
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|