cp's OEIS Frontend

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

%I A239295 #34 Mar 29 2017 04:38:16
%S A239295 1,1,4,26,210,1897,18368,186636,1965414,21277685,235493544,2653779856,
%T A239295 30357956720,351719984280,4119552129280,48708104589368,
%U A239295 580682799531822,6973356315752445,84286657672243880,1024694111031383100,12522664914160322460,153762682439070435390
%N A239295 Number of words of length n over the alphabet {0,...,n-1} that avoid the pattern 123.
%H A239295 Alois P. Heinz, <a href="/A239295/b239295.txt">Table of n, a(n) for n = 0..800</a>
%F A239295 a(n) = Sum_{k=0..2} A245667(n,k).
%F A239295 a(n) ~ 3^(3*n-1/2) / (5^(3/2) * Pi * 2^(n-3) * n^2). - _Vaclav Kotesovec_, Sep 11 2014
%e A239295 a(0) = [].
%e A239295 a(1) = [0].
%e A239295 a(2) = [0,0], [0,1], [1,0], [1,1].
%e A239295 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].
%p A239295 a:= proc(n) option remember; `if`(n<3, [1, 1, 4][n+1],
%p A239295       ((7324*n^4-36350*n^3+58408*n^2-36126*n+8352) *a(n-1)
%p A239295       -3*(n-3)*(2083*n^3-5374*n^2+2979*n+816) *a(n-2)
%p A239295       -63*(n-3)*(n-4)*(3*n-7)*(3*n-8) *a(n-3)) /
%p A239295       (4*n*(n-2)*(n+1)*(127*n-261)))
%p A239295     end:
%p A239295 seq(a(n), n=0..25);  # _Alois P. Heinz_, Mar 15 2014
%t A239295 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]]}]];
%t A239295 A[n_, k_] := A[n, k] = If[k == 0, If[n == 0, 1, 0], b[n, Array[n&, k]]];
%t A239295 T[n_, k_] := A[n, k] - If[k == 0, 0, A[n, k-1]];
%t A239295 a[n_] := Sum[T[n, k], {k, 0, 2}];
%t A239295 Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Mar 29 2017, after _Alois P. Heinz_ (cf. A245667) *)
%Y A239295 Cf. A000108 (the permutation analog for 123-avoiding), A000312, A245667.
%K A239295 nonn
%O A239295 0,3
%A A239295 _Chad Brewbaker_, Mar 14 2014
%E A239295 a(8)-a(11) from _Giovanni Resta_, Mar 14 2014
%E A239295 a(12)-a(21) from _Alois P. Heinz_, Mar 15 2014