|
| |
|
|
A137435
|
|
Arises in counting acyclic digraphs.
|
|
1
|
|
|
|
1, 1, 7, 289, 63487, 69711361, 367404658687, 9036285693861889, 1015983915928423497727, 514039127264534042076119041, 1155907276780291114251550828003327, 11436746463485293365165228859824053157889, 493776641438913029616304251647570171691844763647
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
This is the 2nd row of Table 1, p. 3 in Liskovets. The first row is A003024. Abstract: In this note we derive enumerative formulas for several types of labelled acyclic directed graphs by slight modifications of the familiar recursive formula for simple acyclic digraphs. These considerations are motivated by and based upon, recent combinatorial results in geometric topology obtained by S.Choi, who established exact correspondences between acyclic digraphs and so-called small covers over hypercubes and related polytopes. In particular, we show that the number of equivalence classes of small covers over the cartesian product of n copies of an r-simplex is equal to the number of acyclic (2^r-1)-multidigraphs of order n. Asymptotics follows easily since the main formula is represented by a simple equation in terms of special generating functions.
|
|
|
LINKS
|
Table of n, a(n) for n=0..12.
Valery A. Liskovets, More on counting acyclic digraphs, April 15, 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). [From Paul D. Hanna, Oct 17 2009]
1 = Sum_{n>=0} a(n)*C(n+m-1,n)*x^n/(1 + 4^n*x)^(n+m) for m>=1. [From Paul D. Hanna, Apr 1 2011]
log(1+x) = Sum_{n>=1} a(n)*(x^n/n)/(1 + 4^n*x)^n. [From Paul D. Hanna, Apr 1 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. [From Paul D. Hanna, Apr 1 2011]
|
|
|
EXAMPLE
|
From Paul D. Hanna, Apr 1 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)
|
|
|
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)} [From 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)} [From Paul D. Hanna, Apr 1 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)))} [From Paul D. Hanna, Apr 1 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)} [From Paul D. Hanna, Apr 1 2011]
|
|
|
CROSSREFS
|
Cf. A003024, A188457.
Sequence in context: A176072 A096548 A160072 * A220241 A041851 A082168
Adjacent sequences: A137432 A137433 A137434 * A137436 A137437 A137438
|
|
|
KEYWORD
|
nonn,changed
|
|
|
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 1 2011.
|
|
|
STATUS
|
approved
|
| |
|
|
