|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|