A185334 -id:A185334 - cp's OEIS frontend

A005638 Number of unlabeled trivalent (or cubic) graphs with 2n nodes.

1, 0, 1, 2, 6, 21, 94, 540, 4207, 42110, 516344, 7373924, 118573592, 2103205738, 40634185402, 847871397424, 18987149095005, 454032821688754, 11544329612485981, 310964453836198311, 8845303172513781271

Offset: 0

N. J. A. Sloane

Because the triangle A051031 is symmetric, a(n) is also the number of (2n-4)-regular graphs on 2n vertices.

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. Brinkmann, Fast generation of cubic graphs, Journal of Graph Theory, 23(2):139-149, 1996.
Jason Kimberley, Not-necessarily connected regular graphs
Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth at least g
R. W. Robinson, Cubic graphs (notes)
Robinson, R. W.; Wormald, N. C., Numbers of cubic graphs, J. Graph Theory 7 (1983), no. 4, 463-467.
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Cubic Graph
Gal Weitz, Lirandë Pira, Chris Ferrie, and Joshua Combes, Sub-universal variational circuits for combinatorial optimization problems, arXiv:2308.14981 [quant-ph], 2023.

Cf. A000421.
Row sums of A275744.
3-regular simple graphs: A002851 (connected), A165653 (disconnected), this sequence (not necessarily connected).
Regular graphs A005176 (any degree), A051031 (triangular array), chosen degrees: A000012 (k=0), A059841 (k=1), A008483 (k=2), this sequence (k=3), A033301 (k=4), A165626 (k=5), A165627 (k=6), A165628 (k=7), A180260 (k=8).
Not necessarily connected 3-regular simple graphs with girth *at least* g: this sequence (g=3), A185334 (g=4), A185335 (g=5), A185336 (g=6).
Not necessarily connected 3-regular simple graphs with girth *exactly* g: A185133 (g=3), A185134 (g=4), A185135 (g=5), A185136 (g=6).

a(n) = A002851(n) + A165653(n).

This sequence is the Euler transformation of A002851.

More terms from Ronald C. Read.

Comment, formulas, and (most) crossrefs by Jason Kimberley, 2009 and 2012

A008484 Number of partitions of n into parts >= 4.

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 5, 5, 7, 8, 11, 12, 16, 18, 24, 27, 34, 39, 50, 57, 70, 81, 100, 115, 140, 161, 195, 225, 269, 311, 371, 427, 505, 583, 688, 791, 928, 1067, 1248, 1434, 1668, 1914, 2223, 2546, 2945, 3370, 3889, 4443, 5113, 5834, 6698

Offset: 0

T. Forbes (anthony.d.forbes(AT)googlemail.com)

a(n) is also the number of not necessarily connected 2-regular graphs on n-vertices with girth at least 4 (all such graphs are simple). The integer i corresponds to the i-cycle; addition of integers corresponds to disconnected union of cycles. - Jason Kimberley, Jan 2011 and Feb 2012
By removing a single part of size 4, an A026797 partition of n becomes an A008484 partition of n - 4. Hence this sequence is essentially the same as A026797. - Jason Kimberley, Feb 2012
Number of partitions of n+3 such that 3*(number of parts) is a part. - Clark Kimberling, Feb 27 2014
Let c(n) be the number of partitions of n such that both (number of parts) and 2*(number of parts) are parts; then c(n) = a(n-6) for n >= 6 and c(n) = 0 for n < 6. - Clark Kimberling, Mar 01 2014
a(n) is also the number of partitions of n for which three times the number of ones is twice the number of parts (conjectured). - George Beck, Aug 19 2017
Proof: Above definition is equivalent to 2 out of 3 parts being equal to 1. Arrange in triples 1, 1, >= 2, etc. Sum of each triple corresponds to sequence definition. - Martin Fuller, Aug 21 2023

Giovanni Resta, Table of n, a(n) for n = 0..1000
Kevin Beanland and Hung Viet Chu, On Schreier-type Sets, Partitions, and Compositions, arXiv:2311.01926 [math.CO], 2023.
Jason Kimberley, Not necessarily connected k-regular graphs with girth at least 4
Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth at least g

