A095816 Number of permutations of 1..n with no three elements in correct or reverse order.

1, 1, 2, 4, 18, 92, 570, 4082, 33292, 304490, 3086890, 34357812, 416526730, 5463479106, 77094352076, 1164544912938, 18749754351338, 320544941916628, 5799226664694602, 110695180631374114, 2223242026407894732, 46868311165318977130, 1034758905785710599402

Offset: 0

Author

Jonas Wallgren, Jun 08 2004

Keywords

• nonn

Comments

Counts permutations with the property that no subsequence i(i+1)(i+2) or (i+2)(i+1)i occurs.

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200
• W. M. Dymacek and I. Lambert, Permutations Avoiding Runs of i, i+1, i+2 or i, i-1, i-2, J. Int. Seq. 14 (2011) # 11.1.6, Table 1.
• 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, A095817, A095818.

Cf. A165963, A165964, A078628. [From Isaac Lambert, Oct 07 2009]

Programs

PARI

seq(n)={my(m=3); 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 = 3. - Ivana Jovovic ( ivana121(AT)EUnet.yu ), Nov 11 2007

From Vaclav Kotesovec, May 26 2023: (Start)

a(n) ~ n! * (1 - 2/n + 6/n^2 - 28/(3*n^3) - 10/(3*n^4) + 496/(15*n^5) + 1384/(45*n^6) - 79724/(315*n^7) - 259306/(315*n^8) + 3718094/(2835*n^9) + 33233992/(2025*n^10) + ...).

a(n) = (n-3)*a(n-1) + 3*(n-1)*a(n-2) + (2*n-5)*a(n-3) - (n-3)*a(n-4) - (2*n-13)*a(n-5) - (n-8)*a(n-6) + (n-6)*a(n-7).

(End)

Extensions

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

a(0)=1 prepended by Max Alekseyev, Jun 14 2011