A001205 -id:A001205 - cp's OEIS frontend

A110041 a(n) = number of labeled graphs on n vertices (with no isolated vertices, multi-edges or loops) such that the degree of every vertex is at most 3.

1, 0, 1, 4, 41, 512, 8285, 166582, 4054953, 116797432, 3912076929, 150190759240, 6532014077809, 318632936830136, 17286883399233149, 1035508343364348938, 68053563847088272945, 4879593083836366195728, 379847137967853770523937, 31960371880691511556886988

Offset: 0

Marni Mishna, Jul 08 2005

P-recursive.

			Graphs listed by edgeset: a(3) = 4: {(1,2), (2,3)}, {(1,3), (2,3)}, {(1,3), (1,2)}, {(2,3), (1,2), (1,3)}.

Goulden, I. P.; Jackson, D. M. Labelled graphs with small vertex degrees and $P$-recursiveness. SIAM J. Algebraic Discrete Methods 7(1986), no. 1, 60--66. MR0819706 (87k:05093) [Gives e.g.f.]

Alois P. Heinz, Table of n, a(n) for n = 0..150

Cf. A110040, A110039, A002829, A001205, A001147.

Satisfies the linear recurrence: (-150917976*n^2 - 105258076*n^3 - 1925*n^9 - 13339535*n^5 - 45995730*n^4 - 357423*n^7 - 2637558*n^6 - 120543840*n - n^11 - 66*n^10 - 39916800 - 32670*n^8)*a(n) + (22057180*n^4 + 2*n^10 + 69934280*n^3 + 140581872*n^2 + 161254080*n + 4621890*n^5 + 79833600 + 130*n^9 + 3720*n^8 + 61620*n^7 + 653226*n^6)*a(n + 1) +
(3*n^10 + 6932835*n^5 + 5580*n^8 + 92430*n^7 + 979839*n^6 + 241881120*n + 33085770*n^4 + 104901420*n^3 + 210872808*n^2 + 119750400 + 195*n^9)*a(n + 2) + (6932520*n^3 + 39916800 + 136080*n^5 + 24168936*n^2 + 9324*n^6 + 47363040*n + 1223334*n^4 + 6*n^8 + 360*n^7)*a(n + 3) + (6*n^8 + 1431654*n^4 + 372*n^7 + 9996*n^6 + 152040*n^5 + 59875200 + 8545908*n^3 + 31580424*n^2 + 66054960*n)*a(n + 4) + (9100956*n + 6*n^7 + 9646560 + 3631220*n^2 + 335*n^6 + 7929*n^5 + 103085*n^4 + 794709*n^3)*a(n + 5) +
(492*n^6 + 9*n^7 + 11032560 + 11359*n^5 + 143385*n^4 + 1067026*n^3 + 4671483*n^2 + 11110486*n)*a(n + 6) + (1021680 + 1041*n^4 + 17838*n^3 + 150699*n^2 + 626358*n + 24*n^5)*a(n + 7) + (461340 + 7027*n^3 + 9*n^5 + 61461*n^2 + 267044*n + 399*n^4)*a(n + 8) + (100980 + 5751*n^2 + 9*n^4 + 39408*n + 372*n^3)*a(n + 9) + (-6414*n - 588*n^2 - 18*n^3 - 23364)*a(n + 10) + (-48*n - 528)*a(n + 11) + 24*a(n + 12) = 0.
Differential equation satisfied by the exponential generating function: {F(0) = 1, 9*t^4*(t^4 + t + t^2 - 2)^2*(d^2/dt^2)F(t) + 3*t*(-4*t^6 + 8*t^5 - 16*t + t^10 - 16*t^2 + 2*t^7 + 8 - 2*t^4 + 2*t^8 + 10*t^3)*(t^4 + t + t^2 - 2)*(d/dt)F(t) - t^2*(t^4 + t + t^2 - 2)*(t^10 - 2*t^9 - 6*t^7 - 12*t^6 + t^5 - t^4 + 39*t^3 - 10*t^2 + 24)*F(t)}.
Satisfies the recurrence (of order 8): 12*(81*n^4 - 837*n^3 + 2997*n^2 - 4326*n + 1987)*a(n) = 18*(n-1)*(81*n^4 - 810*n^3 + 2709*n^2 - 3435*n + 1036)*a(n-1) + 3*(n-1)*(243*n^6 - 2997*n^5 + 14499*n^4 - 35118*n^3 + 44823*n^2 - 26766*n + 3244)*a(n-2) + 3*(n-2)*(n-1)*(81*n^5 - 1080*n^4 + 4968*n^3 - 9825*n^2 + 7666*n - 178)*a(n-3) + (n-3)*(n-2)*(n-1)*(243*n^5 - 2430*n^4 + 8721*n^3 - 13896*n^2 + 8637*n - 2468)*a(n-4) + (n-4)*(n-3)*(n-2)*(n-1)*(405*n^4 - 3537*n^3 + 11934*n^2 - 15915*n + 6008)*a(n-5) + (n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(243*n^5 - 2916*n^4 + 11799*n^3 - 19593*n^2 + 11382*n + 502)*a(n-6) + (n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(162*n^4 - 1026*n^3 + 2241*n^2 - 1884*n + 182)*a(n-7) - (n-7)*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(81*n^4 - 513*n^3 + 972*n^2 - 519*n - 98)*a(n-8). - Vaclav Kotesovec, Sep 10 2014
a(n) ~ 3^(n/2) * exp(sqrt(3*n) - 3*n/2 - 5/4) * n^(3*n/2) / 2^(n + 1/2) * (1 + 23/(24*sqrt(3*n))). - Vaclav Kotesovec, Nov 04 2023, extended Nov 06 2023
Limit_{n->oo} A110041(n)/A110040(n) = exp(2). - Vaclav Kotesovec, Nov 05 2023

Edited and extended by Max Alekseyev, Apr 28 2010

A144163 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: T(n,k) = number of simple graphs on n labeled nodes with k edges where each maximally connected subgraph is either a tree or a cycle.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 3, 3, 1, 1, 6, 15, 20, 3, 1, 10, 45, 120, 150, 12, 1, 15, 105, 455, 1185, 1473, 70, 1, 21, 210, 1330, 5565, 14469, 18424, 465, 1, 28, 378, 3276, 19635, 81060, 213990, 280200, 3507, 1, 36, 630, 7140, 57393, 334656, 1385076, 3732300, 5029218, 30016

Offset: 0

Alois P. Heinz, Sep 12 2008

			T(4,3) = 20, because there are 20 simple graphs on 4 labeled nodes with 3 edges, where each maximally connected subgraph is either a tree or a cycle, 16 of these graphs consist of a single tree with 4 nodes and 4 consist of a cycle with 3 and a tree with 1 node:
  .1-2. .1-2. .1.2. .1.2. .1-2. .1-2. .1-2. .1-2. .1-2. .1.2.
  .|\.. ../|. ..\|. .|/.. .|... ...|. ../.. ..\.. .|.|. .|.|.
  .4.3. .4.3. .4-3. .4-3. .4-3. .4-3. .4-3. .4-3. .4.3. .4-3.
  .
  .1.2. .1.2. .1-2. .1.2. .1.2. .1.2. .1.2. .1.2. .1-2. .1-2.
  .|/|. .|\|. ..X.. ..X|. ..X.. .|X.. ../|. .|\.. .|/.. ..\|.
  .4.3. .4.3. .4.3. .4.3. .4-3. .4.3. .4-3. .4-3. .4.3. .4.3.
Triangle begins:
  1;
  1,  0;
  1,  1,  0;
  1,  3,  3,   1;
  1,  6, 15,  20,   3;
  1, 10, 45, 120, 150, 12;

Alois P. Heinz, Rows n = 0..140, flattened
Index entries for sequences related to trees

Columns k=0-3 give: A000012, A000217, A050534, A093566.
Main diagonal gives A001205.
Row sums give A144164.
Cf. A138464, A144161, A007318, A000142.

f:= proc(n,k) option remember; local j; if k=0 then 1 elif k<0 or n<=k then 0 elif k=n-1 then n^(n-2) else add(binomial(n-1,j) *f(j+1,j) *f(n-1-j,k-j), j=0..k) fi end:
c:= proc(n,k) option remember; local i,j; if k=0 then 1 elif k<0 or n

f[n_, k_] := f[n, k] = Which[k == 0, 1, k<0 || n <= k, 0, k == n-1, n^(n-2), True, Sum[Binomial[n-1, j]*f[j+1, j]*f[n-1-j, k-j], {j, 0, k}]]; c[n_, k_] := c[n, k] = Which[k == 0, 1 , k<0 || nJean-François Alcover, Jan 21 2014, translated from Alois P. Heinz's Maple code *)

T(n,k) = A138464(n,k) + Sum_{j=3..k} C(n,j) A138464(n-j,k-j) A144161 (j,j).

A338978 Number of labeled 5-regular graphs on 2n nodes.

Original entry on oeis.org

1, 0, 0, 1, 3507, 66462606, 2977635137862, 283097260184159421, 52469332407700365320163, 17647883828569858659972268092, 10148613081040117624319536901932188, 9494356410654311931931879706070629989407, 13859154719468565627065764000731047706917194485

Offset: 0

Atabey Kaygun, Dec 18 2020

nonn

Marni Mishna, Table of n, a(n) for n = 0..110 (first 51 terms from Brendan Mackay)
Frédéric Chyzak and Marni Mishna, Differential equations satisfied by generating functions of 5-, 6-, and 7-regular labelled graphs: a reduction based approach, arXiv:2406.04753 [math.CO], 2024.
Élie de Panafieu, Asymptotic expansion of regular and connected regular graphs, arXiv:2408.12459 [math.CO], 2024. See p. 9.
Atabey Kaygun, Counting Graphs with a Prescribed Degree Sequence.
Atabey Kaygun, Enumerating Labeled Graphs that Realize a Fixed Degree Sequence, arXiv:2101.02299 [math.CO], 2021.

With interspersed zeros, column k=5 of A059441.

Cf. A001205, A002829, A005815, A165626 (unlabeled case).

A369931 Triangle read by rows: T(n,k) is the number of labeled simple graphs with n edges and k vertices and without endpoints or isolated vertices.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 3, 0, 0, 0, 6, 12, 0, 0, 0, 1, 85, 70, 0, 0, 0, 0, 100, 990, 465, 0, 0, 0, 0, 45, 2805, 11550, 3507, 0, 0, 0, 0, 10, 3595, 59990, 140420, 30016, 0, 0, 0, 0, 1, 2697, 147441, 1174670, 1802682, 286884, 0, 0, 0, 0, 0, 1335, 222516, 4710300, 22467312, 24556140, 3026655

Offset: 1

Andrew Howroyd, Feb 08 2024

T(n,k) is the number of traceless symmetric binary matrices with 2n 1's and k rows and at least two 1's in every row.

			Triangle begins:
  0;
  0, 0;
  0, 0, 1;
  0, 0, 0, 3;
  0, 0, 0, 6,  12;
  0, 0, 0, 1,  85,   70;
  0, 0, 0, 0, 100,  990,    465;
  0, 0, 0, 0,  45, 2805,  11550,    3507;
  0, 0, 0, 0,  10, 3595,  59990,  140420,   30016;
  0, 0, 0, 0,   1, 2697, 147441, 1174670, 1802682, 286884;
  ...
The T(3,3) = 1 matrix is:
  [0 1 1]
  [1 0 1]
  [1 1 0]
The T(4,4) = 3 matrices are:
  [0 0 1 1]  [0 1 0 1]  [0 1 1 0]
  [0 0 1 1]  [1 0 1 0]  [1 0 0 1]
  [1 1 0 0]  [0 1 0 1]  [1 0 0 1]
  [1 1 0 0]  [1 0 1 0]  [0 1 1 0]

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

Row sums are A370059.
Column sums are A100743.
Main diagonal is A001205.
Cf. A369928, A369932 (unlabeled).

G(n)={my(A=x/exp(x*y + O(x*x^n))); exp(y*x^2/2 - x + O(x*x^n)) * sum(k=0, n, (1 + y + O(y*y^n))^binomial(k, 2)*A^k/k!)}
T(n)={my(r=Vec(substvec(serlaplace(G(n)), [x, y], [y, x]))); vector(#r-1, i, Vecrev(Pol(r[i+1]/y), i))}

T(n,k) = k!*[x^k][y^n] exp(y*x^2/2 - x) * Sum_{j>=0} (1 + y)^binomial(j, 2)*(x/exp(y*x))^j/j!.

A370059 Number of traceless symmetric binary matrices with 2n 1's and all row sums >= 2.

Original entry on oeis.org

1, 0, 0, 1, 3, 18, 156, 1555, 17907, 234031, 3414375, 54984258, 968680368, 18532158756, 382616109012, 8479409847277, 200776196593073, 5058600736907013, 135130222251100358, 3814891312969572209, 113492694557655580989, 3548800852807887882157, 116359373033373284971070

Offset: 0

Andrew Howroyd, Feb 08 2024

nonn

			The a(3) = 1 matrix is:
  [0 1 1]
  [1 0 1]
  [1 1 0]
The a(4) = 3 matrices are:
  [0 0 1 1]  [0 1 0 1]  [0 1 1 0]
  [0 0 1 1]  [1 0 1 0]  [1 0 0 1]
  [1 1 0 0]  [0 1 0 1]  [1 0 0 1]
  [1 1 0 0]  [1 0 1 0]  [0 1 1 0]

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

Row sums of A369931.

Cf. A001205 (row sums of matrices exactly 2).

G(n)={my(A=x/exp(x*y + O(x*x^n))); exp(y*x^2/2 - x + O(x*x^n)) * sum(k=0, n, (1 + y + O(y*y^n))^binomial(k, 2)*A^k/k!)}
seq(n)={Vec(subst(Pol(serlaplace(G(n))), x, 1))}

A201013 Triangular array read by rows: T(n,k) is the number of 2-regular labeled graphs on n nodes that have exactly k connected components (cycles); n>=3, 1<=k<=floor(n/3).

Original entry on oeis.org

1, 3, 12, 60, 10, 360, 105, 2520, 987, 20160, 9576, 280, 181440, 99144, 6300, 1814400, 1104840, 107415, 19958400, 13262040, 1708245, 15400, 239500800, 171119520, 27042444, 600600, 3113510400, 2366076960, 437729292, 16186170, 43589145600, 34941291840, 7335055728, 382056675, 1401400

Offset: 3

Geoffrey Critzer, Nov 25 2011

A 2-regular labeled graph is a simple labeled graph such that every vertex has degree 2.

			1;
3;
12;
60,     10;
360,    105;
2520,   987;
20160,  9576,    280;
181440, 99144,   6300;

Alois P. Heinz, Rows n = 3..170, flattened

Cf. A001205 (row sums), A001710(n-1) (first row).

T:= proc(n, k) option remember; `if`(k=1, (n-1)!/2,
      add(binomial(n-1, j-1) *T(j,1) *T(n-j, k-1), j=3..n-3))
    end:
seq(seq(T(n, k), k=1..n/3), n=3..14); # Alois P. Heinz, Nov 25 2011

f[list_]:=Select[list,#>0&];Flatten[Drop[Map[f, a = Log[1/(1 - x)]/2 - x/2 - x^2/4; Range[0, 20]! CoefficientList[Series[Exp[y a], {x, 0, 20}], {x, y}]], 3]]

E.g.f.: exp(-xy/2-x^2y/4)/(1-x)^(y/2).
T(n,1) = (n-1)!/2, T(n,k) = Sum_{j=3..n-3} C(n-1,j-1)*T(j,1)*T(n-j,k-1) for k>1. - Alois P. Heinz, Nov 25 2011
Sum_{k=1..floor(n/3)} T(n,k)*2^k = A038205(n) the number of permutations with minimum cycle size of 3. - Geoffrey Critzer, Nov 05 2012

A202065 The number of simple labeled graphs on 2n nodes whose connected components are even length cycles.

Original entry on oeis.org

1, 0, 3, 60, 2835, 219240, 25519725, 4169185020, 910363278825, 256123949281200, 90240816705714675, 38923077574032151500, 20174526711617730727275, 12373285262231460281715000, 8863077725980930704895768125, 7332455066541096999983523547500

Offset: 0

Geoffrey Critzer, Dec 10 2011

nonn

Robert Israel, Table of n, a(n) for n = 0..225

Cf. A001205, A053532, A053533.

f:= gfun:-rectoproc({(4*n^3-n)*a(n-1) + (4*n^2+2*n)*a(n) - a(n+1)=0,a(0)=1,a(1)=0},a(n),remember):
map(f, [$0..30]); # Robert Israel, Mar 02 2017

nn = 30; a = Log[1/(1 - x^2)^(1/4)] - x^2/4; Table[i, {i, 0, nn, 2}]! CoefficientList[Series[Exp[a], {x, 0, nn}], x][[Table[i, {i, 1, nn+1, 2}]]]
Table[((2 n)!/n!) HypergeometricPFQ[{1/4, -n}, {}, 4] (-1/4)^n, {n, 0, 15}] (* Benedict W. J. Irwin, May 24 2016 *)

E.g.f. for aerated sequence: exp(-x^2/4)/(1-x^2)^(1/4).
a(n) ~ (2*n)! * 2^(1/4)*exp(-1/4)*Gamma(3/4)/((2*n)^(3/4)*Pi). - Vaclav Kotesovec, Sep 24 2013
a(n) = ((2n)!/n!)*2F0(1/4,-n;;4)*(-1/4)^n. - Benedict W. J. Irwin, May 24 2016
(4n^3-n)a(n-1) + (4n^2+2n)a(n) - a(n+1) = 0. - Robert Israel, Mar 02 2017

a(14) and e.g.f. corrected by Robert Israel, Mar 02 2017

A202081 The number of simple labeled graphs on n nodes whose connected components are cycles, stars, wheels, or paths.

Original entry on oeis.org

1, 1, 2, 8, 46, 298, 2206, 19009, 187076, 2053349, 24800484, 327067043, 4677505768, 72075818159, 1189985755128, 20952274850927, 391829421176768, 7755079821666945, 161926610838369418, 3556807008080385549, 81979632030102053376, 1978135038931568355707

Offset: 0

Geoffrey Critzer, Dec 10 2011

nonn

Here a cycle is of length 3 or more, a star has at least 4 (total) vertices, a wheel has at least 4 (total) vertices, and a path can be an isolated vertex.

R. P. Stanley, Enumerative Combinatorics Volume 2, Cambridge 1999, problem 5.15

G. C. Greubel, Table of n, a(n) for n = 0..440

Cf. A001205, A053530, A053531, A011800.

nn = 16; a = x/(2 (1 - x)) + x/2; b = x^4/4! + Sum[(n (n - 2)!/2) x^n/n!, {n, 5, nn}]; c = x Exp[x] - x^3/2 - x^2 - x; d = -x/2 - x^2/4; Range[0, nn]! CoefficientList[Series[Exp[a]*Exp[b]*Exp[c]*Exp[d]/(1 - x)^(1/2), {x, 0, nn}], x]

E.g.f.: exp(x/2+x/(2*(1-x))) * exp(-x^2/2-x^3/4-x^4/8)/(1-x)^(x/2) * exp(-x-x^2-x^3/2 + x*exp(x)) * exp(-x/2-x^2/4)/(1-x)^(1/2). [corrected by Jason Yuen, Feb 17 2025]

A211774 Number of rooted 2-regular labeled graphs on n nodes.

Original entry on oeis.org

0, 0, 0, 3, 12, 60, 420, 3255, 28056, 270144, 2868840, 33293205, 419329020, 5697423732, 83069039508, 1293734268645, 21436030749840, 376516868504160, 6988441065717744, 136675039085498691, 2809247116432575420, 60543293881318183740, 1365186080156105513460

Offset: 0

Geoffrey Critzer, May 18 2012

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..170

egf:= x *diff(exp(-x/2-x^2/4)/sqrt(1-x), x):
a:= n-> n! * coeff(series(egf, x, n+1), x, n):
seq(a(n), n=0..30);  # Alois P. Heinz, May 18 2012

nn = 20; a = Log[1/(1 - x)]/2 - x/2 - x^2/4; Drop[Range[0, nn]! CoefficientList[Series[x D[Exp[a], x], {x, 0, nn}], x], 3]

a(n) = n*A001205(n).
E.g.f.: x*A'(x) where A(x) = exp(-x/2-x^2/4)/sqrt(1-x) is the e.g.f. for A001205.
a(n) ~ sqrt(2) * n^(n+1) / exp(n+3/4). - Vaclav Kotesovec, Aug 22 2014

A322706 Regular triangle read by rows where T(n,k) is the number of k-regular k-uniform hypergraphs spanning n vertices.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 3, 1, 0, 1, 12, 12, 1, 0, 1, 70, 330, 70, 1, 0, 1, 465, 11205, 11205, 465, 1, 0, 1, 3507, 505505, 2531200, 505505, 3507, 1, 0

Offset: 1

Gus Wiseman, Dec 23 2018

We define a hypergraph to be any finite set of finite nonempty sets. A hypergraph is k-uniform if all edges contain exactly k vertices, and k-regular if all vertices belong to exactly k edges. The span of a hypergraph is the union of its edges.

			Triangle begins:
  1
  1       0
  1       1       0
  1       3       1       0
  1      12      12       1       0
  1      70     330      70       1       0
  1     465   11205   11205     465       1       0
  1    3507  505505 2531200  505505    3507       1       0
Row 4 counts the following hypergraphs:
  {{1}{2}{3}{4}}  {{12}{13}{24}{34}}  {{123}{124}{134}{234}}
                  {{12}{14}{23}{34}}
                  {{13}{14}{23}{24}}

Row sums are A322705. Second column is A001205. Third column is A110101.

Cf. A005176, A058891, A059441, A295193, A306021, A319056, A319189, A319190, A319612, A321721, A322704.

Table[Table[SeriesCoefficient[Product[1+Times@@x/@s,{s,Subsets[Range[n],{k}]}],Sequence@@Table[{x[i],0,k},{i,n}]],{k,1,n}],{n,1,6}]

cp's OEIS Frontend

A110041 a(n) = number of labeled graphs on n vertices (with no isolated vertices, multi-edges or loops) such that the degree of every vertex is at most 3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A144163 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: T(n,k) = number of simple graphs on n labeled nodes with k edges where each maximally connected subgraph is either a tree or a cycle.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A338978 Number of labeled 5-regular graphs on 2n nodes.

Views

Author

Keywords

Links

Crossrefs

A369931 Triangle read by rows: T(n,k) is the number of labeled simple graphs with n edges and k vertices and without endpoints or isolated vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A370059 Number of traceless symmetric binary matrices with 2n 1's and all row sums >= 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A201013 Triangular array read by rows: T(n,k) is the number of 2-regular labeled graphs on n nodes that have exactly k connected components (cycles); n>=3, 1<=k<=floor(n/3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A202065 The number of simple labeled graphs on 2n nodes whose connected components are even length cycles.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A202081 The number of simple labeled graphs on n nodes whose connected components are cycles, stars, wheels, or paths.

Views

Author

Keywords

Comments

References

Links

Crossrefs