A006125 -id:A006125 - cp's OEIS frontend

A263340 Triangle read by rows: T(n,k) is the number of graphs with n vertices containing k triangles.

1, 1, 2, 3, 1, 7, 2, 1, 0, 1, 14, 7, 5, 2, 3, 1, 0, 1, 0, 0, 1, 38, 23, 28, 14, 18, 9, 7, 5, 4, 1, 4, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 107, 102, 141, 117, 123, 92, 80, 63, 49, 35, 35, 23, 15, 17, 10, 4, 9, 5, 2, 3, 3, 2, 2, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1

Offset: 0

Christian Stump, Oct 15 2015

Row sums give A000088.
First column is A006785.
Row lengths are 1 + binomial(n,3). - Geoffrey Critzer, Apr 13 2017

			Triangle begins:
  1;
  1;
  2;
  3,1;
  7,2,1,0,1;
  14,7,5,2,3,1,0,1,0,0,1;
  38,23,28,14,18,9,7,5,4,1,4,1,1,1,0,0,1,0,0,0,1;
  ...

Pontus von Brömssen, Rows n = 0..10, flattened
FindStat - Combinatorial Statistic Finder, The number of triangles of a graph.
Gus Wiseman, The graphs counted under row n = 5.

Row sums are A000088, labeled A006125.
Column k = 0 is A006785 (lab A213434), covering A372169 (lab A372168).
Counting edges gives A008406 (lab A084546), covering A370167 (lab A054548).
Row lengths are A050407.
The labeled version is A372170, covering A372167.
The covering case is A372173, sums A002494, labeled A006129.
Column k = 1 is A372194 (lab A372172), covering A372174 (lab A372171).
A001858 counts acyclic graphs, unlabeled A005195.
A372176 counts labeled graphs by directed cycles, covering A372175.
Cf. A000055, A053530, A137917, A137918, A140637, A144958, A322700, A370169.

Table[Table[Count[Table[Tr[MatrixPower[AdjacencyMatrix[GraphData[{n, i}]], 3]]/6, {i, 1, NumberOfGraphs[n]}], k], {k, 0, Binomial[n, 3]}], {n, 1, 7}] (* Geoffrey Critzer, Apr 13 2017 *)

Row 7 from Geoffrey Critzer, Apr 13 2017

T(0,0)=1 prepended by Alois P. Heinz, Apr 13 2017

A326293 Number of non-nesting, topologically connected simple graphs with vertices {1..n}.

Original entry on oeis.org

1, 1, 2, 4, 8, 27, 192, 1750

Offset: 0

Gus Wiseman, Jun 29 2019

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d. A graph with positive integer vertices is topologically connected if the graph whose vertices are the edges and whose edges are crossing pairs of edges is connected.

Gus Wiseman, The a(5) = 27 non-nesting, topologically connected simple graphs.

The inverse binomial transform is the covering case A326349.
Topologically connected simple graphs are A324328.
Non-crossing simple graphs are A054726.
Topologically connected set partitions are A099947.
Cf. A000108, A000699, A006125, A007297, A117662, A136653.
Cf. A324173, A324323, A324327, A326244, A326330, A326341.

croXQ[eds_]:=MatchQ[eds,{_,{x_,y_},_,{z_,t_},_}/;x_,{x_,y_},_,{z_,t_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],!nesXQ[#]&&Length[csm[Union[Subsets[#,{1}],Select[Subsets[#,{2}],croXQ]]]]<=1&]],{n,0,5}]

A368984 Number of graphs with loops (symmetric relations) on n unlabeled vertices in which each connected component has an equal number of vertices and edges.

Original entry on oeis.org

1, 1, 2, 5, 12, 29, 75, 191, 504, 1339, 3610, 9800, 26881, 74118, 205706, 573514, 1606107, 4513830, 12727944, 35989960, 102026638, 289877828, 825273050, 2353794251, 6724468631, 19239746730, 55123700591, 158133959239, 454168562921, 1305796834570, 3758088009136

Offset: 0

Andrew Howroyd, Jan 11 2024

nonn

The graphs considered here can have loops but not parallel edges.

Also the number of unlabeled loop-graphs with n edges and n vertices such that it is possible to choose a different vertex from each edge. - Gus Wiseman, Jan 25 2024

			Representatives of the a(3) = 5 graphs are:
   {{1,2}, {1,3}, {2,3}},
   {{1}, {1,2}, {1,3}},
   {{1}, {1,2}, {2,3}},
   {{1}, {2}, {2,3}},
   {{1}, {2}, {3}}.
The graph with 4 vertices and edges {{1}, {2}, {1,2}, {3,4}} is included by A368599 but not by this sequence.

Andrew Howroyd, Table of n, a(n) for n = 0..500

The case of a unique choice is A000081.
Without loops we have A137917, labeled A137916.
The labeled version appears to be A333331.
Without the choice condition we have A368598, covering A368599.
The complement is counted by A368835, labeled A368596 (covering A368730).
Row sums of A368926, labeled A368924.
The connected case is A368983.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A000666 counts unlabeled loop-graphs, covering A322700.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, connected A001187, unlabeled A002494.
A322661 counts labeled covering loop-graphs, connected A062740.
Cf. A014068, A057500, A116508, A129271, A133686, A367863, A367869, A367902, A368597, A368601, A368836.

brute[m_]:=First[Sort[Table[Sort[Sort/@(m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]},{i,Length[p]}])],{p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute/@Select[Subsets[Subsets[Range[n],{1,2}],{n}],Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]]],{n,0,5}] (* Gus Wiseman, Jan 25 2024 *)

