A000273 -id:A000273 - cp's OEIS frontend

A361366 Number of unlabeled simple planar digraphs with n nodes.

Original entry on oeis.org

1, 3, 16, 218, 9026, 907123

Offset: 1

Manfred Scheucher, Mar 09 2023

M. Kirchweger, M. Scheucher, and S. Szeider, SAT-Based Generation of Planar Graphs, in preparation.

Directed variant of A005470.

Cf. A000273

A361590 Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled nodes with exactly k strongly connected components of size 1.

Original entry on oeis.org

1, 0, 1, 1, 0, 2, 5, 5, 0, 6, 90, 55, 42, 0, 31, 5289, 2451, 974, 592, 0, 302, 1071691, 323709, 94332, 29612, 15616, 0, 5984, 712342075, 135208025, 25734232, 6059018, 1650492, 795930, 0, 243668, 1585944117738, 181427072519, 21650983294, 3358042412, 704602272, 174576110, 79512478, 0, 20286025

Offset: 0

Andrew Howroyd, Mar 16 2023

			Triangle begins:
        1;
        0,      1;
        1,      0,     2;
        5,      5,     0,     6;
       90,     55,    42,     0,    31;
     5289,   2451,   974,   592,     0, 302;
  1071691, 323709, 94332, 29612, 15616,   0, 5984;
  ...

Column k=0 is A361586.
Main diagonal is A003087.
Row sums are A000273.
The labeled version is A361592.
Cf. A350794, A361582, A361588.

\\ See PARI link in A350794 for program code.
{ my(A=A361590triang(6)); for(n=1, #A, print(A[n])) }

A003084 Related to number of digraphs.

Original entry on oeis.org

1, 5, 40, 801, 46821, 9185102, 6163297995, 14339791643249, 117235455142196308, 3412474003994007703605, 357748249084029269153547905, 136400554886800212073525651823742, 190697966236731843091458826668123014367, 984418987245772021436902193577676975221669509, 18875177868521443706244256784212908480749407027875180

Offset: 1

N. J. A. Sloane

nonn

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 124, table 5.1.2, p*a_p
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Needs["Combinatorica`"]; d[n_] := GraphPolynomial[n, x, Directed] /. x -> 1; max = 12; se = Series[ Sum[ a[n]*x^n/n, {n, 1, max}] - Log[1 + Sum[ d[n]*x^n, {n, 1, max}]], {x, 0, max}]; sol = SolveAlways[ se == 0, x]; A003084 = Table[ a[n], {n, 1, max}] /. sol[[1]] (* Jean-François Alcover, Feb 01 2012, after formula *)
terms = 15;
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v - 1];
d[n_] := (s = 0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]} ]; s/n!);
CoefficientList[Log[Sum[ d[n] x^n, {n, 0, terms + 1}]] + O[x]^(terms + 1), x] Range[0, terms] // Rest (* Jean-François Alcover, Aug 29 2019, after Andrew Howroyd in A000273 *)

Sum a(n) x^n / n = log (1 + Sum d(n) x^n ), where d(n) is # digraphs on n nodes (A000273).

Corrected and extended by Vladeta Jovovic, Jan 09 2000

More terms from Jean-François Alcover, Aug 29 2019

A054590 Number of disconnected digraphs with n unlabeled nodes.

Original entry on oeis.org

0, 1, 3, 19, 244, 10101, 1562298, 885237542, 1795141933300, 13031553571814674, 341286507770733602176, 32523592049568306757117737, 11366810480400463340177768296746, 14669108426561606778443288692015619955, 70315685953531425166863071956073529852161120

Offset: 1

Vladeta Jovovic, Apr 14 2000

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50

The labeled case is A054593.

Cf. A000273, A000719, A003085.

from functools import lru_cache
from itertools import product
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A054590(n):
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<Chai Wah Wu, Jul 05 2024

a(n) = A000273(n) - A003085(n).

Terms a(14) and beyond from Andrew Howroyd, Apr 18 2021

A054933 Number of unlabeled digraphs on n nodes up to reversing the arcs.

Original entry on oeis.org

1, 3, 13, 144, 5158, 778084, 441288796, 896699384640, 6513980949408584, 170630216624502796000, 16261454692830032538976880, 5683372715412978313604073582912, 7334542846356465411966209047539403296, 35157828307617499762304829312302735958971072, 629172630775224433640531447950565255471723325434560

Offset: 1

N. J. A. Sloane, May 24 2000

Andrew Howroyd, Table of n, a(n) for n = 1..50
A. Gainer-Dewar, Pólya theory for species with an equivariant group action, arXiv:1401.6202 [math.CO], 2014. Also Andrew Gainer-Dewar, Species with an equivariant group action, AUSTRALASIAN JOURNAL OF COMBINATORICS, Volume 63(2) (2015), Pages 202-225.
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

Cf. A000273, A002499.

A000273 = Cases[Import["https://oeis.org/A000273/b000273.txt", "Table"], {, }][[All, 2]];
A002499 = Cases[Import["https://oeis.org/A002499/b002499.txt", "Table"], {, }][[All, 2]];
a[n_] := (A000273[[n + 1]] + A002499[[n]])/2;
Array[a, 50] (* Jean-François Alcover, Aug 29 2019 *)

