login
Number of partitions into pairs.
(Formerly M4241)
2

%I M4241 #52 Nov 14 2018 14:07:48

%S 1,1,6,41,365,3984,51499,769159,13031514,246925295,5173842311,

%T 118776068256,2964697094281,79937923931761,2315462770608870,

%U 71705109685449689,2364107330976587909,82676528225908987824,3056806370495613000259,119137361202296994159415

%N Number of partitions into pairs.

%C a(n) is the subset of the set of unordered pairings of the first 2n integers (A001147) forbidding pairs of the form (i,i+1) for all i in [2,n-1]. There are many other selections of forbidden pairs giving the same count. - _Olivier Gérard_, Feb 08 2011

%D G. Kreweras and Y. Poupard, Sur les partitions en paires d'un ensemble fini totalement ordonné, Publications de l'Institut de Statistique de l'Université de Paris, 23 (1978), 57-74.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Gheorghe Coserea, <a href="/A006198/b006198.txt">Table of n, a(n) for n = 1..201</a>

%H Simon Plouffe, <a href="http://arxiv.org/abs/0911.4975">Approximations of generating functions and a few conjectures</a>, arXiv:0911.4975 [math.NT], 2009.

%F a(n) = |A000806(n-1)|+|A000806(n)|. G.f.: Sum_{n>=0} A001147(n)*(x/(1+x)^2)^n. - _Vladeta Jovovic_, Jun 27 2007

%F Recurrence: (4*n^2-8*n+1)*a(n-1) + (2*n-1)*a(n-2) + (3-2*n)*a(n) = 0. - _Vaclav Kotesovec_, Oct 05 2012

%F G.f.: T(0) - 1, where T(k) = 1 - (k+1)*x/( (k+1)*x - (1+x)^2/T(k+1) ); (continued fraction). - _Sergei N. Gladkovskii_, Nov 03 2013

%F a(-n) = -a(n) for all n in Z. - _Michael Somos_, Jan 27 2014

%F a(n+1) = Sum_{k=0..n} (-1)^k * (2n+1-k)! / (2^(n-k) * k! * (n-k)!) if n>=0. - _Michael Somos_, Jan 27 2014

%F 0 = a(n) * (a(n+2) + a(n+3)) + a(n+1) * (-a(n+1) -3*a(n+2) -4*a(n+3) + a(n+4)) + a(n+2) * (-3*a(n+3) + a(n+4)) + a(n+3) * (-a(n+3)) for all n in Z. - _Michael Somos_, Jan 27 2014

%F E.g.f. (for offset 0): ((2 - 2*x - (1 - 2*x)^(1/2)) / (1-2*x)^(3/2)) * exp((1-2*x)^(1/2) - 1) (formula due to B. Salvy, see Plouffe link). - _Gheorghe Coserea_, Aug 05 2015

%F E.g.f. (for offset 1): exp(sqrt(1-2*x)-1) * (1/sqrt(1-2*x)-1). - _Vaclav Kotesovec_, Nov 29 2015

%F a(n) ~ 2^(n+1/2)*n^n/exp(n+1). - _Vaclav Kotesovec_, Nov 29 2015

%e G.f. = x + x^2 + 6*x^3 + 41*x^4 + 365*x^5 + 3984*x^6 + 51499*x^7 + ...

%t a[ n_] := With[ {m = Abs[n] - 1}, If[ m < 0, 0, Sign[n] Hypergeometric1F1[-m, -2 m - 1, -2] (2 m + 1)!!]]; (* _Michael Somos_, Jan 27 2014 *)

%t a[ n_] := With[ {m = Abs[n] - 1}, If[ m < 0, 0, Sign[n] Sum[ (-1)^k (2 m + 1 - k)! / (2^(m - k) k! (m - k)!), {k, 0, m}]]]; (* _Michael Somos_, Jan 27 2014 *)

%t a[ n_] := With[ {m = Abs[n] - 1}, If[ m < 0, 0, Sign[n] Numerator @ FromContinuedFraction[ Table[(-1)^Quotient[k, 2] If[ OddQ[k], k, 1], {k, 2 m + 1}]]]]; (* _Michael Somos_, Jan 27 2014 *)

%t Rest[CoefficientList[Series[E^(-1 + Sqrt[1 - 2*x])*(-1 + 1/Sqrt[1 - 2*x]), {x, 0, 20}], x] * Range[0, 20]!] (* _Vaclav Kotesovec_, Nov 29 2015 *)

%t Table[(2 n - 1)!! Hypergeometric1F1[1 - n, 1 - 2 n, -2], {n, 20}] (* _Eric W. Weisstein_, Nov 14 2018 *)

%o (PARI) {a(n) = sign(n) * if( n==0, 0, contfracpnqn( vector( 2*abs(n) -1, k, (-1)^(k\2) * if( k%2, k, 1))) [1,1]) }; /* _Michael Somos_, Jan 27 2014 */

%o (PARI) {a(n) = sign(n) * sum( k=0, n=abs(n)-1, (-1)^k * (2*n + 1 - k)! / (2^(n - k) * k! * (n - k)!) ) }; /* _Michael Somos_, Jan 27 2014 */

%o (PARI) x = 'x+O('x^33); Vec(serlaplace(((2 - 2*x - (1 - 2*x)^(1/2)) / (1-2*x)^(3/2)) * exp((1-2*x)^(1/2) - 1))) \\ _Gheorghe Coserea_, Aug 05 2015

%K nonn

%O 1,3

%A _N. J. A. Sloane_