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,2

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.

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

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

Crossrefs

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

Sequence in context: A240638 A245050 A242009 * A203429 A153850 A138458

Adjacent sequences: A121134 A121135 A121136 * A121138 A121139 A121140

Keyword

easy,nonn,changed

Author

Vladeta Jovovic, Sep 06 2006

Status

approved