A382645 Number of king permutations on n elements not beginning with the smallest element and not ending with the largest element.

1, 0, 0, 0, 2, 10, 68, 500, 4174, 38774, 397584, 4462848, 54455754, 717909202, 10171232060, 154142811052, 2488421201446, 42636471916622, 772807552752712, 14774586965277816, 297138592463202402, 6271277634164008170, 138596853553771517492, 3200958202120445923684, 77114612783976599209598

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 and do not end with the largest element.

Links

Table of n, a(n) for n=0..24.

Dan Li and Philip B. Zhang, Distributions of mesh patterns of short lengths on king permutations, arXiv:2411.18131 [math.CO], 2024. See formula (3) at page 5.

Formula

G.f.: t/(1+t) + Sum_{n >= 0} n!*t^n*(1-t)^n/(1+t)^(n+2).

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) = 10 solutions are these 10 permutations: 24153, 25314, 31524, 35142, 35241, 41352, 42513, 42531, 52413, and 53142.

Mathematica

nmax = 20; CoefficientList[Series[x/(1+x) + Sum[k!*x^k*(1-x)^k/(1+x)^(k+2), {k, 0, nmax}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Apr 04 2025 *)

Prog

(PARI) my(N=30, t='t+O('t^N)); Vec(t/(1+t)+sum(n=0, N, n!*t^n*(1-t)^n/(1+t)^(n+2))) \\ Joerg Arndt, Apr 03 2025

Crossrefs

Cf. A002464, A382644.

Sequence in context: A152621 A383434 A382651 * A147725 A074603 A110520

Adjacent sequences: A382642 A382643 A382644 * A382646 A382647 A382648

Keyword

nonn

Author

Dan Li, Apr 01 2025

Status

approved