login
A363656
Number of bounded affine permutations of size n.
1
1, 3, 13, 87, 761, 8243, 106037, 1578671, 26685361, 504770859, 10562259533, 242216304839, 6040459572681, 162750100464643, 4711225866217381, 145818462291970911, 4805369568409107809, 167982555421167341147, 6208589923091273031293, 241898639921607255506039
OFFSET
1,2
COMMENTS
An affine permutation of size n is a bijection p from the integers to the integers that satisfies (1) p(i+n) = p(i) + n for all i and (2) Sum_{i=1..n} p(i) = Sum_{i=1..n} i. A bounded affine permutation of size n is an affine permutation of size n that satisfies (3) |p(i) - i| < n for all i.
LINKS
N. Madras and J. M. Troyka, Bounded affine permutations I. Pattern avoidance and enumeration, Discrete Math. Theor. Comput. Sci. 22(2) (2021), #1.
N. Madras and J. M. Troyka, Bounded affine permutations II. Avoidance of decreasing patterns, Ann. Comb. 25 (2021), 1007-1048.
FORMULA
a(n) = Sum_{m=0..n} binomial(n,m) Sum_{k=0..m} binomial(m,k) A046739(m,k) (Madras and Troyka I, Thm. 38(a)).
a(n) = Sum_{m=0..n} binomial(n,m) Sum_{k=0..m} binomial(m,n-k) (-1)^(n-m) A173018(m,k) (Madras and Troyka I, Thm. 38(b)).
a(n) ~ sqrt[3/(2*pi*e)] n^(-1/2) 2^n n! (Madras and Troyka I, Thm. 45).
EXAMPLE
Let [a,b] denote the affine permutation p of size 2 determined by p(1) = a and p(2) = b.
The 3 bounded affine permutations of size 2 are [1,2], [2,1], and [0,3], so a(2) = 3.
CROSSREFS
Sequence in context: A167810 A331646 A054420 * A300701 A174278 A352121
KEYWORD
nonn
AUTHOR
Justin M. Troyka, Jun 14 2023
STATUS
approved