a(n) = (A000273(n) + A002499(n))/2.

A055969 Number of unlabeled digraphs with n nodes and an odd number of arcs.

Original entry on oeis.org

0, 1, 6, 104, 4736, 770112, 440994608, 896679244544, 6513978322585408, 170630215971902124288, 16261454692523251085611648, 5683372715412699486531047331840, 7334542846356464931239079919515090432, 35157828307617499760690834338506768579289088

Offset: 1

Vladeta Jovovic, Jul 19 2000

Andrew Howroyd, Table of n, a(n) for n = 1..50

Cf. A054928, A007869, A054960.

A000273 = Cases[Import["https://oeis.org/A000273/b000273.txt", "Table"], {, }][[All, 2]];
A003086 = Cases[Import["https://oeis.org/A003086/b003086.txt", "Table"], {, }][[All, 2]];
a[n_] := (A000273[[n + 1]] - A003086[[n]])/2;
Array[a, 50] (* Jean-François Alcover, Sep 12 2019, after Andrew Howroyd *)

a(n) = (A000273(n)-A003086(n))/2.

Terms a(14) and beyond from Andrew Howroyd, Sep 17 2018

A087616 Number of unlabeled cyclic preferences/voting outcomes, indifference and undecidedness/incompleteness permitted (Social Choice Theory).

Original entry on oeis.org

0, 0, 1, 26, 2491

Offset: 1

Detlef Pauly (dettodet(AT)yahoo.de), Sep 12 2003

Jobst Heitzig, Social Choice Under Incomplete, Cyclic Preferences, arXiv:math/0201285 [math.CO], 2002.

Cf. A087615 for the labeled analog, A003087, A087614, A000273.

Equals A000273 - A087614.

A217654 Triangular array read by rows. T(n,k) is the number of unlabeled directed graphs of n nodes that have exactly k isolated nodes.

Original entry on oeis.org

1, 0, 1, 2, 0, 1, 13, 2, 0, 1, 202, 13, 2, 0, 1, 9390, 202, 13, 2, 0, 1, 1531336, 9390, 202, 13, 2, 0, 1, 880492496, 1531336, 9390, 202, 13, 2, 0, 1, 1792477159408, 880492496, 1531336, 9390, 202, 13, 2, 0, 1, 13026163465206704, 1792477159408, 880492496, 1531336, 9390, 202, 13, 2, 0, 1

Offset: 0

Geoffrey Critzer, Oct 09 2012

Row sums give A000273.

Column k = 0 is A053598.

			Triangle T(n,k) begins:
        1;
        0,    1;
        2,    0,   1;
       13,    2,   0,  1;
      202,   13,   2,  0, 1;
     9390,  202,  13,  2, 0, 1;
  1531336, 9390, 202, 13, 2, 0, 1;
  ...

Alois P. Heinz, Rows n = 0..43, flattened

Cf. A000273, A053598.

b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(p[j]-1+add(
      igcd(p[k], p[j]), k=1..j-1)*2, j=1..nops(p)))([l[], 1$n])),
      add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
    end:
