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

Author

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

Keywords

• nonn

Comments

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

Examples

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

Links

• 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.

Crossrefs

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

Cf. A020561, A120945.

Programs

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 *)

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

Extensions

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

Offset corrected by Vaclav Kotesovec, May 03 2015