login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A057271 Triangle T(n,k) of number of digraphs with a source and a sink on n labeled nodes and k arcs, k=0,1,..,n*(n-1). 4
1, 0, 2, 1, 0, 0, 6, 20, 15, 6, 1, 0, 0, 0, 24, 234, 672, 908, 792, 495, 220, 66, 12, 1, 0, 0, 0, 0, 120, 2544, 16880, 55000, 111225, 161660, 183006, 167660, 125945, 77520, 38760, 15504, 4845, 1140, 190, 20, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

REFERENCES

V. Jovovic, G. Kilibarda, Enumeration of labeled initially-finally connected digraphs, Scientific review, Serbian Scientific Society, 19-20 (1996), p. 245.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..2680 (rows 1..20)

V. Jovovic and G. Kilibarda, Enumeration of labeled quasi-initially connected digraphs, Discrete Math., 224 (2000), 151-163.

R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.

EXAMPLE

Triangle starts:

[1] 1;

[2] 0,2,1;

[3] 0,0,6,20,15,6,1;

[4] 0,0,0,24,234,672,908,792,495,220,66,12,1;

  ...

The number of digraphs with a source and a sink on 3 labeled nodes is 48 = 6+20+15+6+1.

PROG

(PARI) \\ Following Eqn 20 in the Robinson reference.

Z(p, f)={my(n=serprec(p, x)); serconvol(p, sum(k=0, n-1, x^k*f(k), O(x^n)))}

G(e, p)={Z(p, k->1/e^(k*(k-1)/2))}

U(e, p)={Z(p, k->e^(k*(k-1)/2))}

DigraphEgf(n, e)={sum(k=0, n, e^(k*(k-1))*x^k/k!, O(x*x^n) )}

StrongD(n, e=2)={-log(U(e, 1/G(e, DigraphEgf(n, e))))}

InitFinally(n, e=2)={my(S=StrongD(n, e)); Vec(serlaplace( S - S^2 + exp(S) * U(e, G(e, S*exp(-S))^2*G(e, DigraphEgf(n, e))) ))}

row(n)={Vecrev(InitFinally(n, 1+'y)[n]) }

{ for(n=1, 5, print(row(n))) } \\ Andrew Howroyd, Jan 16 2022

CROSSREFS

Row sums give A049524.

The unlabeled version is A057278.

Cf. A057272, A057273, A057274, A057275, A062735, A350791.

Sequence in context: A267163 A265163 A057275 * A021480 A201299 A057274

Adjacent sequences:  A057268 A057269 A057270 * A057272 A057273 A057274

KEYWORD

nonn,tabf,changed

AUTHOR

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 22 05:19 EST 2022. Contains 350481 sequences. (Running on oeis4.)