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
Alois P. Heinz, Table of n, a(n) for n = 1..404
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
KEYWORD
nonn
AUTHOR
Justin M. Troyka, Jun 14 2023
STATUS
approved