2-regular graphs with girth at least 4: A185114 (connected), A185224 (disconnected), this sequence (not necessarily connected).
Not necessarily connected 2-regular graphs with girth at least g [partitions into parts >= g]: A026807 (triangle); chosen g: A000041 (g=1 -- multigraphs with loops allowed), A002865 (g=2 -- multigraphs with loops forbidden), A008483 (g=3), this sequence (g=4), A185325(g=5), A185326 (g=6), A185327 (g=7), A185328 (g=8), A185329 (g=9).
Not necessarily connected 2-regular graphs with girth exactly g [partitions with smallest part g]: A026794 (triangle); chosen g: A002865 (g=2), A026796 (g=3), A026797 (g=4), A026798 (g=5), A026799 (g=6), A026800(g=7), A026801 (g=8), A026802 (g=9), A026803 (g=10).
Not necessarily connected k-regular simple graphs with girth at least 4: A185314 (any k), A185304 (triangle); specified degree k: this sequence (k=2), A185334 (k=3), A185344 (k=4), A185354 (k=5), A185364 (k=6).

a:= func< n | NumberOfPartitions(n)-NumberOfPartitions(n-1)-NumberOfPartitions(n-2)+ NumberOfPartitions(n-4)+NumberOfPartitions(n-5)- NumberOfPartitions(n-6) >; [1,0,0,0,1,1,1] cat [ a(n) : n in [7..60]]; // Vincenzo Librandi, Aug 20 2017

R:=PowerSeriesRing(Integers(), 60); Coefficients(R!( 1/(&*[1-x^(m+4): m in [0..70]]) )); // G. C. Greubel, Nov 03 2019

series(1/product((1-x^i),i=4..65),x,60); # end of program
ZL := [ B,{B=Set(Set(Z, card>=4))}, unlabeled ]: seq(combstruct[count](ZL, size=n), n=0..60); # Zerinvary Lajos, Mar 13 2007

f[1, 1]=1; f[n_, k_]:= f[n, k] = If[n<0, 0, If[k>n, 0, If[k==n, 1, f[n, k +1] + f[n-k, k]]]]; Table[f[n, 4], {n, 60}] (* end of program *)
Drop[Table[Count[IntegerPartitions[n], p_ /; MemberQ[p, 3*Length[p]]], {n, 60}],2]  (* Clark Kimberling, Feb 27 2014 *)
Table[Count[IntegerPartitions[n],
  p_ /; 3 Count[p, 1] == 2 Length[p]], {n, 0, 60}] (* George Beck Aug 19 2017 *)
CoefficientList[Series[1/QPochhammer[x^4, x], {x,0,60}], x] (* G. C. Greubel, Nov 03 2019 *)

my(x='x+O('x^60)); Vec(1/prod(m=0,70, 1-x^(m+4))) \\ G. C. Greubel, Nov 03 2019

def A008484_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 1/product((1-x^(m+4)) for m in (0..70)) ).list()
A008484_list(60) # G. C. Greubel, Nov 03 2019

G.f.: 1 / Product_{m>=4} (1 - x^m).
Euler transformation of A185114. - Jason Kimberley, Jan 30 2011
Given by p(n) - p(n-1) - p(n-2) + p(n-4) + p(n-5) - p(n-6) where p(n) = A000041(n). Generally, 1/Product_{i>=K} (1 - x^i) is given by p({A}), where {A} is defined over the coefficients of Product_{i=1..K-1} (1 - x^i). In this case, K=4, so (1-x)(1-x^2)(1-x^3) = 1 - x - x^2 + x^4 + x^5 - x^6, defining {A} as above. G.f.: 1 + Sum_{i>=1} (x^4i)/Product_{j=1..i}(1 - x^j). - Jon Perry, Jul 04 2004
a(n) ~ exp(Pi*sqrt(2*n/3)) * Pi^3 / (12*sqrt(2)*n^(5/2)). - Vaclav Kotesovec, Jun 02 2018
G.f.: exp(Sum_{k>=1} x^(4*k)/(k*(1 - x^k))). - Ilya Gutkovskiy, Aug 21 2018
G.f.: 1 + Sum_{n >= 1} x^(n+3)/Product_{k = 0..n-1} (1 - x^(k+4)). - Peter Bala, Dec 01 2024

A014371 Number of trivalent connected simple graphs with 2*n nodes and girth at least 4.

Original entry on oeis.org

1, 0, 0, 1, 2, 6, 22, 110, 792, 7805, 97546, 1435720, 23780814, 432757568, 8542471494, 181492137812, 4127077143862

