login
A206701
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 and no subwords (any nonadjacent subsequence of letters) of the form cbc.
2
1, 1, 3, 9, 17, 46, 114, 262, 574, 1427, 2927, 6603, 14404, 30565, 63613, 138813, 280318, 587475, 1218642, 2483850, 5029611, 10412477, 20733046, 42016631, 84910771, 169447050, 337521488, 680231390, 1340806837, 2667729672, 5306731496, 10458274889, 20608397551
OFFSET
0,3
LINKS
EXAMPLE
a(0) = 1: "".
a(1) = 1: "a".
a(2) = 3: "aa", "ab", "ba".
a(3) = 9: "aaa", "aab", "abc", "acb", "baa", "bac", "bca", "cab", "cba".
G.f. = 1 + x + 3*x^2 + 9*x^3 + 17*x^4 + 46*x^5 + 114*x^6 + 262*x^7 + ...
MAPLE
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, y), 0)+
`if`(b>0, w(a, b-1, c, `if`(x=1, 2, 0), `if`(y>0, 2, 0)), 0)+
`if`(c>0 and y<>2, w(a, b, c-1, 0, 1), 0))
end:
seq(a(n), n=0..40); # Alois P. Heinz, May 21 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, y], 0] + If[b > 0, w[a, b - 1, c, If[x == 1, 2, 0], If[y > 0, 2, 0]], 0] + If[c > 0 && y != 2, w[a, b, c - 1, 0, 1], 0]];
a /@ Range[0, 40] (* Jean-François Alcover, Nov 12 2020, after Alois P. Heinz *)
PROG
(Sage)
def myavoids(w):
v = w.count(2)
if w.count(1)<v or v<w.count(3):
return False
else:
return Word([1, 2, 1]).nb_factor_occurrences_in(w)==0 and Word([3, 2, 3]).nb_subword_occurrences_in(w)==0
for n in range(30):
print(len([w for w in Words(3, length=n) if myavoids(w)]))
CROSSREFS
Sequence in context: A128301 A348382 A176148 * A176354 A210337 A173140
KEYWORD
nonn
AUTHOR
Grazia Barone, Feb 11 2012
EXTENSIONS
Extended beyond a(15) by Alois P. Heinz, May 21 2012
STATUS
approved