cp's OEIS Frontend

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.

%I A177840 #69 Jul 23 2023 07:32:37
%S A177840 1,1,21,653,37577,3434169,457819549,83900098309,20238575173137,
%T A177840 6217167231292913,2369809434953636261,1097587512530348834301,
%U A177840 607119566298408076479961,395312612701784187384578473,299298318246814086742418737197,260721599469397754183307347278709
%N 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.
%C A177840 Inverse binomial transform of (2n)!. - _Peter Luschny_, May 31 2014
%C A177840 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
%H A177840 Alois P. Heinz, <a href="/A177840/b177840.txt">Table of n, a(n) for n = 0..224</a>
%H A177840 Paul Weisenhorn, <a href="/A177840/a177840.txt">First 10 rows of permutation numbers A(n,s) with s=0..n, formatted as a simple linear sequence n, a(n)</a>
%F A177840 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).
%F A177840 a(n) = A(n,0), with A(n,s) = number of permutations of [2n] with exactly s pairs with 2 fixed points:
%F A177840 A(n,s) = (n!/s!) * Sum_{j=0..n-s} 1/(j!*(n-s-j)!) * 2^j * f(2*(n-s)-j).
%F A177840 A(n,n) = 1, A(n,n-1) = n, A(n,n-2) = 21*n!/(2*(n-2)!).
%F A177840 Sum_{s=0..n} A(n,s) = (2*n)!.
%F A177840 a(n) = Sum_{j=0..n} C(n,j)*(2*n-2*j)!*(-1)^j. - _Tani Akinari_, Feb 01 2015
%F A177840 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
%F A177840 From _Peter Bala_, Mar 07 2015: (Start)
%F A177840 a(n) = Integral_{x = 0..oo} (x^2 - 1)^n*exp(-x) dx.
%F A177840 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.
%F A177840 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 + ....
%F A177840 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.
%F A177840 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)
%F A177840 a(n) ~ sqrt(Pi) * 2^(2*n+1) * n^(2*n + 1/2) / exp(2*n). - _Vaclav Kotesovec_, Mar 10 2015
%F A177840 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
%e A177840 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].
%e A177840 a(3) = A(3,0) = 653, A(3,1) = 63, A(3,2) = 3, A(3,4) = 1, sum = 720 = 6!.
%p A177840 f:= proc(n) option remember;
%p A177840       `if`(n<2, 1-n, (n-1) *(f(n-1)+f(n-2)))
%p A177840     end:
%p A177840 a:= n-> add(binomial(n,j) *2^j *f(2*n-j), j=0..n):
%p A177840 seq(a(n), n=0..20);  # _Alois P. Heinz_, Sep 06 2011
%t A177840 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_ *)
%Y A177840 Cf. A000166, A064570, A007060, A053983, A053984, A116218.
%K A177840 nonn,easy
%O A177840 0,3
%A A177840 _Paul Weisenhorn_, May 14 2010
%E A177840 b-file changed to a-file by _N. J. A. Sloane_, Oct 05 2010
%E A177840 Edited by _Alois P. Heinz_, Sep 06 2011
%E A177840 a(0)=1 prepended by _Alois P. Heinz_, Jul 23 2023