A239295 Number of words of length n over the alphabet {0,...,n-1} that avoid the pattern 123.

1, 1, 4, 26, 210, 1897, 18368, 186636, 1965414, 21277685, 235493544, 2653779856, 30357956720, 351719984280, 4119552129280, 48708104589368, 580682799531822, 6973356315752445, 84286657672243880, 1024694111031383100, 12522664914160322460, 153762682439070435390

Offset: 0

Author

Chad Brewbaker, Mar 14 2014

Keywords

• nonn

Examples

			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].
		

Links

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

Crossrefs

Cf. A000108 (the permutation analog for 123-avoiding), A000312, A245667.

Programs

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) *)

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

Extensions

a(8)-a(11) from Giovanni Resta, Mar 14 2014

a(12)-a(21) from Alois P. Heinz, Mar 15 2014