login
A239295
Number of words of length n over the alphabet {0,...,n-1} that avoid the pattern 123.
17
1, 1, 4, 26, 210, 1897, 18368, 186636, 1965414, 21277685, 235493544, 2653779856, 30357956720, 351719984280, 4119552129280, 48708104589368, 580682799531822, 6973356315752445, 84286657672243880, 1024694111031383100, 12522664914160322460, 153762682439070435390
OFFSET
0,3
LINKS
FORMULA
a(n) = Sum_{k=0..2} A245667(n,k).
a(n) ~ 3^(3*n-1/2) / (5^(3/2) * Pi * 2^(n-3) * n^2). - Vaclav Kotesovec, Sep 11 2014
EXAMPLE
a(0) = [].
a(1) = [0].
a(2) = [0,0], [0,1], [1,0], [1,1].
a(3) = [0,0,0], [0,0,1], [0,0,2], [0,1,0], [0,1,1], [0,2,0], [0,2,1], [0,2,2], [1,0,0], [1,0,1], [1,0,2], [1,1,0], [1,1,1], [1,1,2], [1,2,0], [1,2,1], [1,2,2], [2,0,0], [2,0,1], [2,0,2], [2,1,0], [2,1,1], [2,1,2], [2,2,0], [2,2,1], [2,2,2].
MAPLE
a:= proc(n) option remember; `if`(n<3, [1, 1, 4][n+1],
((7324*n^4-36350*n^3+58408*n^2-36126*n+8352) *a(n-1)
-3*(n-3)*(2083*n^3-5374*n^2+2979*n+816) *a(n-2)
-63*(n-3)*(n-4)*(3*n-7)*(3*n-8) *a(n-3)) /
(4*n*(n-2)*(n+1)*(127*n-261)))
end:
seq(a(n), n=0..25); # Alois P. Heinz, Mar 15 2014
MATHEMATICA
b[n_, l_] := b[n, l] = If[n == 0, 1, Sum[b[n-1, Table[Min[l[[j]], If[j == 1 || l[[j-1]] < i, i, l[[j]]]], {j, 1, Length[l]}]], {i, 1, l[[-1]]}]];
A[n_, k_] := A[n, k] = If[k == 0, If[n == 0, 1, 0], b[n, Array[n&, k]]];
T[n_, k_] := A[n, k] - If[k == 0, 0, A[n, k-1]];
a[n_] := Sum[T[n, k], {k, 0, 2}];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 29 2017, after Alois P. Heinz (cf. A245667) *)
CROSSREFS
Cf. A000108 (the permutation analog for 123-avoiding), A000312, A245667.
Sequence in context: A228966 A291533 A363363 * A274735 A355379 A349719
KEYWORD
nonn
AUTHOR
Chad Brewbaker, Mar 14 2014
EXTENSIONS
a(8)-a(11) from Giovanni Resta, Mar 14 2014
a(12)-a(21) from Alois P. Heinz, Mar 15 2014
STATUS
approved