A382644 Number of king permutations on n elements not beginning with the smallest element.

1, 0, 0, 0, 2, 12, 78, 568, 4674, 42948, 436358, 4860432, 58918602, 772364956, 10889141262, 164314043112, 2642564012498, 45124893118068, 815444024669334, 15547394518030528, 311913179428480218, 6568416226627210572, 144868131187935525662, 3339555055674217441176, 80315570986097045133282

Offset: 0

Author

Dan Li, Apr 01 2025

Keywords

• nonn
• easy

Comments

A permutation p(1)p(2)...p(n) is a king permutation if |p(i+1)-p(i)|>1 for each 0

Examples

			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.
		

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.

Crossrefs

Cf. A001266, A002464, A382645.

Programs

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

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

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.