A104209 Number of labeled directed multigraphs with n arrows and no vertex of degree 0.

1, 3, 39, 819, 23949, 898947, 41212155, 2232057171, 139455901101, 9873341493231, 781184921112075, 68309191570851759, 6541702440222052137, 680922615974259589527, 76544749927261960908807, 9241807764375868372683255, 1192762017796744530286451865

Offset

0,2

Comments

These are the dimensions of the homogeneous components of a commutative graded Hopf algebra generalizing quasi-symmetric functions.

Links

Table of n, a(n) for n=0..16.

J.-C. Novelli, J.-Y. Thibon and N. M. Thiéry, Algèbres de Hopf de graphes [Hopf algebras of graphs], C.R. Acad. Sci. Paris (Comptes Rendus Mathématique), 339 (2004), 607-610.

Formula

a(n) = Sum_{m >=0} binomial(m^2+n-1, n)/2^(m+1).

G.f.: Sum_{m >= 0} (1-x)^(-m^2)/2^(m+1). Row sums of A120945. - Vladeta Jovovic, Sep 25 2006

a(n) ~ c * 2^(2*n) * n! / (sqrt(n) * (log(2))^(2*n)), where c = 0.432167265869761794333243584356866417673557873163120324347... = 2^(log(2)/8 - 1) / (sqrt(Pi) * log(2)). - Vaclav Kotesovec, May 03 2015, updated Mar 21 2018

Example

a(1)=3, the three graphs being (1 -> 2), (2 -> 1) and (1 -> 1).

Maple

d:=proc(n) local m; sum(binomial(m^2+n-1, n)/2^(m+1), m=0..infinity); end;

Mathematica

f[n_] := Sum[ Binomial[m^2 + n - 1, n]/2^(m + 1), {m, 0, Infinity}]; Table[ f[n], {n, 0, 15}] (* Robert G. Wilson v, Mar 16 2005 *)
Table[Sum[Sum[(-1)^(k-j)*Binomial[k, j]*Binomial[j^2+n-1, n], {j, 0, k}], {k, 0, 2*n}], {n, 0, 20}] (* Vaclav Kotesovec, May 03 2015, much faster *)

Crossrefs

Cf. A052171 (counts same objects up to labeling).

Cf. A020561, A120945.

Sequence in context: A336540 A228749 A370327 * A121247 A064732 A092610

Adjacent sequences: A104206 A104207 A104208 * A104210 A104211 A104212

Keyword

nonn

Author

Jean-Yves Thibon (jyt(AT)univ-mlv.fr), Mar 13 2005

Extensions

Corrected and extended by Robert G. Wilson v, Mar 16 2005

Offset corrected by Vaclav Kotesovec, May 03 2015

Status

approved