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.

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

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

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

Cf. A176148, A176354.

Sequence in context: A128301 A348382 A176148 * A176354 A210337 A173140

Adjacent sequences: A206698 A206699 A206700 * A206702 A206703 A206704

Keyword

nonn

Author

Grazia Barone, Feb 11 2012

Extensions

Extended beyond a(15) by Alois P. Heinz, May 21 2012

Status

approved