g:= proc(n) option remember; b(n$2, []) end:
T:= (n, k)-> g(n-k)-`if`(kAlois P. Heinz, Sep 04 2019

Needs["Combinatorica`"]; f[list_]:=Insert[Select[list,#>0&],0,-2]; nn=10; s=Sum[NumberOfDirectedGraphs[n]x^n, {n,0,nn}]; Drop[Flatten[Map[f, CoefficientList[Series[s (1-x)/(1-y x), {x,0,nn}], {x,y}]]], 1]
(* Second program: *)
b[n_, i_, l_List] := If[n==0 || i==1, 1/n!*2^(Function[p, Sum[p[[j]] - 1 + Sum[GCD[p[[k]], p[[j]]], {k, 1, j - 1}]*2, {j, 1, Length[p]}]][Join[l, Array[1&, n]]]), Sum[b[n - i*j, i - 1, Join[l, Array[i&, j]]]/j!/i^j, {j, 0, n/i}]];
g[n_] := g[n] = b[n, n, {}];
T[n_, k_] := g[n - k] - If[k < n, g[n - k - 1], 0];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Dec 07 2019, after Alois P. Heinz *)

O.g.f.: A(x)*(1-x)/(1-y*x) where A(x) is o.g.f. for A000273.

A309980 Number of binary relations on n unlabeled nodes that are neither reflexive nor antireflexive.

Original entry on oeis.org

0, 4, 72, 2608, 272752, 93847104, 110518842048, 454710381676032, 6640565658505128832, 348708024629593894001152, 66538376166308068986316241408, 46534722991725338264882258863095808, 120139253095727581744381043433138973706240, 1151909524447243687554850690730124812494959992832

Offset: 1

Peter Dolland, Nov 02 2019

nonn

Also the number of colored digraphs on n unlabeled nodes with nodes of exactly two colors. (Understand "(x,x) in the relation" for several nodes x as a special color!)

			n=2: We label node 1 with (1,1) in the relation and node 2 with (2,2) not in the relation, and we have two differently labeled nodes and so a(2) = A053763(2) = 4.
n=3: We have exactly either one or two nodes x with (x,x) in the relation. In A328773 this labelings correspond to the color schemes [2,1] and [1,2], both represented by the column index 2. So we have a(3) = 2 * A328773(3,2) = 72.

Andrew Howroyd, Table of n, a(n) for n = 1..50

Cf. A000595 (arbitrary binary relations), A000273 (digraphs, i.e. reflexive resp. antireflexive binary relations), A053763 (digraphs with distinguishing labeled nodes), A328773 (digraphs with given color scheme).

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v];
a[n_] := Module[{s = 0}, Do[t = 2^edges[p]; s += t*(1 - 2^(1 - Length[p]))* permcount[p], {p, IntegerPartitions[n]}]; s/n!];
Array[a, 14] (* Jean-François Alcover, Jan 08 2021, after Andrew Howroyd *)

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i], v[j]))) + sum(i=1, #v, v[i])}
a(n) = {my(s=0); forpart(p=n, my(t=2^edges(p)); s+=t*(1 - 2^(1-#p))*permcount(p)); s/n!} \\ Andrew Howroyd, Nov 02 2019

a(n) = A000595(n) - 2 * A000273(n) for n >= 1.

A329541 Triangle read by rows: T(n,k) is the number of colored digraphs on n nodes with exactly k colors assigned in a fix order according the node count (1 <= k <= n).

Original entry on oeis.org

1, 3, 4, 16, 36, 64, 218, 1856, 2112, 4096, 9608, 136376, 445440, 528384, 1048576, 1540944, 62020640, 270506880, 449511424, 537919488, 1073741824, 882033440, 55259421024, 435010671104, 1101584588800, 1834672455680, 2200096997376, 4398046511104

Offset: 1

Peter Dolland, Nov 16 2019

The values are just subtotals of the rows of the irregular triangle A328773.
Colors C_1,...,C_k are assigned to n nodes in the way that a_i >= a_(i+1) >= 1 for 1 <= i < k, where a_i denotes the number of nodes colored with C_i.
T(n,k) gives the number of digraphs (see A000273) without restrictions, where nodes of the same color are not differentiated.
The order of the colors effects, that only one color scheme has to be considered for a given color count. If such an order may not be presupposed, you should note A329546.

			Partitions for n=4, k=2: [3,1] and [2,2] with indices 2 and 3: T(4,2) = Sum_{i=2,3} A328773(4,i) = 752 + 1104 = 1856.
Partitions for n=6, k=3: [4,1,1], [3,2,1], [2,2,2] with indices 4, 6, 8: T(6,3) = Sum_{i=4,6,8} A328773(6,i) = 45277312 + 90196736 + 135032832 = 270506880.
Triangle T(n,k) begins:
        1
        3        4
       16       36        64
      218     1856      2112      4096
     9608   136376    445440    528384   1048576
  1540944 62020640 270506880 449511424 537919488 1073741824
  ...

Cf. A000273 (digraphs with one color), A053763 (digraphs with n colors), A328773 (digraphs to a given color scheme). A329546 (digraphs with unordered colors).

\\ here C(p) computes A328773 sequence value for given partition.
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i], v[j]))) + sum(i=1, #v, v[i]-1)}
C(p)={((i, v)->if(i>#p, 2^edges(v), my(s=0); forpart(q=p[i], s+=permcount(q)*self()(i+1, concat(v, Vec(q)))); s/p[i]!))(1, [])}
Row(n)={[vecsum(apply(C, vecsort([Vecrev(p) | p<-partitions(n),#p==m], , 4))) | m<-[1..n]]}
{ for(n=0, 10, print(Row(n))) }

T(n,1) = A000273(n) = A328773(n,1).
T(n,n) = 2^(n^2-n) = A053763(n) = A328773(n,A000041(n)).
T(n,n-1) = A328773(n,A000041(n)-1).
T(n,k) = Sum_{i=1..A000041(n), A063008(n,i) encodes a partition p with k=#p} A328773(n,i).

cp's OEIS Frontend

A361366 Number of unlabeled simple planar digraphs with n nodes.

Views

Author

Keywords

References

Crossrefs

A361590 Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled nodes with exactly k strongly connected components of size 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

A003084 Related to number of digraphs.

Views

Author

Keywords

References

Programs

Mathematica

Formula

Extensions

A054590 Number of disconnected digraphs with n unlabeled nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

Extensions

A054933 Number of unlabeled digraphs on n nodes up to reversing the arcs.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A055969 Number of unlabeled digraphs with n nodes and an odd number of arcs.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A087616 Number of unlabeled cyclic preferences/voting outcomes, indifference and undecidedness/incompleteness permitted (Social Choice Theory).

Views

Author

Keywords

Links

Crossrefs

Formula

A217654 Triangular array read by rows. T(n,k) is the number of unlabeled directed graphs of n nodes that have exactly k isolated nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A309980 Number of binary relations on n unlabeled nodes that are neither reflexive nor antireflexive.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs