login
A095816
Number of permutations of 1..n with no three elements in correct or reverse order.
12
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,3
COMMENTS
Counts permutations with the property that no subsequence i(i+1)(i+2) or (i+2)(i+1)i occurs.
LINKS
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.
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)
PROG
(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
CROSSREFS
Cf. A165963, A165964, A078628. [From Isaac Lambert, Oct 07 2009]
Sequence in context: A295370 A292280 A120664 * A020101 A370524 A099938
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 by Max Alekseyev, Jun 14 2011
STATUS
approved