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
Alois P. Heinz, Table of n, a(n) for n = 0..803
S. Kitaev, J. Remmel, The 1-box pattern on pattern avoiding permutations, arXiv:1305.6970 [math.CO], 2013.
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