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,3

Links

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

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

Adjacent sequences: A239292 A239293 A239294 * A239296 A239297 A239298

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