cp's OEIS Frontend

A239299 Number of words of length n over the alphabet {0,...,n-1} that are 1234-avoiding.

%I A239299 #32 Dec 21 2020 11:57:16
%S A239299 1,1,4,27,255,3028,41979,647790,10803237,191122140,3542732908,
%T A239299 68213661464,1355643940248,27673150807344,578051855658450,
%U A239299 12318499151821116,267156147212406393,5884501351433388108,131418738987996420708,2971588663914996425000
%N A239299 Number of words of length n over the alphabet {0,...,n-1} that are 1234-avoiding.
%H A239299 Alois P. Heinz, <a href="/A239299/b239299.txt">Table of n, a(n) for n = 0..500</a>
%H A239299 Alois P. Heinz, <a href="/A239299/a239299.txt">Maple program for A239299</a>
%F A239299 Recurrence (of order 3): 9*(n-3)^2*(n-2)*n*(n+2)^2*(1057*n^7 - 19522*n^6 + 153671*n^5 - 668749*n^4 + 1738472*n^3 - 2700169*n^2 + 2319664*n - 849696)*a(n) = (n-3)*(327670*n^12 - 7739849*n^11 + 80785028*n^10 - 489037999*n^9 + 1890857973*n^8 - 4828424052*n^7 + 8060049557*n^6 - 8146857268*n^5 + 3520960348*n^4 + 1831667104*n^3 - 3220309536*n^2 + 1597874688*n - 295612416)*a(n-1) - (n-4)*(1633065*n^12 - 41573919*n^11 + 478203433*n^10 - 3285690086*n^9 + 15017055239*n^8 - 48092317343*n^7 + 110651362619*n^6 - 184276357364*n^5 + 220420044268*n^4 - 184591308504*n^3 + 102631197456*n^2 - 33947092224*n + 5033249280)*a(n-2) + 8*(n-5)*(n-4)^2*(2*n-5)*(4*n-11)*(4*n-9)*(1057*n^7 - 12123*n^6 + 58736*n^5 - 156229*n^4 + 246741*n^3 - 231170*n^2 + 118368*n - 25272)*a(n-3). - _Vaclav Kotesovec_, Mar 20 2014
%F A239299 a(n) ~ 2^(8*n-3/2) /  (7^4 * Pi^(3/2) * n^(9/2) * 3^(2*n-9)). - _Vaclav Kotesovec_, Mar 20 2014
%F A239299 a(n) = Sum_{k=0..3} A245667(n,k). - _Alois P. Heinz_, Jul 31 2014
%p A239299 # for an efficient program see link above.
%p A239299 # for initial terms only:
%p A239299 b:= proc(n, s, u, t) option remember; `if`(n=0, 1,
%p A239299       add(b(n-1, min(s, i), min(u, `if`(s<i, i, u)),
%p A239299       min(t, `if`(u<i, i+1, t))), i=1..t-1))
%p A239299     end:
%p A239299 a:= n-> b(n, n+1$3):
%p A239299 seq(a(n), n=0..20); # _Alois P. Heinz_, Mar 18 2014
%t A239299 b[n_, s_, u_, t_] := b[n, s, u, t] = If[n == 0, 1,
%t A239299     Sum[b[n - 1, Min[s, i], Min[u, If[s < i, i, u]],
%t A239299     Min[t, If[u < i, i + 1, t]]], {i, 1, t - 1}]];
%t A239299 a[n_] := b[n, n+1, n+1, n+1];
%t A239299 Table[Print[n, " ", a[n]]; a[n], {n, 0, 40}] (* _Jean-François Alcover_, Dec 21 2020, after _Alois P. Heinz_ *)
%Y A239299 The permutation analog is A005802.
%Y A239299 Cf. A000312, A245667.
%K A239299 nonn
%O A239299 0,3
%A A239299 _Chad Brewbaker_, Mar 14 2014
%E A239299 a(8)-a(10) from _Giovanni Resta_, Mar 14 2014
%E A239299 a(11)-a(19) from _Alois P. Heinz_, Mar 17 2014