A003274 Number of key permutations of length n: permutations {a_i} with |a_i - a_{i-1}| = 1 or 2.
1, 1, 2, 6, 12, 20, 34, 56, 88, 136, 208, 314, 470, 700, 1038, 1534, 2262, 3330, 4896, 7192, 10558, 15492, 22724, 33324, 48860, 71630, 105002, 153912, 225594, 330650, 484618, 710270, 1040980, 1525660, 2235994, 3277040, 4802768, 7038832, 10315944, 15118786
Offset: 0
References
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..2000 (first 251 terms from R. H. Hardin)
- S. Avgustinovich and S. Kitaev, On uniquely k-determined permutations, Discr. Math., 308 (2008), 1500-1507.
- Hugh Denoncourt, Ordinal pattern probabilities for symmetric random walks, arXiv:1907.07172 [math.CO], 2019.
- E. S. Page, Systematic generation of ordered sequences using recurrence relations, Computer J., 14 (1971), 150-153.
- E. S. Page, Systematic generation of ordered sequences using recurrence relations, The Computer Journal 14 (1971), 150-153. (Annotated scanned copy)
- Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
- Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
- Index entries for linear recurrences with constant coefficients, signature (3,-3,2,-2,1).
Programs
-
Maple
A003274:=-(1-z+3*z**2-2*z**3+z**5)/(z**3+z-1)/(z-1)**2; # [Conjectured by Simon Plouffe in his 1992 dissertation.]
-
Mathematica
CoefficientList[Series[-(x^6 - x^5 + x^3 + 2 x^2 - 2 x + 1)/((x^3 + x - 1) (x - 1)^2), {x, 0, 39}], x] (* Michael De Vlieger, Oct 01 2019 *)
Formula
For n > 1, a(n) = 2*A069241(n).
G.f.: -(x^6 - x^5 + x^3 + 2*x^2 - 2*x + 1)/((x^3 + x - 1)*(x-1)^2).
Extensions
Better description and g.f. from Erich Friedman
a(0)=1 prepended and g.f. adapted by Alois P. Heinz, Apr 01 2018