[go: up one dir, main page]
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!)
Search: a122078 -id:a122078
Displaying 1-10 of 13 results found. page 1 2
     Sort: relevance | references | number | modified | created      Format: long | short | data
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
Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 0..18 were computed by R. W. Robinson; terms 19..36 by Sean A. Irvine, Jan 22 2014)
Jack Kuipers and Giusi Moffa, Uniform generation of random acyclic digraphs, arXiv preprint arXiv:1202.6590 [stat.CO], 2012. - N. J. A. Sloane, Sep 14 2012
B. D. McKay, F. E. Oggier, G. F. Royle, N. J. A. Sloane, I. M. Wanless and H. S. Wilf, Acyclic digraphs and eigenvalues of (0,1)-matrices, J. Integer Sequences, 7 (2004), #04.3.3.
B. D. McKay, F. E. Oggier, G. F. Royle, N. J. A. Sloane, I. M. Wanless and H. S. Wilf, Acyclic digraphs and eigenvalues of (0,1)-matrices, arXiv:math/0310423 [math.CO], 2003.
Lawrence Ong, Optimal Finite-Length and Asymptotic Index Codes for Five or Fewer Receivers, arXiv preprint arXiv:1606.05982 [cs.IT], 2016.
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.
R. W. Robinson, Enumeration of acyclic digraphs, Manuscript. (Annotated scanned copy)
Eric Weisstein's World of Mathematics, Acyclic Digraph.
Index entries for sequences related to binary matrices
CROSSREFS
Cf. A003024 (the labeled case), A082402, A101228 (weakly connected, inverse Euler Trans).
Rows sums of A122078, A350447, A350448.
KEYWORD
nonn,nice
AUTHOR
N. J. A. Sloane
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
Andrew Howroyd, Table of n, a(n) for n = 1..50
Marcel et al., Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?, MathOverflow, 2021.
PROG
(PARI) A350415seq(16) \\ See PARI link in A122078 for program code.
CROSSREFS
The labeled case is A003025.
Row sums of A350488.
A diagonal of A122078.
Cf. A003087, A345258, A350360.
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Dec 29 2021
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
Andrew Howroyd, Table of n, a(n) for n = 1..1350 (rows 1..20)
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
Row sums are A101228.
Columns sums are A350451.
Leading diagonal is A000238.
Cf. A350447 (not necessarily connected), A350450 (transpose).
KEYWORD
nonn,tabf
AUTHOR
Andrew Howroyd, Dec 31 2021
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
Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
R. W. Robinson, Enumeration of acyclic digraphs, Manuscript. (Annotated scanned copy)
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}
{ my(T=A058876(10)); for(n=1, #T, print(Vecrev(T[n]))) } \\ Andrew Howroyd, Dec 27 2021
CROSSREFS
Columns give A058877, A060337.
Diagonals give A003025, A003026, A060335.
Row sums give A003024.
Cf. A122078 (unlabeled case).
KEYWORD
nonn,easy,tabl
AUTHOR
N. J. A. Sloane, Jan 07 2001
EXTENSIONS
More terms from Vladeta Jovovic, Apr 10 2001
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
Andrew Howroyd, Table of n, a(n) for n = 1..50 (terms 1..40 from Mikhail Tikhomirov)
Marcel et al., Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?, MathOverflow, 2021.
PROG
(PARI) A345258seq(16) \\ See PARI link in A122078 for program code.
CROSSREFS
Row sums of A350491.
The labeled version is A165950.
Cf. A003087, A049531, A122078, A350415, A350492.
KEYWORD
nonn
AUTHOR
Max Alekseyev, Jun 12 2021
EXTENSIONS
a(9) from Brendan McKay.
Terms a(10) and beyond from Mikhail Tikhomirov, Jun 16 2021
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
Andrew Howroyd, Table of n, a(n) for n = 0..860 (rows 0..40)
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
Main diagonal is A000238.
Row sums are A350451.
Column sums are A101228.
Cf. A122078, A350449 (transpose).
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Dec 31 2021
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
Andrew Howroyd, Table of n, a(n) for n = 0..1350 (rows 0..20)
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
The labeled version is A081064.
Row sums are A003087.
Cf. A122078, A350449.
KEYWORD
nonn,tabf
AUTHOR
Andrew Howroyd, Dec 31 2021
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
Andrew Howroyd, Table of n, a(n) for n = 0..40
PROG
(PARI) \\ See PARI link in A122078 for program code.
{ my(T=WeakAcyclicDigraphsTr(15)); vector(#T, n, vecsum(T[n])) }
CROSSREFS
Row sums of A350450.
Column sums of A350449.
Cf. A101228, A122078.
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Dec 31 2021
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
Andrew Howroyd, Table of n, a(n) for n = 1..1350 (rows 1..20)
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
Row sums are A350415.
Column sums are A350490.
Leading diagonal is A000081.
The labeled version is A350487.
Cf. A122078, A350447, A350449, A350491.
KEYWORD
nonn,tabf
AUTHOR
Andrew Howroyd, Jan 01 2022
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
Andrew Howroyd, Table of n, a(n) for n = 1..1350 (rows 1..20)
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
Row sums are A345258.
Column sums are A350492.
Cf. A122078, A350447, A350449, A350488.
KEYWORD
nonn,tabf
AUTHOR
Andrew Howroyd, Jan 08 2022
STATUS
approved
page 1 2

Search completed in 0.012 seconds

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 29 18:55 EDT 2024. Contains 375518 sequences. (Running on oeis4.)