Offset: 0

N. J. A. Sloane

The null graph on 0 vertices is vacuously connected and 3-regular; since it is acyclic, it has infinite girth. - Jason Kimberley, Jan 29 2011

CRC Handbook of Combinatorial Designs, 1996, p. 647.

G. Brinkmann, J. Goedgebeur and B. D. McKay, Generation of Cubic graphs, Discrete Mathematics and Theoretical Computer Science, 13 (2) (2011), 69-80. (hal-00990486)
House of Graphs, Cubic graphs.
Jason Kimberley, Connected regular graphs with girth at least 4
Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth at least g
M. Meringer, Tables of Regular Graphs.
M. Meringer, Fast generation of regular graphs and construction of cages, J. Graph Theory 30 (2) (1999) 137-146.

From Jason Kimberley, Jun 28 2010 and Jan 29 2011: (Start)
3-regular simple graphs with girth at least 4: this sequence (connected), A185234 (disconnected), A185334 (not necessarily connected).
Connected k-regular simple graphs with girth at least 4: A186724 (any k), A186714 (triangle); specified degree k: A185114 (k=2), this sequence (k=3), A033886 (k=4), A058275 (k=5), A058276 (k=6), A181153 (k=7), A181154 (k=8), A181170 (k=9).
Connected 3-regular simple graphs with girth at least g: A185131 (triangle); chosen g: A002851 (g=3), this sequence (g=4), A014372 (g=5), A014374 (g=6), A014375 (g=7), A014376 (g=8).
Connected 3-regular simple graphs with girth exactly g: A198303 (triangle); chosen g: A006923 (g=3), A006924 (g=4), A006925 (g=5), A006926 (g=6), A006927 (g=7). (End)

A[s_Integer] := With[{s6 = StringPadLeft[ToString[s], 6, "0"]}, Cases[ Import["https://oeis.org/A" <> s6 <> "/b" <> s6 <> ".txt", "Table"], {, }][[All, 2]]];
A002851 = A@002851;
A006923 = A@006923;
a[n_] := A002851[[n + 1]] - A006923[[n + 1]];
a /@ Range[0, 16] (* Jean-François Alcover, Jan 27 2020 *)

Terms a(14) and a(15) appended, from running Meringer's GENREG for 4.2 and 93.2 processor days at U. Newcastle, by Jason Kimberley on Jun 28 2010

a(16), from House of Graphs, by Jan Goedgebeur et al., added by Jason Kimberley, Feb 15 2011

A185314 Number of, not necessarily connected, regular simple graphs on n vertices with girth at least 4.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 4, 2, 7, 3, 14, 6, 44, 37, 350, 1616, 18042, 193919, 2867779, 32674078, 1581632332, 6705889886

Offset: 0

Jason Kimberley, May 23 2012

Jason Kimberley, Not necessarily connected k-regular graphs with girth at least 4
Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth at least g

Regular graphs, of any degree, with girth at least 4: A186724 (connected), A185214 (disconnected), this sequence (not-necessarily connected).
Not necessarily connected k-regular simple graphs with girth at least 4: this sequence (any k), A185304 (triangle); specified degree k: A008484 (k=2), A185334 (k=3), A185344 (k=4), A185354 (k=5), A185364 (k=6).
Not necessarily connected regular simple graphs with girth at least g: A005176 (g=3), this sequence (g=4), A185315 (g=5), A185316 (g=6), A185317 (g=7), A185318 (g=8), A185319 (g=9).

a(n) = A186724(n) + A185214(n).

a(n) is the sum of the n-th row of A185304.

A185133 Number of not necessarily connected 3-regular simple graphs on 2n vertices with girth exactly 3.

Original entry on oeis.org

0, 0, 1, 1, 4, 15, 71, 428, 3406, 34270, 418621, 5937051, 94782437, 1670327647, 32090011476, 666351752261, 14859579573845

Offset: 0

Jason Kimberley, Mar 21 2012

Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth exactly g

Not necessarily connected k-regular simple graphs girth exactly 3: A198313 (any k), A185643 (triangle); fixed k: A026796 (k=2), this sequence (k=3), A185143 (k=4), A185153 (k=5), A185163 (k=6).

