|
| |
|
|
A177840
|
|
Consider the n pairs (1,2), ..., (2n-1,2n); a(n) is the number of permutations of [ 2n ] with no two fixed points for any pair.
|
|
2
|
|
|
|
1, 1, 21, 653, 37577, 3434169, 457819549, 83900098309, 20238575173137, 6217167231292913, 2369809434953636261, 1097587512530348834301, 607119566298408076479961, 395312612701784187384578473, 299298318246814086742418737197, 260721599469397754183307347278709
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Inverse binomial transform of (2n)!. - Peter Luschny, May 31 2014
Also, the number of permutations of [2n] with no two cycle (2i-1,2i) for any pair. The number of permutation where no such pair is exchanged or fixed pointwise is A116218. - Aaron Meyerowitz, Jul 22 2023
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = Sum_{j=0..n} C(n,j) * 2^j * f(2*n-j), where f(n) is the number of permutations of [n] with no fixed-points (A000166).
a(n) = A(n,0), with A(n,s) = number of permutations of [2n] with exactly s pairs with 2 fixed points:
A(n,s) = (n!/s!) * Sum_{j=0..n-s} 1/(j!*(n-s-j)!) * 2^j * f(2*(n-s)-j).
A(n,n) = 1, A(n,n-1) = n, A(n,n-2) = 21*n!/(2*(n-2)!).
Sum_{s=0..n} A(n,s) = (2*n)!.
a(n) = Sum_{j=0..n} C(n,j)*(2*n-2*j)!*(-1)^j. - Tani Akinari, Feb 01 2015
A(n,s) = Sum_{j=s..n} C(n,j)*C(j,s)*(2*n-2*j)!*(-1)^(j-s). - Tani Akinari, Feb 01 2015
a(n) = Integral_{x = 0..oo} (x^2 - 1)^n*exp(-x) dx.
For n >= 1, Integral_{x = 0..1} (x^2 - 1)^n*exp(x) dx = A007060(n)*e - a(n). Hence lim_{n->oo} a(n)/A007060(n) = e.
O.g.f. with a(0) := 1: Sum_{k >= 0} (2*k)!*x^k/(1 + x)^(k + 1) = 1 + x + 21*x^2 + 653*x^3 + ....
a(n) = 2*n*(2*n - 1)*a(n-1) + 4*n*(n - 1)*a(n-2) + (-1)^n, with initial conditions a(0) = 1, a(1) = 1.
Homogeneous recurrence: a(n) = (4*n^2 - 2*n - 1)*a(n-1) + 2*(n - 1)*(4*n - 3)*a(n-2) + 4*(n - 1)*(n - 2)*a(n-3), with initial conditions a(0) = 1, a(1) = 1 and a(2) = 21. Cf. A064570. (End)
a(n) ~ sqrt(Pi) * 2^(2*n+1) * n^(2*n + 1/2) / exp(2*n). - Vaclav Kotesovec, Mar 10 2015
a(n) = (2*n)!*hypergeom([],[1/2-n],1/4)+(-1)^n*(1-hypergeom([1],[1/2,n+1],1/4)). - Peter Luschny, Mar 15 2015
|
|
|
EXAMPLE
|
a(2) = 21, because there are 4! = 24 permutations of [ 4 ], only 3 of them have pairs with 2 fixed points: [1,2,3,4], [1,2,4,3], [2,1,3,4].
a(3) = A(3,0) = 653, A(3,1) = 63, A(3,2) = 3, A(3,4) = 1, sum = 720 = 6!.
|
|
|
MAPLE
|
f:= proc(n) option remember;
`if`(n<2, 1-n, (n-1) *(f(n-1)+f(n-2)))
end:
a:= n-> add(binomial(n, j) *2^j *f(2*n-j), j=0..n):
|
|
|
MATHEMATICA
|
f[n_] := f[n] = If[n<2, 1-n, (n-1)*(f[n-1]+f[n-2])]; a[n_] := Sum[Binomial[ n, j]*2^j*f[2*n-j], {j, 0, n}]; Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Feb 25 2017, after Alois P. Heinz *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