Euler transform of A368983.

A369142 Number of labeled loop-graphs covering {1..n} such that it is not possible to choose a different vertex from each edge (non-choosable).

Original entry on oeis.org

0, 0, 1, 22, 616, 26084, 1885323, 253923163, 66619551326, 34575180977552, 35680008747431929, 73392583275070667841, 301348381377662031986734, 2471956814761854578316988092, 40530184362443276558060719358471, 1328619783326799871747200601484790193

Offset: 0

Gus Wiseman, Jan 20 2024

nonn

Also labeled loop-graphs covering n vertices with at least one connected component containing more edges than vertices.

			The a(0) = 0 through a(3) = 22 loop-graphs (loops shown as singletons):
  .  .  {{1},{2},{1,2}}  {{1},{2},{3},{1,2}}
                         {{1},{2},{3},{1,3}}
                         {{1},{2},{3},{2,3}}
                         {{1},{2},{1,2},{1,3}}
                         {{1},{2},{1,2},{2,3}}
                         {{1},{2},{1,3},{2,3}}
                         {{1},{3},{1,2},{1,3}}
                         {{1},{3},{1,2},{2,3}}
                         {{1},{3},{1,3},{2,3}}
                         {{2},{3},{1,2},{1,3}}
                         {{2},{3},{1,2},{2,3}}
                         {{2},{3},{1,3},{2,3}}
                         {{1},{1,2},{1,3},{2,3}}
                         {{2},{1,2},{1,3},{2,3}}
                         {{3},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3}}
                         {{1},{2},{3},{1,2},{2,3}}
                         {{1},{2},{3},{1,3},{2,3}}
                         {{1},{2},{1,2},{1,3},{2,3}}
                         {{1},{3},{1,2},{1,3},{2,3}}
                         {{2},{3},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3},{2,3}}

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

The version for a unique choice is A000272, unlabeled A000055.
Without the choice condition we have A006125, unlabeled A000088.
The case without loops is A367868, covering case of A367867.
For exactly n edges we have A368730, covering case of A368596.
The complement is counted by A369140, covering case of A368927.
This is the covering case of A369141.
For n edges and no loops we have A369144, covering A369143.
The unlabeled version is A369147, covering case of A369146.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A129271 counts connected choosable graphs, unlabeled A005703.
A133686 counts choosable graphs, covering A367869.
A322661 counts covering loop-graphs, connected A062740, unlabeled A322700.
A367902 counts choosable set-systems, complement A367903.
Cf. A000666, A003465, A006649, A116508, A137916, A333331, A368600, A368924, A368984, A369145, A369194.

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}]],Union@@#==Range[n]&&Length[Select[Tuples[#],UnsameQ@@#&]]==0&]],{n,0,5}]

Inverse binomial transform of A369141.

a(n) = A322661(n) - A369140(n). - Andrew Howroyd, Feb 02 2024

a(6) onwards from Andrew Howroyd, Feb 02 2024

A372169 Number of unlabeled triangle-free graphs covering n vertices.

Original entry on oeis.org

1, 0, 1, 1, 4, 7, 24, 69, 303, 1487, 10275, 92899, 1157109, 19534822, 447074367, 13764681083, 567227701549, 31139379910949

