login
Certain subgraphs of a directed graph.
(Formerly M4438)
1

%I M4438 #22 Sep 07 2022 07:45:05

%S 1,7,58,838,25171,1610977,214838128,58540023808,32208188445841,

%T 35543124039418147,78391002506394742198,344921660620756227029578,

%U 3025372940760065880037836511,52886001393832278158415800800117,1842588406743140390123203185385824268,127974225758895121562137768141145597226148

%N Certain subgraphs of a directed graph.

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

%H E. Andresen, K. Kjeldsen, <a href="http://dx.doi.org/10.1016/0012-365X(76)90054-6">On certain subgraphs of a complete transitively directed graph</a>, Discrete Math. 14 (1976), no. 2, 103-119.

%F 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

%t 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 *)

%o (PARI) p(n) = prod(k=1, n, 2^k-1);

%o 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

%Y Cf. A005330.

%K nonn

%O 2,2

%A _N. J. A. Sloane_

%E More terms from _Sean A. Irvine_, May 10 2016