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

1, 1, 4, 27, 255, 3028, 41979, 647790, 10803237, 191122140, 3542732908, 68213661464, 1355643940248, 27673150807344, 578051855658450, 12318499151821116, 267156147212406393, 5884501351433388108, 131418738987996420708, 2971588663914996425000

Offset

0,3

Links

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

Alois P. Heinz, Maple program for A239299

Formula

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

a(n) ~ 2^(8*n-3/2) / (7^4 * Pi^(3/2) * n^(9/2) * 3^(2*n-9)). - Vaclav Kotesovec, Mar 20 2014

a(n) = Sum_{k=0..3} A245667(n,k). - Alois P. Heinz, Jul 31 2014

Maple

# for an efficient program see link above.
# for initial terms only:
b:= proc(n, s, u, t) option remember; `if`(n=0, 1,
      add(b(n-1, min(s, i), min(u, `if`(s<i, i, u)),
      min(t, `if`(u<i, i+1, t))), i=1..t-1))
    end:
a:= n-> b(n, n+1$3):
seq(a(n), n=0..20); # Alois P. Heinz, Mar 18 2014

Mathematica

b[n_, s_, u_, t_] := b[n, s, u, t] = If[n == 0, 1,
    Sum[b[n - 1, Min[s, i], Min[u, If[s < i, i, u]],
    Min[t, If[u < i, i + 1, t]]], {i, 1, t - 1}]];
a[n_] := b[n, n+1, n+1, n+1];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 40}] (* Jean-François Alcover, Dec 21 2020, after Alois P. Heinz *)

Crossrefs

The permutation analog is A005802.

Cf. A000312, A245667.

Sequence in context: A239380 A239379 A239298 * A239300 A239490 A239491

Adjacent sequences: A239296 A239297 A239298 * A239300 A239301 A239302

Keyword

nonn

Author

Chad Brewbaker, Mar 14 2014

Extensions

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

a(11)-a(19) from Alois P. Heinz, Mar 17 2014

Status

approved