cp's OEIS Frontend

A363181 Number of permutations p of [n] such that for each i in [n] we have: (i>1) and |p(i)-p(i-1)| = 1 or (i and |p(i)-p(i+1)| = 1.

%I A363181 #43 Feb 07 2025 12:02:10
%S A363181 1,0,2,2,8,14,54,128,498,1426,5736,18814,78886,287296,1258018,4986402,
%T A363181 22789000,96966318,461790998,2088374592,10343408786,49343711666,
%U A363181 253644381032,1268995609502,6756470362374,35285321738624,194220286045506,1054759508543554
%N A363181 Number of permutations p of [n] such that for each i in [n] we have: (i>1) and |p(i)-p(i-1)| = 1 or (i<n) and |p(i)-p(i+1)| = 1.
%C A363181 Number of permutations p of [n] such that each element in p has at least one neighbor whose value is smaller or larger by one.
%C A363181 Number of permutations of [n] having n occurrences of the 1-box pattern.
%H A363181 Alois P. Heinz, <a href="/A363181/b363181.txt">Table of n, a(n) for n = 0..803</a>
%H A363181 FindStat, <a href="http://www.findstat.org/StatisticsDatabase/St000064">St000064: The number of one-box pattern of a permutation</a>.
%H A363181 S. Kitaev, J. Remmel, <a href="http://www.arxiv.org/abs/1305.6970">The 1-box pattern on pattern avoiding permutations</a>, arXiv:1305.6970 [math.CO], 2013.
%F A363181 a(n) = A346462(n,n).
%F A363181 a(n)/2 mod 2 = A011655(n-1) for n>=1.
%F A363181 a(n) ~ sqrt(Pi) * n^((n+1)/2) / (2 * exp(n/2 - sqrt(n)/2 + 7/16)) * (1 - 119/(192*sqrt(n))). - _Vaclav Kotesovec_, May 26 2023
%e A363181 a(0) = 1: (), the empty permutation.
%e A363181 a(1) = 0.
%e A363181 a(2) = 2: 12, 21.
%e A363181 a(3) = 2: 123, 321.
%e A363181 a(4) = 8: 1234, 1243, 2134, 2143, 3412, 3421, 4312, 4321.
%e A363181 a(5) = 14: 12345, 12354, 12543, 21345, 21543, 32145, 32154, 34512, 34521, 45123, 45321, 54123, 54312, 54321.
%e A363181 a(6) = 54: 123456, 123465, 123654, 124356, 124365, 125634, 125643, 126534, 126543, 213456, 213465, 214356, 214365, 215634, 215643, 216534, 216543, 321456, 321654, 341256, 341265, 342156, 342165, 345612, 345621, 346512, 346521, 431256, 431265, 432156, 432165, 435612, 435621, 436512, 436521, 456123, 456321, 561234, 561243, 562134, 562143, 563412, 563421, 564312, 564321, 651234, 651243, 652134, 652143, 653412, 653421, 654123, 654312, 654321.
%p A363181 a:= proc(n) option remember; `if`(n<4, [1, 0, 2$2][n+1],
%p A363181       3/2*a(n-1)+(n-3/2)*a(n-2)-(n-5/2)*a(n-3)+(n-4)*a(n-4))
%p A363181     end:
%p A363181 seq(a(n), n=0..30);
%Y A363181 Main diagonal of A346462.
%Y A363181 Cf. A002464, A003274, A011655, A095816, A127697, A179957, A229730, A271212, A211694, A333833, A363236.
%K A363181 nonn
%O A363181 0,3
%A A363181 _Alois P. Heinz_, May 19 2023