A006198 Number of partitions into pairs. (Formerly M4241)

1, 1, 6, 41, 365, 3984, 51499, 769159, 13031514, 246925295, 5173842311, 118776068256, 2964697094281, 79937923931761, 2315462770608870, 71705109685449689, 2364107330976587909, 82676528225908987824, 3056806370495613000259, 119137361202296994159415

Offset

1,3

Comments

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

References

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.

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

Links

Gheorghe Coserea, Table of n, a(n) for n = 1..201

Simon Plouffe, Approximations of generating functions and a few conjectures, arXiv:0911.4975 [math.NT], 2009.

Formula

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

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

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

a(-n) = -a(n) for all n in Z. - Michael Somos, Jan 27 2014

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

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

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

E.g.f. (for offset 1): exp(sqrt(1-2*x)-1) * (1/sqrt(1-2*x)-1). - Vaclav Kotesovec, Nov 29 2015

a(n) ~ 2^(n+1/2)*n^n/exp(n+1). - Vaclav Kotesovec, Nov 29 2015

Example

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

Mathematica

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 *)
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 *)
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 *)
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 *)
Table[(2 n - 1)!! Hypergeometric1F1[1 - n, 1 - 2 n, -2], {n, 20}] (* Eric W. Weisstein, Nov 14 2018 *)

Prog

(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 */
(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 */
(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

Crossrefs

Sequence in context: A317410 A094869 A178824 * A167588 A323573 A230134

Adjacent sequences: A006195 A006196 A006197 * A006199 A006200 A006201

Keyword

nonn

Author

N. J. A. Sloane

Status

approved