|
|
A006198
|
|
Number of partitions into pairs.
(Formerly M4241)
|
|
2
|
|
|
1, 1, 6, 41, 365, 3984, 51499, 769159, 13031514, 246925295, 5173842311, 118776068256, 2964697094281, 79937923931761, 2315462770608870, 71705109685449689, 2364107330976587909, 82676528225908987824, 3056806370495613000259, 119137361202296994159415
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
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+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
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|