A121137 Number of labeled directed multigraphs (without loops) with n arcs and no vertex of degree 0.

1, 2, 27, 572, 16787, 631362, 28980861, 1570956872, 98212870233, 6956704585554, 550626446263423, 48163137319172436, 4613554511554200251, 480324019903607680066, 54004504167811544647161, 6521368218660772789452944, 841771274136198763040518633

Offset: 0

Author

Vladeta Jovovic, Sep 06 2006

Keywords

• easy
• nonn

Links

• Nathaniel Johnston, Table of n, a(n) for n = 0..50
• Math StackExchange, Marko Riedel et al., Labeled multigraphs
• Marko Riedel, Proof of closed form by Egorychev method.

Crossrefs

Cf. A052170 (unlabeled analog), A104209, A052171.

Programs

Maple

seq(sum(binomial(m*(m-1)+n-1,n)/2^(m+1),m=0..infinity),n=0..10);
# alternate program
A121137:= n -> add(add(binomial(m, q)*(-1)^(m-q)*binomial(n+q*(q-1)-1, n), q=0..m), m=0..2*n):
seq(A121137(n), n=0..20); # Marko Riedel, Jan 26 2025

Formula

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

a(n) = Sum_{m=0..2n} Sum_{q=0..m} binomial(m,q)*(-1)^(m-q)*binomial(n+q*(q-1)-1,n). - Marko Riedel, Jan 26 2025