Search: a122078 -id:a122078
|
|
A003087
|
|
Number of acyclic digraphs with n unlabeled nodes.
(Formerly M1696)
|
|
+10
24
|
|
|
1, 1, 2, 6, 31, 302, 5984, 243668, 20286025, 3424938010, 1165948612902, 797561675349580, 1094026876269892596, 3005847365735456265830, 16530851611091131512031070, 181908117707763484218885361402
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Also the number of equivalence classes of n X n real (0,1)-matrices with all eigenvalues positive, up to conjugation by permutations.
|
|
REFERENCES
|
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 194.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
R. W. Robinson, Counting unlabeled acyclic digraphs, in Little C.H.C. (Ed.), "Combinatorial Mathematics V (Melbourne 1976)", Lect. Notes Math. 622 (1976), pp. 28-43. DOI:10.1007/BFb0069178.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A350415
|
|
Number of acyclic digraphs on n unlabeled nodes with a global source (or sink).
|
|
+10
10
|
|
|
1, 1, 3, 16, 164, 3341, 138101, 11578037, 1961162564, 668678055847, 457751797355605, 628137837068751147, 1726130748679532455689, 9493834992383031007906911, 104476428350838383854529661007, 2299979227717819421763629684068904
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
A local source (also called an out-node) is a node whose in-degree is zero. In the case of an acyclic digraph with only one local source, the source is also a global source.
|
|
LINKS
|
|
|
PROG
|
(PARI) A350415seq(16) \\ See PARI link in A122078 for program code.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A350449
|
|
Triangle read by rows: T(n,k) is the number of weakly connected acyclic digraphs on n unlabeled nodes with k arcs, n >= 1, k = 0..(n-1)*n/2.
|
|
+10
9
|
|
|
1, 0, 1, 0, 0, 3, 1, 0, 0, 0, 8, 9, 6, 1, 0, 0, 0, 0, 27, 54, 79, 63, 33, 10, 1, 0, 0, 0, 0, 0, 91, 320, 732, 1136, 1281, 1056, 649, 281, 85, 15, 1, 0, 0, 0, 0, 0, 0, 350, 1788, 6012, 14378, 26529, 38407, 44621, 41638, 31321, 18843, 8983, 3325, 920, 180, 21, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,6
|
|
LINKS
|
|
|
EXAMPLE
|
Triangle begins:
[1] 1;
[2] 0, 1;
[3] 0, 0, 3, 1;
[4] 0, 0, 0, 8, 9, 6, 1;
[5] 0, 0, 0, 0, 27, 54, 79, 63, 33, 10, 1;
...
|
|
PROG
|
(PARI) \\ See PARI link in A122078 for program code.
{ my(T=WeakAcyclicDigraphsByArcs(6)); for(n=1, #T, print(T[n])) }
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A058876
|
|
Triangle read by rows: T(n,k) = number of labeled acyclic digraphs with n nodes, containing exactly n+1-k points of in-degree zero (n >= 1, 1<=k<=n).
|
|
+10
8
|
|
|
1, 1, 2, 1, 9, 15, 1, 28, 198, 316, 1, 75, 1610, 10710, 16885, 1, 186, 10575, 211820, 1384335, 2174586, 1, 441, 61845, 3268125, 64144675, 416990763, 654313415, 1, 1016, 336924, 43832264, 2266772550, 44218682312, 286992935964, 450179768312
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
REFERENCES
|
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, (1.6.4).
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.
|
|
LINKS
|
|
|
FORMULA
|
Harary and Prins (following Robinson) give a recurrence.
|
|
EXAMPLE
|
Triangle begins:
1;
1, 2;
1, 9, 15;
1, 28, 198, 316;
1, 75, 1610, 10710, 16885;
...
|
|
MATHEMATICA
|
a[p_, k_] :=a[p, k] =If[p == k, 1, Sum[Binomial[p, k]*a[p - k, n]*(2^k - 1)^n*2^(k (p - k - n)), {n, 1, p - k}]];
Map[Reverse, Table[Table[a[p, k], {k, 1, p}], {p, 1, 6}]] // Grid (* Geoffrey Critzer, Aug 29 2016 *)
|
|
PROG
|
(PARI)
A058876(n)={my(v=vector(n)); for(n=1, #v, v[n]=vector(n, i, if(i==n, 1, my(u=v[n-i]); sum(j=1, #u, 2^(i*(#u-j))*(2^i-1)^j*binomial(n, i)*u[j])))); v}
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A345258
|
|
Number of acyclic digraphs (or DAGs) on n unlabeled vertices with one source and one sink.
|
|
+10
8
|
|
|
1, 1, 2, 10, 98, 1960, 80176, 6686760, 1129588960, 384610774696, 263104175114712, 360908867732030980, 991603865814038728388, 5453395569997436383751204, 60010050181461052836515513108, 1321051495313052133670927704328040, 58170762510305449187073353930875222256
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
LINKS
|
|
|
PROG
|
(PARI) A345258seq(16) \\ See PARI link in A122078 for program code.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A350450
|
|
Triangle read by rows: T(n,k) is the number of unlabeled weakly connected acyclic digraphs with n arcs and k vertices, n >= 0, k = 1..n+1.
|
|
+10
7
|
|
|
1, 0, 1, 0, 0, 3, 0, 0, 1, 8, 0, 0, 0, 9, 27, 0, 0, 0, 6, 54, 91, 0, 0, 0, 1, 79, 320, 350, 0, 0, 0, 0, 63, 732, 1788, 1376, 0, 0, 0, 0, 33, 1136, 6012, 9933, 5743, 0, 0, 0, 0, 10, 1281, 14378, 45225, 54502, 24635, 0, 0, 0, 0, 1, 1056, 26529, 151848, 322736, 298250, 108968
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
LINKS
|
|
|
EXAMPLE
|
Triangle begins:
1;
0, 1;
0, 0, 3;
0, 0, 1, 8;
0, 0, 0, 9, 27;
0, 0, 0, 6, 54, 91;
0, 0, 0, 1, 79, 320, 350;
0, 0, 0, 0, 63, 732, 1788, 1376;
0, 0, 0, 0, 33, 1136, 6012, 9933, 5743;
...
|
|
PROG
|
(PARI) \\ See PARI link in A122078 for program code.
{ my(T=WeakAcyclicDigraphsTr(10)); for(n=1, #T, print(T[n])); }
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A350447
|
|
Triangle read by rows: T(n,k) is the number of acyclic digraphs on n unlabeled nodes with k arcs, n >=0, k = 0..(n-1)*n/2.
|
|
+10
6
|
|
|
1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 4, 9, 9, 6, 1, 1, 1, 4, 12, 37, 60, 80, 63, 33, 10, 1, 1, 1, 4, 13, 51, 163, 407, 796, 1169, 1291, 1057, 649, 281, 85, 15, 1, 1, 1, 4, 13, 54, 215, 846, 2690, 7253, 15703, 27596, 39057, 44902, 41723, 31336, 18844, 8983, 3325, 920, 180, 21, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,7
|
|
LINKS
|
|
|
EXAMPLE
|
Triangle begins:
[0] 1;
[1] 1;
[2] 1, 1;
[3] 1, 1, 3, 1;
[4] 1, 1, 4, 9, 9, 6, 1;
[5] 1, 1, 4, 12, 37, 60, 80, 63, 33, 10, 1;
...
|
|
PROG
|
(PARI) \\ See PARI link in A122078 for program code.
{ my(T=AcyclicDigraphsByArcs(6)); for(n=1, #T, print(T[n])) }
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A350451
|
|
Number of weakly connected acyclic digraphs with n arcs.
|
|
+10
6
|
|
|
1, 1, 3, 9, 36, 151, 750, 3959, 22857, 140031, 909388, 6202031, 44256875, 328994157, 2540242646, 20317980102, 167980915848, 1432808198569, 12587788263807, 113739153822878, 1055610955120803, 10051265993496814, 98083750658261085, 979961276867802001, 10015362142357613001
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
|
|
PROG
|
(PARI) \\ See PARI link in A122078 for program code.
{ my(T=WeakAcyclicDigraphsTr(15)); vector(#T, n, vecsum(T[n])) }
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A350488
|
|
Triangle read by rows: T(n,k) is the number of acyclic digraphs on n unlabeled nodes with k arcs and a global source, n >= 1, k = 0..n*(n-1)/2.
|
|
+10
5
|
|
|
1, 0, 1, 0, 0, 2, 1, 0, 0, 0, 4, 6, 5, 1, 0, 0, 0, 0, 9, 25, 47, 46, 27, 9, 1, 0, 0, 0, 0, 0, 20, 95, 297, 582, 783, 738, 501, 235, 75, 14, 1, 0, 0, 0, 0, 0, 0, 48, 337, 1575, 4941, 11295, 19404, 25847, 26966, 22195, 14380, 7280, 2831, 816, 165, 20, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,6
|
|
LINKS
|
|
|
EXAMPLE
|
Triangle begins:
[1] 1;
[2] 0, 1;
[3] 0, 0, 2, 1;
[4] 0, 0, 0, 4, 6, 5, 1;
[5] 0, 0, 0, 0, 9, 25, 47, 46, 27, 9, 1;
[6] 0, 0, 0, 0, 0, 20, 95, 297, 582, 783, 738, 501, 235, 75, 14, 1;
...
|
|
PROG
|
(PARI) \\ See PARI link in A122078 for program code.
{ my(A=A350488rows(7)); for(i=1, #A, print(A[i])) }
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A350491
|
|
Triangle read by rows: T(n,k) is the number of acyclic digraphs on n unlabeled nodes with k arcs and a global source and sink, n >= 1, k = 0..n*(n-1)/2.
|
|
+10
4
|
|
|
1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 4, 4, 1, 0, 0, 0, 0, 1, 9, 25, 32, 22, 8, 1, 0, 0, 0, 0, 0, 1, 17, 92, 259, 441, 496, 379, 195, 66, 13, 1, 0, 0, 0, 0, 0, 0, 1, 28, 259, 1286, 4026, 8754, 13930, 16686, 15289, 10785, 5842, 2397, 722, 151, 19, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,12
|
|
LINKS
|
|
|
EXAMPLE
|
Triangle begins:
[1] 1;
[2] 0, 1;
[3] 0, 0, 1, 1;
[4] 0, 0, 0, 1, 4, 4, 1;
[5] 0, 0, 0, 0, 1, 9, 25, 32, 22, 8, 1;
[6] 0, 0, 0, 0, 0, 1, 17, 92, 259, 441, 496, 379, 195, 66, 13, 1;
...
|
|
PROG
|
(PARI) \\ See PARI link in A122078 for program code.
{ my(A=A350491rows(7)); for(i=1, #A, print(A[i])) }
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
Search completed in 0.012 seconds
|