A095817 Number of permutations of 1..n with no four elements in correct or reverse order.

1, 1, 2, 6, 22, 114, 692, 4884, 39318, 355490, 3567292, 39345804, 473148014, 6161310442, 86376341412, 1297099489668, 20772929663254, 353415786538434, 6365693021157116, 121016486728717740, 2421505946364174606, 50873034832373299370, 1119617627206173146308

Offset

0,3

Comments

For no k do either of the subsequences k(k+1)(k+2)(k+3) or (k+3)(k+2)(k+1)k occur in any permutation.

Links

Table of n, a(n) for n=0..22.

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.

Formula

G.f.: Sum_{n>=0} n!*((2*x^m-x^(m+1)-x)/(x^m-1))^n where m = 4. - Ivana Jovovic ( ivana121(AT)EUnet.yu ), Nov 11 2007

Prog

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

Crossrefs

Cf. A002464, A095816, A095818.

Sequence in context: A290279 A014371 A111280 * A370525 A352413 A101042

Adjacent sequences: A095814 A095815 A095816 * A095818 A095819 A095820

Keyword

nonn

Author

Jonas Wallgren, Jun 08 2004

Extensions

More terms from Ivana Jovovic ( ivana121(AT)EUnet.yu ), Nov 11 2007

a(0)=1 prepended and terms a(20) and beyond from Andrew Howroyd, Aug 31 2018

Status

approved