A005649 Expansion of e.g.f. (2 - e^x)^(-2). (Formerly M1866)

1, 2, 8, 44, 308, 2612, 25988, 296564, 3816548, 54667412, 862440068, 14857100084, 277474957988, 5584100659412, 120462266974148, 2772968936479604, 67843210855558628, 1757952715142990612, 48093560991292628228, 1385244691781856307124

Offset

0,2

Comments

Exponential self-convolution of numbers of preferential arrangements.

Number of compatible bipartitional relations on a set of cardinality n. - _Ralf Stephan_, Apr 27 2003

Stirling transform of A000142, shifted left one place: 1, 2, 6, 24, 120, 720, ... - _Philippe Deléham_, May 17 2005; corrected by _Ilya Gutkovskiy_, Jul 25 2018

With an extra 1 at the beginning, coefficients of the formal (divergent) series expansion at infinity of Sum_{k>=0} 1/binomial(x,k) = 1+1/x+2/x^2+8/x^3+... Also Sum_{k>=0} k!/x^k Product_{i=1..k-1} 1/(1-i/x) yields a generating function in 1/x. - _Roland Bacher_, Nov 21 2000

Stirling-Bernoulli transform of A001057: 1, -1, 2, -2, 3, -3, 4, ... - _Philippe Deléham_, May 27 2015

a(n) is the total number of open sets summed over all chain topologies that can be placed on an n-set. A chain topology is a topology whose open sets can be totally ordered by inclusion. - _Geoffrey Critzer_, Apr 06 2017

From _Gus Wiseman_, Jun 10 2020: (Start)

Also the number of length n + 1 sequences covering an initial interval of positive integers with no adjacent equal parts (anti-runs). For example, the a(0) = 1 through a(2) = 8 anti-runs are:

(1) (1,2) (1,2,1)

(2,1) (1,2,3)

(1,3,2)

(2,1,2)

(2,1,3)

(2,3,1)

(3,1,2)

(3,2,1)

Also the number of ordered set partitions of {1,...,n + 1} with no two successive vertices in the same block. For example, the a(0) = 1 through a(2) = 8 ordered set partitions are:

{{1}} {{1},{2}} {{1,3},{2}}

{{2},{1}} {{2},{1,3}}

{{1},{2},{3}}

{{1},{3},{2}}

{{2},{1},{3}}

{{2},{3},{1}}

{{3},{1},{2}}

{{3},{2},{1}}

(End)

References

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 294.

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..423 (first 101 terms from T. D. Noe)

José A. Adell, Beáta Bényi, Venkat Murali, and Sithembele Nkonkobe, Generalized Barred Preferential Arrangements, Transactions on Combinatorics (2022).

Connor Ahlbach, Jeremy Usatine and Nicholas Pippenger, Barred Preferential Arrangements, Electron. J. Combin., Volume 20, Issue 2 (2013), #P55.

D. Foata, and C. Krattenthaler, Graphical Major Indices, II, Séminaire Lotharingien de Combinatoire, B34k, 16 pp., 1995.

D. Foata and D. Zeilberger, The Graphical Major Index, arXiv:math/9406220 [math.CO], 1994.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 154

Augustine O. Munagi, Two Applications of the Bijection on Fibonacci Set Partitions, Fibonacci Quart. 55 (2017), no. 5, 144-148.

Formula

E.g.f.: 1/(2-exp(x))^2.

a(n) = (A000670(n) + A000670(n+1)) / 2. - _Philippe Deléham_, May 16 2005

a(n) = D^n(1/(1-x)^2) evaluated at x = 0, where D is the operator (1+x)*d/dx. Cf. A000670 and A052841. - _Peter Bala_, Nov 25 2011

