A005330 Certain subgraphs of a directed graph. (Formerly M3992)

1, 5, 40, 644, 21496, 1471460, 204062440, 56865072164, 31688930152696, 35223651007587140, 78001790003385408040, 343983307379873262633284, 3020895063527811952260491896, 52843677532033943174017588842020, 1841795434229559227318546660111716840

Offset

2,2

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=2..16.

E. Andresen, K. Kjeldsen, On certain subgraphs of a complete transitively directed graph, Discrete Math. 14 (1976), no. 2, 103-119.

Formula

a(n) = Sum_{i=0..n-2} (C(n-1, i) * p(n-1-i) * Sum_{j=0..n-2-i} (-1)^j * (n-1-i-j) / p(j)) where p(n) = Product_{k=1..n} (2^k-1). - Sean A. Irvine, May 10 2016

Prog

(PARI) p(n) = prod(k=1, n, 2^k-1);
a(n) = sum(i=0, n-2, binomial(n-1, i) * p(n-1-i) * sum(j=0, n-2-i, (-1)^j * (n-1-i-j) / p(j))); \\ Michel Marcus, May 10 2016

Crossrefs

Sequence in context: A280572 A217904 A357796 * A003084 A010573 A326265

Adjacent sequences: A005327 A005328 A005329 * A005331 A005332 A005333

Keyword

nonn

Author

N. J. A. Sloane

Extensions

More terms from Sean A. Irvine, May 10 2016

Status

approved