OFFSET
1,3
COMMENTS
As usual, there can be an edge both from i to j and from j to i.
REFERENCES
Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 428.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1980.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Vaclav Kotesovec, Table of n, a(n) for n = 1..58 (first 18 terms from R. W. Robinson)
Nicholas R. Beaton, Walks obeying two-step rules on the square lattice: full, half and quarter planes, arXiv:2010.06955 [math.CO], 2020.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002 [Local copy, with permission]
A. Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.
Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Bridging Weighted First Order Model Counting and Graph Polynomials, arXiv:2407.11877 [cs.LO], 2024. See p. 33.
J. Ostroff, Counting connected digraphs with gradings, Phd. Thesis (2013), Table 1.
R. W. Robinson, Letter to N. J. A. Sloane, 1980
FORMULA
a(n) ~ 2^(n*(n-1)). - Vaclav Kotesovec, May 19 2015
EXAMPLE
a(3) = 18 (the symbol = denotes a pair of parallel edges): 1->2->3->1 (2 such); 1=2->3->1 (6); 1=2=3->1 (6); 1=2=3=1 (1); 1=2=3 (3).
MAPLE
A003030 := proc(n)
option remember;
if n =1 then
1;
else
end if;
end proc:
seq(A003030(n), n=1..10) ; # R. J. Mathar, May 10 2016
MATHEMATICA
b[1]=1; b[n_]:=b[n]=2^(n*(n-1))-Sum[Binomial[n, j]*2^((n-1)*(n-j))*b[j], {j, 1, n-1}];
a[1]=1; a[n_]:=a[n]=b[n]+Sum[Binomial[n-1, j-1]*b[n-j]*a[j], {j, 1, n-1}];
Table[a[n], {n, 1, 15}] (* Vaclav Kotesovec, May 19 2015 *)
PROG
(PARI) \\ here B(n) is A054947 as vector.
B(n)={my(v=vector(n)); v[1]=1; for(n=2, #v, v[n]=2^(n*(n-1))-sum(j=1, n-1, binomial(n, j)*2^((n-1)*(n-j))*v[j])); v}
seq(n)={my(u=B(n), v=vector(n)); v[1]=1; for(n=2, #v, v[n]=u[n]+sum(j=1, n-1, binomial(n-1, j-1)*u[n-j]*v[j])); v} \\ Andrew Howroyd, Sep 10 2018
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
a(12)-a(13) added by Andrew Howroyd, Sep 10 2018
STATUS
approved