OFFSET
0,5
COMMENTS
A permutation p(1)p(2)...p(n) is a king permutation if |p(i+1)-p(i)|>1 for each 0<i<n. a(n) counts king permutations of length n that do not begin with the smallest element.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..450
Dan Li and Philip B. Zhang, Distributions of mesh patterns of short lengths on king permutations, arXiv:2411.18131 [math.CO], 2024. See formula (2) at page 5.
FORMULA
G.f.: Sum_{n >= 0} n!*t^n*(1-t)^n/(1+t)^(n+1).
a(n) = (n+1)*a(n-1) - (n-3)*(a(n-2)+a(n-3)) + (n-2)*a(n-4) for n>=4. - Alois P. Heinz, Apr 04 2025
a(n) ~ exp(-2) * n!. - Vaclav Kotesovec, Apr 04 2025
EXAMPLE
For n = 4 the a(4) = 2 solutions are the two permutations 2413 and 3142.
For n = 5 the a(5) = 12 solutions are these 12 permutations: 24135, 24153, 25314, 31425, 31524, 35142, 35241, 41352, 42513, 42531, 52413, and 53142.
MAPLE
a:= proc(n) option remember; `if`(n<4, [1, 0$3][n+1],
(n+1)*a(n-1)-(n-3)*(a(n-2)+a(n-3))+(n-2)*a(n-4))
end:
seq(a(n), n=0..24); # Alois P. Heinz, Apr 04 2025
MATHEMATICA
nmax = 20; CoefficientList[Series[Sum[k!*x^k*(1-x)^k/(1+x)^(k+1), {k, 0, nmax}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Apr 04 2025 *)
PROG
(PARI) my(N=30, t='t+O('t^N)); Vec(sum(n=0, N, n!*t^n*(1-t)^n/(1+t)^(n+1))) \\ Joerg Arndt, Apr 03 2025
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Dan Li, Apr 01 2025
STATUS
approved