E.g.f.: 1/(2-exp(x))^2 = 1/(G(0) + 4), G(k) = 1-4/((2^k)-x*(4^k)/((2^k)*x-(2*k+2)/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Dec 15 2011

O.g.f.: Sum_{n>=0} (2*n)!/n! * x^n / Product_{k=1..n} (1 + (n+k)*x). - _Paul D. Hanna_, Jan 03 2013

G.f.: (G(0) - 1)/(x-1) where G(k) = 1 - (k+1)/(1-k*x)/(1-x/(x-1/G(k+1) )); (recursively defined continued fraction). - _Sergei N. Gladkovskii_, Jan 15 2013

G.f.: 1/G(0) where G(k) = 1 - x*(k+2)/( 1 - 2*x*(k+1)/G(k+1) ); (continued fraction ). - _Sergei N. Gladkovskii_, Mar 23 2013

a(n) = Sum_{k = 0..n} A163626(n,k) * A001057(k+1). - _Philippe Deléham_, May 27 2015

a(n) ~ n! * n / (4 * (log(2))^(n+2)). - _Vaclav Kotesovec_, Jul 01 2018

a(n) = Sum_{k=0..n} Stirling2(n,k)*(k + 1)!. - _Ilya Gutkovskiy_, Jul 25 2018

From _Seiichi Manyama_, Nov 19 2023: (Start)

a(0) = 1; a(n) = Sum_{k=1..n} (k/n + 1) * binomial(n,k) * a(n-k).

a(0) = 1; a(n) = 2*a(n-1) - 2*Sum_{k=1..n-1} (-1)^k * binomial(n-1,k) * a(n-k). (End)

Maple

b:= proc(n, m) option remember;
     `if`(n=0, (m+1)!, m*b(n-1, m)+b(n-1, m+1))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..23);  # _Alois P. Heinz_, Aug 03 2021

Mathematica

f[n_] := Sum[(i + j)^n/2^(2 + i + j), {i, 0, Infinity}, {j, 0, Infinity}]; Array[f, 20, 0] (* _Vladimir Reshetnikov_, Dec 31 2008 *)
a[n_] := (-1)^n (PolyLog[-n-1, 2] - PolyLog[-n, 2])/4; Array[f, 20, 0] (* _Vladimir Reshetnikov_, Jan 23 2011 *)
Range[0, 19]! CoefficientList[Series[(2 - Exp@ x)^-2, {x, 0, 19}], x] (* _Robert G. Wilson v_, Jan 23 2011 *)
nn = 19; Range[0, nn]! CoefficientList[Series[1 + D[u^2 (Exp[z] - 1)/(1 - u (Exp[z] - 1)), u] /. u -> 1, {z, 0, nn}], z] (* _Geoffrey Critzer_, Apr 06 2017 *)
allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n], FreeQ[Differences[#], 0]&]], {n, 0, 6}] (* _Gus Wiseman_, Jun 10 2020 *)
With[{nn=20}, CoefficientList[Series[1/(2-E^x)^2, {x, 0, nn}], x] Range[0, nn]!] (* _Harvey P. Dale_, Oct 02 2021 *)

Prog

(PARI) a(n)=if(n<0, 0, n!*polcoeff(subst(1/(1-y)^2, y, exp(x+x*O(x^n))-1), n))
(PARI) a(n)=polcoeff(sum(m=0, n, (2*m)!/m!*x^m/prod(k=1, m, 1+(m+k)*x+x*O(x^n))), n)
for(n=0, 20, print1(a(n), ", ")) \\ _Paul D. Hanna_, Jan 03 2013
(Maxima) t(n):=sum(stirling2(n, k)*k!, k, 0, n);
makelist(sum(binomial(n, k)*t(k)*t(n-k), k, 0, n), n, 0, 20);
\\ _Emanuele Munarini_, Oct 02 2012

Crossrefs

Cf. A000670.

2*A083410(n)=a(n), if n>0.

Pairwise sums of A052841 and also of A089677.

Anti-run compositions are counted by A003242.

A triangle counting maximal anti-runs of compositions is A106356.

Anti-runs of standard compositions are counted by A333381.

Adjacent unequal pairs in standard compositions are counted by A333382.

Cf. A000110, A008277, A055932, A124762, A238279, A238424, A317081.

Sequence in context: A137984 A191810 A172109 * A253950 A212913 A321628

Adjacent sequences: A005646 A005647 A005648 * A005650 A005651 A005652

Keyword

nonn,easy,nice

Author

_N. J. A. Sloane_, _Simon Plouffe_

Status

approved