A137435 Acyclic 3-multidigraphs on n nodes.

1, 1, 7, 289, 63487, 69711361, 367404658687, 9036285693861889, 1015983915928423497727, 514039127264534042076119041, 1155907276780291114251550828003327, 11436746463485293365165228859824053157889, 493776641438913029616304251647570171691844763647

Offset

0,3

Comments

This is the 2nd row of Table 1, p. 3 in Liskovets. The first row is A003024.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..55

Valery A. Liskovets, More on counting acyclic digraphs, arXiv:0804.2496 [math.CO], 2008.

Formula

1 = Sum_{n>=0} a(n)*exp(-4^n*x)*x^n/n!. - Vladeta Jovovic, Apr 22 2008

1 = Sum_{n>=0} a(n)*x^n/(1 + 4^n*x)^(n+1). - Paul D. Hanna, Oct 17 2009

1 = Sum_{n>=0} a(n)*binomial(n+m-1,n)*x^n/(1 + 4^n*x)^(n+m) for m >= 1. - Paul D. Hanna, Apr 01 2011

log(1+x) = Sum_{n>=1} a(n)*(x^n/n)/(1 + 4^n*x)^n. - Paul D. Hanna, Apr 01 2011

a(n) = Sum_{k=1..n} (-1)^(k+1)*C(n, k)*4^(k*(n-k))*a(n-k) for n > 0 with a(0)=1. - Paul D. Hanna, Apr 01 2011

Example

From Paul D. Hanna, Apr 01 2011: (Start)
Illustration of the generating functions.
E.g.f.: 1 = exp(-x) + exp(-4*x)*x + 7*exp(-16*x)*x^2/2! + 289*exp(-64*x)*x^3/3! + ...
L.g.f.: log(1+x) = x/(1+4*x) + 7*(x^2/2)/(1+16*x)^2 + 289*(x^3/3)/(1+64*x)^3 + ...
G.f.: 1 = 1/(1+x) + 1*x/(1+4*x)^2 + 7*x^2/(1+16*x)^3 + 289*x^3/(1+64*x)^4 + ...
G.f.: 1 = 1/(1+x)^2 + 1*2*x/(1+4*x)^3 + 7*3*x^2/(1+16*x)^4 + 289*4*x^3/(1+64*x)^5 + ...
G.f.: 1 = 1/(1+x)^3 + 1*3*x/(1+4*x)^4 + 7*6*x^2/(1+16*x)^5 + 289*10*x^3/(1+64*x)^6 + ... (End)

Mathematica

a[n_] := a[n] = Sum[(-1)^(k+1)*Binomial[n, k]*4^(k*(n-k))*a[n-k], {k, 1, n}]; a[0]=1; Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Dec 15 2014, after Paul D. Hanna *)

Prog

(PARI) {a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+4^k*x+x*O(x^n))^(k+1)), n)} \\ Paul D. Hanna, Oct 17 2009
(PARI) /* Holds for m>=1: */
{a(n)=local(m=1); polcoeff(1-sum(k=0, n-1, a(k)*binomial(m+k-1, k)*x^k/(1+4^k*x+x*O(x^n))^(k+m)), n)/binomial(m+n-1, n)} \\ Paul D. Hanna, Apr 01 2011
(PARI) /* Recurrence: */
{a(n)=if(n<1, n==0, sum(k=1, n, -(-1)^k*binomial(n, k)*4^(k*(n-k))*a(n-k)))} \\ Paul D. Hanna, Apr 01 2011
(PARI) /* E.g.f.: */
{a(n)=n!*polcoeff(1-sum(k=0, n-1, a(k)*exp(-4^k*x+x*O(x^n))*x^k/k!), n)} \\ Paul D. Hanna, Apr 01 2011

Crossrefs

Cf. A003024, A188457.

Sequence in context: A176072 A096548 A160072 * A220241 A041851 A082168

Adjacent sequences: A137432 A137433 A137434 * A137436 A137437 A137438

Keyword

nonn

Author

Jonathan Vos Post, Apr 17 2008

Extensions

More terms from Vladeta Jovovic, Apr 22 2008

Offset changed to 0 by Paul D. Hanna, Apr 01 2011

Status

approved