login
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.
5
1, 0, 2, 2, 8, 14, 54, 128, 498, 1426, 5736, 18814, 78886, 287296, 1258018, 4986402, 22789000, 96966318, 461790998, 2088374592, 10343408786, 49343711666, 253644381032, 1268995609502, 6756470362374, 35285321738624, 194220286045506, 1054759508543554
OFFSET
0,3
COMMENTS
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.
Number of permutations of [n] having n occurrences of the 1-box pattern.
LINKS
FORMULA
a(n) = A346462(n,n).
a(n)/2 mod 2 = A011655(n-1) for n>=1.
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
EXAMPLE
a(0) = 1: (), the empty permutation.
a(1) = 0.
a(2) = 2: 12, 21.
a(3) = 2: 123, 321.
a(4) = 8: 1234, 1243, 2134, 2143, 3412, 3421, 4312, 4321.
a(5) = 14: 12345, 12354, 12543, 21345, 21543, 32145, 32154, 34512, 34521, 45123, 45321, 54123, 54312, 54321.
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.
MAPLE
a:= proc(n) option remember; `if`(n<4, [1, 0, 2$2][n+1],
3/2*a(n-1)+(n-3/2)*a(n-2)-(n-5/2)*a(n-3)+(n-4)*a(n-4))
end:
seq(a(n), n=0..30);
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, May 19 2023
STATUS
approved