A363181 - OEIS

%I #41 May 26 2023 08:17:12

%S 1,0,2,2,8,14,54,128,498,1426,5736,18814,78886,287296,1258018,4986402,

%T 22789000,96966318,461790998,2088374592,10343408786,49343711666,

%U 253644381032,1268995609502,6756470362374,35285321738624,194220286045506,1054759508543554

%N 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 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 Number of permutations of [n] having n occurrences of the 1-box pattern.

%H Alois P. Heinz, <a href="/A363181/b363181.txt">Table of n, a(n) for n = 0..803</a>

%H FindStat, <a href="http://www.findstat.org/StatisticsDatabase/St000064">St000064: The number of one-box pattern of a permutation</a>.

%H 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 a(n) = A346462(n,n).

%F a(n)/2 mod 2 = A011655(n-1) for n>=1.

%F 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 a(0) = 1: (), the empty permutation.

%e a(1) = 0.

%e a(2) = 2: 12, 21.

%e a(3) = 2: 123, 321.

%e a(4) = 8: 1234, 1243, 2134, 2143, 3412, 3421, 4312, 4321.

%e a(5) = 14: 12345, 12354, 12543, 21345, 21543, 32145, 32154, 34512, 34521, 45123, 45321, 54123, 54312, 54321.

%e 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 a:= proc(n) option remember; `if`(n<4, [1, 0, 2$2][n+1],

%p       3/2*a(n-1)+(n-3/2)*a(n-2)-(n-5/2)*a(n-3)+(n-4)*a(n-4))

%p     end:

%p seq(a(n), n=0..30);

%Y Main diagonal of A346462.

%Y Cf. A002464, A003274, A011655, A095816, A127697, A179957, A229730, A271212, A303586, A333833, A363236.

%K nonn

%O 0,3

%A _Alois P. Heinz_, May 19 2023