A005332 Certain subgraphs of a directed graph. (Formerly M4438)

1, 7, 58, 838, 25171, 1610977, 214838128, 58540023808, 32208188445841, 35543124039418147, 78391002506394742198, 344921660620756227029578, 3025372940760065880037836511, 52886001393832278158415800800117, 1842588406743140390123203185385824268, 127974225758895121562137768141145597226148

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..17.

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) * 2^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

Mathematica

p[n_]:=Product[2^k-1, {k, n}]; a[n_]:=Sum[(Binomial[n-1, i] * p[n-1-i] * 2^i*Sum [(-1)^j*(n-1-i-j)/p[j], {j, 0, n-2-i}] ), {i, 0, n-2}]; Table[a[n], {n, 2, 17}] (* Stefano Spezia, Sep 07 2022 *)

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) * 2^i * sum(j=0, n-2-i, (-1)^j * (n-1-i-j) / p(j))); \\ Michel Marcus, May 10 2016

Crossrefs

Cf. A005330.

Sequence in context: A123766 A377331 A362772 * A132546 A210404 A301275

Adjacent sequences: A005329 A005330 A005331 * A005333 A005334 A005335

Keyword

nonn,changed

Author

N. J. A. Sloane

Extensions

More terms from Sean A. Irvine, May 10 2016

Status

approved