A095818 Number of permutations of 1..n with no five elements in correct or reverse order.

1, 1, 2, 6, 24, 118, 714, 5012, 40164, 361872, 3621366, 39854930, 478427452, 6221137644, 87112280208, 1306869108686, 20912175669082, 355537064658852, 6400095163337508, 121608318630457872, 2432271817858395382, 51079520016325649394, 1123782363517325646716

Offset: 0

Author

Jonas Wallgren, Jun 08 2004

Keywords

• nonn

Comments

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

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. A002464, A095816, A095817.

Programs

PARI

seq(n)={my(m=5); 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

Formula

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

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