Offset: 0

Gus Wiseman, Apr 23 2024

The labeled version is A372168.

			Non-isomorphic representatives of the a(5) = 7 graphs:
  12-35-45
  13-24-35-45
  14-25-35-45
  15-25-35-45
  12-13-24-35-45
  15-23-24-35-45
  13-14-23-24-35-45

Eric Weisstein's World of Mathematics, Triangle-Free Graph
Gus Wiseman, The a(6) = 24 unlabeled triangle-free graphs covering 6 vertices.

Dominated by A002494, labeled A006129.
Covering case of A006785, labeled A213434.
The connected case is A024607.
For all cycles (not just triangles) we have A144958, labeled A105784.
The labeled version is A372168.
For a unique triangle (labeled) we have A372171, non-covering A372172.
Column k = 0 of A372173, labeled A372167.
For a unique triangle (unlabeled) we have A372174, non-covering A372194.
A001858 counts acyclic graphs, unlabeled A005195.
A006125 counts simple graphs, unlabeled A000088.
A054548 counts covering graphs by number of edges, unlabeled A370167.
A372170 counts graphs by triangles, unlabeled A263340.
Cf. A000055, A000272, A053530, A121251, A322700, A372175, A372191.

First differences of A006785.

A372170 Irregular triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and exactly k triangles, 0 <= k <= binomial(n,3).

Original entry on oeis.org

1, 1, 2, 7, 1, 41, 16, 6, 0, 1, 388, 290, 195, 70, 40, 30, 0, 10, 0, 0, 1, 5789, 6980, 6910, 4560, 3030, 2292, 1230, 780, 600, 180, 236, 60, 45, 60, 0, 0, 15, 0, 0, 0, 1, 133501, 235270, 313705, 302505, 260890, 222509, 174615, 126780, 102970, 67165, 50134, 37485, 20370, 17990, 11445, 6552, 4515, 3570, 1680, 1785, 154, 735, 455, 140, 0, 105, 105, 0, 0, 0, 21, 0, 0, 0, 0, 1

Offset: 0

Gus Wiseman, Apr 23 2024

			Triangle begins:
     1
     1
     2
     7    1
    41   16    6    0    1
   388  290  195   70   40   30    0   10    0    0    1
   ...
For example, the T(4,1) = 16 graphs are:
  12-13-23
  12-14-24
  13-14-34
  23-24-34
  12-13-14-23
  12-13-14-24
  12-13-14-34
  12-13-23-24
  12-13-23-34
  12-14-23-24
  12-14-24-34
  12-23-24-34
  13-14-23-34
  13-14-24-34
  13-23-24-34
  14-23-24-34

Andrew Howroyd, Table of n, a(n) for n = 0..340 (rows 0..10)

Row sums are A006125, covering A006129.
Row lengths are A050407.
Counting edges instead of triangles gives A084546, covering A054548.
Column k = 0 is A213434, covering A372168.
The unlabeled version is A263340.
The covering case is A372167, unlabeled A372173.
Column k = 1 is A372172, covering A372171.
For all cycles (not just triangles) we have A372176, covering A372175.
A001858 counts acyclic graphs, unlabeled A005195.
A367867 counts non-choosable graphs, covering A367868.
A372193 counts unicyclic graphs, unlabeled A236570, covering A372191.
Cf. A000088, A000272, A002494, A006785, A053530, A062734, A121251, A372194.

