login
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.
2

%I #21 Nov 11 2020 08:42:29

%S 1,1,3,9,17,46,153,338,935,3067,7182,20064,64819,156968,441084,

%T 1408612,3488489,9840608,31145791,78388512,221722954,696757333,

%U 1775204952,5031253931,15718503073,40435757688,114779701466,356852697226,925209496348,2629513384131

%N 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.

%H Alois P. Heinz, <a href="/A176354/b176354.txt">Table of n, a(n) for n = 0..200</a>

%p a:= n-> add(add(w(na, nb, n-na-nb, 0),

%p nb=ceil((n-na)/2)..min(n-na, na)), na=ceil(n/3)..n):

%p w:= proc(a, b, c, x) option remember;

%p `if`([a, b, c]=[0$3], 1, `if`(a>0 and x<2, w(a-1, b, c, 1), 0)+

%p `if`(b>0, w(a, b-1, c, `if`(x=1, 2, 0)), 0)+

%p `if`(c>0, w(a, b, c-1, 0), 0))

%p end:

%p seq(a(n), n=0..40); # _Alois P. Heinz_, May 22 2012

%t a[n_] := Sum[Sum[w[na, nb, n - na - nb, 0], {nb, Ceiling[(n - na)/2], Min[n - na, na]}], {na, Ceiling[n/3], n}];

%t w[a_, b_, c_, x_] := w[a, b, c, x] = If[{a, b, c} == {0, 0, 0}, 1, If[a > 0 && x < 2, w[a - 1, b, c, 1], 0] + If[b > 0, w[a, b - 1, c, If[x == 1, 2, 0]], 0] + If[c > 0, w[a, b, c - 1, 0], 0]];

%t a /@ Range[0, 40] (* _Jean-François Alcover_, Nov 11 2020, after _Alois P. Heinz_ *)

%o (Sage)

%o def atleastcond(w):

%o return w.count(0) >= w.count(1) >= w.count(2)

%o def avoidsaba(w):

%o for i in range(len(w)-2):

%o if w[i] == 0 and w[i+1] == 1 and w[i+2] == 0:

%o return False

%o return True

%o len([w for w in Words([0,1,2], length=6) if atleastcond(w) and avoidsaba(w)])

%o # Jenny Li (jiemi2007(AT)yahoo.ca), Apr 17 2010

%Y Cf. A176148, A206701.

%K nonn

%O 0,3

%A Jenny Li (jiemi2007(AT)yahoo.ca), Apr 15 2010, Apr 17 2010

%E Extended beyond a(15) by _Alois P. Heinz_, May 22 2012