A132647 Number of permutations of [n] having no substring [k,k+1,k+2,k+3].

1, 1, 2, 6, 23, 117, 706, 4962, 39817, 359171, 3597936, 39630372, 476066277, 6194080387, 86776390796, 1302376048620, 20847721870931, 354549730559949, 6384006047649910, 121330369923079290, 2427196999663678987, 50981866833670160201, 1121806937829102793662

Offset: 0

Author

Ivana Jovovic (ivana121(AT)EUnet.yu), Nov 14 2007

Keywords

• nonn

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200
• D. M. Jackson and R. C. Read, A note on permutations without runs of given length, Aequationes Math. 17 (1978), no. 2-3, 336-343.

Crossrefs

Cf. A000255, A002628.

Programs

PARI

seq(n)={Vec(sum(k=0, n, k!*((x^4-x)/(x^4-1) + O(x*x^n))^k))} \\ Andrew Howroyd, Aug 31 2018

Formula

G.f.: Sum_{n>=0} n!*((x^m-x)/(x^m-1))^n where m = 4.

a(n) ~ n! * (1 - 1/n^2 + 1/n^3 + 9/(2*n^4) + 7/n^5 - 55/(6*n^6) - 114/n^7 - 11419/(24*n^8) - 970/n^9 + 345199/(120*n^10) + ...). - Vaclav Kotesovec, Feb 17 2024

Extensions

Terms a(16) and beyond from Andrew Howroyd, Aug 31 2018