Not necessarily connected 3-regular simple graphs on 2n vertices with girth exactly g: A185130 (triangle); fixed g: this sequence (g=3), A185134 (g=4), A185135 (g=5), A185136 (g=6).

a(n) = A005638(n) - A185334(n).

a(n) = A006923(n) + A185033(n).

A185134 Number of, not necessarily connected, 3-regular simple graphs on 2n vertices with girth exactly 4.

Original entry on oeis.org

0, 0, 0, 1, 2, 5, 21, 103, 752, 7385, 91939, 1345933, 22170664, 401399440, 7887389438, 166897766824, 3781593764772

Offset: 0

Jason Kimberley, Mar 21 2012

Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth exactly g

Not necessarily connected k-regular simple graphs girth exactly 4: A198314 (any k), A185644 (triangle); fixed k: A026797 (k=2), this sequence (k=3), A185144 (k=4).

Not necessarily connected 3-regular simple graphs on 2n vertices with girth exactly g: A185130 (triangle); fixed g: A185133 (g=3), this sequence (g=4), A185135 (g=5), A185136 (g=6).

a(n) = A185334(n) - A185335(n).

a(n) = A006924(n) + A185034(n).

A185304 Triangular array E(n,k) counting not necessarily connected k-regular simple graphs on n vertices with girth at least 4.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 2, 2, 1, 1, 0, 2, 0, 0, 1, 1, 3, 6, 2, 1, 1, 0, 3, 0, 2, 0, 1, 1, 5, 23, 12, 1, 1, 1, 0, 5, 0, 31, 0, 0, 1, 1, 7, 112, 220, 7, 1, 1, 1, 0, 8, 0, 1606, 0, 1, 0, 1, 1, 11, 801, 16829, 388, 9, 1, 1, 1, 0, 12, 0, 193900, 0, 6, 0, 0, 1, 1, 16, 7840, 2452820, 406824, 267, 8, 1, 1, 1, 0, 18, 0, 32670332, 0, 3727, 0, 0, 0

Offset: 1

Jason Kimberley, Jan 19 2013

Row sums give A185314.

			1: 1;
2: 1, 1;
3: 1, 0;
4: 1, 1, 1;
5: 1, 0, 1;
6: 1, 1, 1, 1;
7: 1, 0, 1, 0;
8: 1, 1, 2, 2, 1;
9: 1, 0, 2, 0, 0;
10: 1, 1, 3, 6, 2, 1;
11: 1, 0, 3, 0, 2, 0;
12: 1, 1, 5, 23, 12, 1, 1;
13: 1, 0, 5, 0, 31, 0, 0;
14: 1, 1, 7, 112, 220, 7, 1, 1;
15: 1, 0, 8, 0, 1606, 0, 1, 0;
16: 1, 1, 11, 801, 16829, 388, 9, 1, 1;
17: 1, 0, 12, 0, 193900, 0, 6, 0,0;
18: 1, 1, 16, 7840, 2452820, 406824, 267, 8, 1, 1;
19: 1, 0, 18, 0, 32670332, 0, 3727, 0,0, 0;
20: 1, 1, 24, 97723, 456028489, 1125022326, 483012, 741, 13, 1, 1;
21: 1, 0, 27, 0, 6636066134, 0, 69823723, 0, 1, 0, 0;
22: 1, 1, 34, 1436873, 100135577994, 3813549359275, 14836130862, 2887493, ?, 14, 1;

Jason Kimberley, Table of n, a(i)=E(n,k) for i = 1..139 (n = 1..22)
Jason Kimberley, Not necessarily connected k-regular graphs with girth at least 4
Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth at least g

Not necessarily connected k-regular simple graphs with girth at least 4: A185314 (any k), this sequence (triangle); specified degree k: A008484 (k=2), A185334 (k=3), A185344 (k=4), A185354 (k=5), A185364 (k=6).

E(n,k) = A186714(n,k) + A185204(n,k).

E(10,2) corrected by the author, Mar 26 2013

a(32)=E(10,2) in b-file corrected as above by Andrew Howroyd, Feb 22 2018

A185335 Number of not necessarily connected 3-regular simple graphs on 2n vertices with girth at least 5.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 2, 9, 49, 455, 5784, 90940, 1620491, 31478651, 656784488, 14621878339, 345975756388

Offset: 0

Jason Kimberley, Jan 28 2011

Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth at least g

