cp's OEIS Frontend

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

%I A382644 #28 Apr 15 2025 15:19:14
%S A382644 1,0,0,0,2,12,78,568,4674,42948,436358,4860432,58918602,772364956,
%T A382644 10889141262,164314043112,2642564012498,45124893118068,
%U A382644 815444024669334,15547394518030528,311913179428480218,6568416226627210572,144868131187935525662,3339555055674217441176,80315570986097045133282
%N A382644 Number of king permutations on n elements not beginning with the smallest element.
%C A382644 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.
%H A382644 Alois P. Heinz, <a href="/A382644/b382644.txt">Table of n, a(n) for n = 0..450</a>
%H A382644 Dan Li and Philip B. Zhang, <a href="https://arxiv.org/abs/2411.18131">Distributions of mesh patterns of short lengths on king permutations</a>, arXiv:2411.18131 [math.CO], 2024. See formula (2) at page 5.
%F A382644 G.f.: Sum_{n >= 0} n!*t^n*(1-t)^n/(1+t)^(n+1).
%F A382644 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
%F A382644 a(n) ~ exp(-2) * n!. - _Vaclav Kotesovec_, Apr 04 2025
%e A382644 For n = 4 the a(4) = 2 solutions are the two permutations 2413 and 3142.
%e A382644 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.
%p A382644 a:= proc(n) option remember; `if`(n<4, [1,0$3][n+1],
%p A382644       (n+1)*a(n-1)-(n-3)*(a(n-2)+a(n-3))+(n-2)*a(n-4))
%p A382644     end:
%p A382644 seq(a(n), n=0..24);  # _Alois P. Heinz_, Apr 04 2025
%t A382644 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 *)
%o A382644 (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
%Y A382644 Cf. A001266, A002464, A382645.
%K A382644 nonn,easy
%O A382644 0,5
%A A382644 _Dan Li_, Apr 01 2025