login
Number of key permutations of length n: permutations {a_i} with |a_i - a_{i-1}| = 1 or 2.
(Formerly M1583)
18

%I M1583 #65 Nov 27 2024 12:41:33

%S 1,1,2,6,12,20,34,56,88,136,208,314,470,700,1038,1534,2262,3330,4896,

%T 7192,10558,15492,22724,33324,48860,71630,105002,153912,225594,330650,

%U 484618,710270,1040980,1525660,2235994,3277040,4802768,7038832,10315944,15118786

%N Number of key permutations of length n: permutations {a_i} with |a_i - a_{i-1}| = 1 or 2.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A003274/b003274.txt">Table of n, a(n) for n = 0..2000</a> (first 251 terms from R. H. Hardin)

%H S. Avgustinovich and S. Kitaev, <a href="https://doi.org/10.1016/j.disc.2007.03.079">On uniquely k-determined permutations</a>, Discr. Math., 308 (2008), 1500-1507.

%H Hugh Denoncourt, <a href="https://arxiv.org/abs/1907.07172">Ordinal pattern probabilities for symmetric random walks</a>, arXiv:1907.07172 [math.CO], 2019.

%H E. S. Page, <a href="https://doi.org/10.1093/comjnl/14.2.150">Systematic generation of ordered sequences using recurrence relations</a>, Computer J., 14 (1971), 150-153.

%H E. S. Page, <a href="/A003274/a003274.pdf">Systematic generation of ordered sequences using recurrence relations</a>, The Computer Journal 14 (1971), 150-153. (Annotated scanned copy)

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,2,-2,1).

%F For n > 1, a(n) = 2*A069241(n).

%F G.f.: -(x^6 - x^5 + x^3 + 2*x^2 - 2*x + 1)/((x^3 + x - 1)*(x-1)^2).

%F Limit_{n->oo} a(n+1)/a(n) = A092526 = 1/A263719. - _Alois P. Heinz_, Apr 15 2018

%p 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.]

%t 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 *)

%Y Cf. A069241, A092526, A174700, A263719, A302118.

%K nonn,easy,changed

%O 0,3

%A _N. J. A. Sloane_

%E Better description and g.f. from _Erich Friedman_

%E a(0)=1 prepended and g.f. adapted by _Alois P. Heinz_, Apr 01 2018