A363656 Number of bounded affine permutations of size n.

1, 3, 13, 87, 761, 8243, 106037, 1578671, 26685361, 504770859, 10562259533, 242216304839, 6040459572681, 162750100464643, 4711225866217381, 145818462291970911, 4805369568409107809, 167982555421167341147, 6208589923091273031293, 241898639921607255506039

Offset: 1

Author

Justin M. Troyka, Jun 14 2023

Keywords

• nonn

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.

Examples

			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.
		

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.

Crossrefs

Cf. A046739, A173018.

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).