cys[y_]:=Select[Subsets[Union@@y,{3}],MemberQ[y,{#[[1]],#[[2]]}]&&MemberQ[y,{#[[1]],#[[3]]}]&&MemberQ[y,{#[[2]],#[[3]]}]&];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Length[cys[#]]==k&]],{n,0,5},{k,0,Binomial[n,3]}]

Binomial transform of columns of A372167.

a(42) onwards from Andrew Howroyd, Dec 29 2024

A372176 Irregular triangle read by rows where T(n,k) is the number of labeled simple graphs on n vertices with exactly 2k directed cycles of length > 2.

Original entry on oeis.org

1, 1, 2, 7, 1, 38, 19, 0, 6, 0, 0, 0, 1, 291, 317, 15, 220, 0, 0, 70, 55, 0, 0, 0, 0, 30, 15, 0, 0, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Gus Wiseman, Apr 25 2024

A directed cycle in a simple (undirected) graph is a sequence of distinct vertices, up to rotation, such that there are edges between all consecutive elements, including the last and the first.

			Triangle begins (zeros shown as dots):
   1
   1
   2
   7 1
   38 19 . 6 ... 1
   291 317 15 220 .. 70 55 .... 30 15 ........ 10 ............... 1
The T(4,3) = 6 graphs:
  12,13,14,23,24
  12,13,14,23,34
  12,13,14,24,34
  12,13,23,24,34
  12,14,23,24,34
  13,14,23,24,34

Column k = 0 is A001858 (unlabeled A005195), covering A105784.
Row lengths are A002807 + 1.
Row sums are A006125, unlabeled A000088.
Counting edges instead of cycles gives A084546 (covering A054548), unlabeled A008406 (covering A370167).
Counting triangles instead of cycles gives A372170 (covering A372167), unlabeled A263340 (covering A372173).
The covering case is A372175.
Column k = 1 is A372193 (covering A372195), unlabeled A236570.
A006129 counts graphs, unlabeled A002494.
A322661 counts covering loop-graphs, unlabeled A322700.
Cf. A000272, A053530, A137916, A144958, A213434, A367863, A372168, A372169, A372171, A372172, A372191.

cyc[y_]:=Select[Join@@Table[Select[Join@@Permutations/@Subsets[Union@@y,{k}], And@@Table[MemberQ[Sort/@y,Sort[{#[[i]],#[[If[i==k,1,i+1]]]}]],{i,k}]&], {k,3,Length[y]}],Min@@#==First[#]&];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Length[cyc[#]]==2k&]], {n,0,4}, {k,0,Length[cyc[Subsets[Range[n],{2}]]]/2}]

A372191 Number of unlabeled simple graphs covering n vertices with a unique undirected cycle of length > 2.

Original entry on oeis.org

0, 0, 0, 1, 2, 6, 16, 43, 117, 319, 875, 2409, 6692, 18614, 52099, 146186, 411720, 1162295, 3289994, 9330913, 26517036, 75481622, 215201178, 614398459, 1756392061, 5026955216, 14403488345, 41311616835, 118601561506, 340795908579, 980078195995

Offset: 0

Gus Wiseman, Apr 27 2024

nonn

An undirected cycle in a graph is a sequence of distinct vertices, up to rotation and reversal, such that there are edges between all consecutive elements, including the last and the first.

Andrew Howroyd, Table of n, a(n) for n = 0..500
Gus Wiseman, The a(3) = 1 through a(6) = 16 covering graphs with a unique cycle.

For no cycles we have A144958 (non-covering A005195), labeled A105784 (non-covering A001858).
Counting triangles instead of cycles gives A372174 (non-covering A372194), labeled A372171 (non-covering A372172).
The non-covering version is A236570, labeled A372193.
The labeled version is A372195, column k = 1 of A372175.
A002807 counts cycles in a complete graph.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A372167 counts graphs by triangles, non-covering A372170.
A372173 counts unlabeled graphs by triangles (non-covering A263340).
A372176 counts labeled graphs by directed cycles.
Cf. A000055, A137916, A137917, A137918, A140637, A370167, A370169.

First differences of A236570.

a(7) onwards from Andrew Howroyd, Jul 31 2024

A322353 Number of factorizations of n into distinct semiprimes; a(1) = 1 by convention.

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 2, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 2, 1, 1, 1, 1, 0, 2, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0

Offset: 1

Antti Karttunen, Dec 06 2018

nonn

A semiprime (A001358) is a product of any two prime numbers. In the even case, these factorizations have A001222(n)/2 factors. - Gus Wiseman, Dec 31 2020

Records 1, 2, 3, 4, 5, 9, 13, 15, 17, ... occur at 1, 60, 210, 840, 1260, 4620, 27720, 30030, 69300, ...

			a(4) = 1, as there is just one way to factor 4 into distinct semiprimes, namely as {4}.
From _Gus Wiseman_, Dec 31 2020: (Start)
The a(n) factorizations for n = 60, 210, 840, 1260, 4620, 12600, 18480:
  4*15   6*35    4*6*35    4*9*35    4*15*77    4*6*15*35    4*6*10*77
  6*10   10*21   4*10*21   4*15*21   4*21*55    4*6*21*25    4*6*14*55
         14*15   4*14*15   6*10*21   4*33*35    4*9*10*35    4*6*22*35
                 6*10*14   6*14*15   6*10*77    4*9*14*25    4*10*14*33
                           9*10*14   6*14*55    4*10*15*21   4*10*21*22
                                     6*22*35    6*10*14*15   4*14*15*22
                                     10*14*33                6*10*14*22
                                     10*21*22
                                     14*15*22
(End)

Unlabeled multiset partitions of this type are counted by A007717.
The version for partitions is A112020, or A101048 without distinctness.
The non-strict version is A320655.
Positions of zeros include A320892.
Positions of nonzero terms are A320912.
The case of squarefree factors is A339661, or A320656 without distinctness.
Allowing prime factors gives A339839, or A320732 without distinctness.
A322661 counts loop-graphs, ranked by A320461.
A001055 counts factorizations, with strict case A045778.
A001358 lists semiprimes, with squarefree case A006881.
A027187 counts partitions of even length, ranked by A028260.
A037143 lists primes and semiprimes.
A338898/A338912/A338913 give the prime indices of semiprimes.
A339846 counts even-length factorizations, with ordered version A174725.
Cf. A001221, A006125, A006129, A028260, A320893, A338915, A339841.

Table[Count[Subsets[Select[Divisors[n], PrimeOmega[#] == 2 &]], ?(Times @@ # == n &)], {n, 105}] (* _Michael De Vlieger, Dec 11 2020 *)

A322353(n, m=n) = if(1==n, 1, my(s=0); fordiv(n, d, if((2==bigomega(d)&&(d<=m)), s += A322353(n/d, d-1))); (s)); \\ Antti Karttunen, Dec 10 2020

a(n) = Sum_{d|n} (-1)^A001222(d) * A339839(n/d). - Gus Wiseman, Dec 31 2020

A368835 Number of unlabeled n-edge loop-graphs with at most n vertices such that it is not possible to choose a different vertex from each edge.

Original entry on oeis.org

0, 0, 0, 1, 5, 23, 98, 394, 1560, 6181, 24655, 99701, 410513, 1725725, 7423757, 32729320, 148027044, 687188969, 3275077017, 16022239940, 80431483586, 414094461610, 2185052929580, 11808696690600, 65312048149993, 369408792148714, 2135111662435080, 12601466371445619

Offset: 0

Gus Wiseman, Jan 13 2024

nonn

			Non-isomorphic representatives of the a(4) = 5 loop-graphs:
  {{1,1},{2,2},{3,3},{1,2}}
  {{1,1},{2,2},{1,2},{1,3}}
  {{1,1},{2,2},{1,2},{3,4}}
  {{1,1},{2,2},{1,3},{2,3}}
  {{1,1},{1,2},{1,3},{2,3}}

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

The case of a unique choice is A000081, row sums of A106234.
The labeled version is A368596, covering A368730.
Without the choice condition we have A368598.
The complement is A368984, row sums of A368926.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A014068 counts loop-graphs, unlabeled A000666.
A058891 counts set-systems (without singletons A016031), unlabeled A000612.
A322661 counts labeled covering half-loop-graphs, connected A062740.
Cf. A116508, A129271, A133686, A137916, A137917, A333331, A367863, A368836, A368924, A368927.

Table[Length[Union[sysnorm /@ Select[Subsets[Subsets[Range[n],{1,2}],{n}],Select[Tuples[#], UnsameQ@@#&]=={}&]]],{n,0,5}]

a(n) = A368598(n) - A368984(n). - Andrew Howroyd, Jan 14 2024

a(8) onwards from Andrew Howroyd, Jan 14 2024

cp's OEIS Frontend

A263340 Triangle read by rows: T(n,k) is the number of graphs with n vertices containing k triangles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A326293 Number of non-nesting, topologically connected simple graphs with vertices {1..n}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A368984 Number of graphs with loops (symmetric relations) on n unlabeled vertices in which each connected component has an equal number of vertices and edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A369142 Number of labeled loop-graphs covering {1..n} such that it is not possible to choose a different vertex from each edge (non-choosable).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A372169 Number of unlabeled triangle-free graphs covering n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A372170 Irregular triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and exactly k triangles, 0 <= k <= binomial(n,3).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A372176 Irregular triangle read by rows where T(n,k) is the number of labeled simple graphs on n vertices with exactly 2k directed cycles of length > 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A372191 Number of unlabeled simple graphs covering n vertices with a unique undirected cycle of length > 2.

Views

Author

Keywords

Comments

Links

Crossrefs