3-regular simple graphs with girth at least 5: A014372 (connected), A185235 (disconnected), this sequence (not necessarily connected).
Not necessarily connected 3-regular simple graphs with girth *at least* g: A005638 (g=3), A185334 (g=4), this sequence (g=5), A185336 (g=6).
Not necessarily connected 3-regular simple graphs with girth *exactly* g: A185133 (g=3), A185134 (g=4), A185135 (g=5), A185136 (g=6).
Not necessarily connected k-regular simple graphs with girth at least 5: A185315 (any k), A185305 (triangle); specified degree k: A185325 (k=2), this sequence (k=3).

A014372 = Cases[Import["https://oeis.org/A014372/b014372.txt", "Table"], {, }][[All, 2]];
(* EulerTransform is defined in A005195 *)
EulerTransform[Rest @ A014372] (* Jean-François Alcover, Dec 04 2019, updated Mar 18 2020 *)

This sequence is the Euler transformation of A014372.

A185344 Number of not necessarily connected 4-regular simple graphs on n vertices with girth at least 4.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 2, 12, 31, 220, 1606, 16829, 193900, 2452820, 32670332, 456028489, 6636066134, 100135577994, 1582718914660

Offset: 0

Jason Kimberley, Nov 03 2011

Jason Kimberley, Not necessarily connected k-regular graphs with girth at least 4
Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth at least g

4-regular simple graphs with girth at least 4: A033886 (connected), A185244 (disconnected), this sequence (not necessarily connected).

Not necessarily connected k-regular simple graphs with girth at least 4: A185314 (any k), A185304 (triangle); specified degree k: A008484 (k=2), A185334 (k=3), this sequence (k=4), A185354 (k=5), A185364 (k=6).

A033886 = Cases[Import["https://oeis.org/A033886/b033886.txt", "Table"], {, }][[All, 2]];
(* EulerTransform is defined in A005195 *)
EulerTransform[Rest @ A033886] (* Jean-François Alcover, Dec 04 2019, updated Mar 18 2020 *)

This sequence is the Euler transformation of A033886.

a(n) = A033886(n) + A185244(n).

A185354 Number of not necessarily connected 5-regular simple graphs on 2n vertices with girth at least 4.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 1, 7, 388, 406824, 1125022326, 3813549359275

Offset: 0

Jason Kimberley, Nov 04 2011

Jason Kimberley, Not necessarily connected k-regular graphs with girth at least 4
Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth at least g

5-regular simple graphs on 2n vertices with girth at least 4: A058275 (connected), A185254 (disconnected), this sequence (not necessarily connected).

Not necessarily connected k-regular simple graphs with girth at least 4: A185314 (any k), A185304 (triangle); specified degree k: A008484 (k=2), A185334 (k=3), A185344 (k=4), this sequence (k=5), A185364 (k=6).

A058275 = Cases[Import["https://oeis.org/A058275/b058275.txt", "Table"], {, }][[All, 2]];
(* EulerTransform is defined in A005195 *)
EulerTransform[Rest @ A058275]  (* Jean-François Alcover, Dec 04 2019, updated Mar 18 2020 *)

This sequence is the Euler transformation of A058275.

a(n) = A058275(n) + A185254(n).

cp's OEIS Frontend

A005638 Number of unlabeled trivalent (or cubic) graphs with 2n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A008484 Number of partitions of n into parts >= 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Magma

Maple

Mathematica

PARI

Sage

Formula

A014371 Number of trivalent connected simple graphs with 2*n nodes and girth at least 4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Extensions

A185314 Number of, not necessarily connected, regular simple graphs on n vertices with girth at least 4.

Views

Author

Keywords

Links

Crossrefs

Formula

A185133 Number of not necessarily connected 3-regular simple graphs on 2n vertices with girth exactly 3.

Views

Author

Keywords

Links

Crossrefs

Formula

A185134 Number of, not necessarily connected, 3-regular simple graphs on 2n vertices with girth exactly 4.

Views

Author

Keywords

Links

Crossrefs

Formula

A185304 Triangular array E(n,k) counting not necessarily connected k-regular simple graphs on n vertices with girth at least 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A185335 Number of not necessarily connected 3-regular simple graphs on 2n vertices with girth at least 5.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A185344 Number of not necessarily connected 4-regular simple graphs on n vertices with girth at least 4.

Views

Author