1,2

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

E. A. Bender and E. R. Canfield, The asymptotic number of labeled graphs with given degree sequences, Journal of Combinatorial Theory, Series A, 24 (1978), 296-307.

Andrew Howroyd, PARI Program

Atabey Kaygun, Enumerating Labeled Graphs that Realize a Fixed Degree Sequence, arXiv:2101.02299 [math.CO], 2021.

B. D. McKay, Applications of a technique for labelled enumeration, Congress. Numerantium, 40 (1983), 207-221.

Wikipedia, Regular graph

From Gus Wiseman, Dec 19 2018: (Start)

A graph is regular if all vertices have the same degree. For example, the a(4) = 8 simple regular graphs are:

1 2

3 4

.

4---1 3---1 2---1

3---2 4---2 4---3

.

3---4 4---3 4---2

| | | | | |

1---2 1---2 1---3

.

4---3

| X |

2---1

(End)

Table[Sum[SeriesCoefficient[Product[1+Times@@x/@s, {s, Subsets[Range[n], {2}]}], Sequence@@Table[{x[i], 0, k}, {i, n}]], {k, 0, n-1}], {n, 1, 9}] (* Gus Wiseman, Dec 19 2018 *)

(PARI) \\ See link for program file.

for(n=1, 10, print1(A295193(n), ", ")) \\ Andrew Howroyd, Aug 28 2019

Row sums of A059441.

Cf. A005176 (unlabeled equivalent), A058891, A116539, A299353, A306017, A306021, A319189, A319190, A319612, A319729.

Álvar Ibeas, Nov 16 2017

a(16)-a(18) from Andrew Howroyd, Aug 28 2019

approved

0,4

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 411.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 279.

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.

R. W. Robinson, Computer print-out, no date. Gives first 30 terms.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..160 (first 31 terms from R. W. Robinson)

F. Chyzak, M. Misnha and B. Salvy, Effective D-Finite Symmetric Functions, FPSAC '02 (2002) # 19.12, see Maple output prior to the References.

Élie de Panafieu, Asymptotic expansion of regular and connected regular graphs, arXiv:2408.12459 [math.CO], 2024. See p. 9.

Oleg Evnin and Weerawit Horinouchi, A Gaussian integral that counts regular graphs, arXiv:2403.04242 [cond-mat.stat-mech], 2024. See p. 12.

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

I. P. Goulden, D. M. Jackson, and J. W. Reilly, The Hammond series of a symmetric function and its application to P-recursiveness, SIAM J. Algebraic Discrete Methods 4 (1983), no. 2, 179-193.

Atabey Kaygun, Enumerating Labeled Graphs that Realize a Fixed Degree Sequence, arXiv:2101.02299 [math.CO], 2021.

Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.

R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)

R. W. Robinson, Cubic labeled graphs, computer print-out, n.d.

N. C. Wormald, Enumeration of labelled graphs II: cubic graphs with a given connectivity, J. Lond Math Soc s2-20 (1979) 1-7, eq. (2.6).

From Vladeta Jovovic, Mar 25 2001: (Start)

E.g.f. f(x) = Sum_{n >= 0} a(2 * n) * x^n/(2 * n)! satisfies differential equation 6 * x^2 * (-x^2 - 2 * x + 2) * (d^2/dx^2)f(x) - (x^5 + 6 * x^4 + 6 * x^3 - 32 * x + 8) * (d/dx)f(x) + (x/6) * (-x^2 - 2 * x + 2)^2 * f(x) = 0.

Recurrence: a(2 * n) = (2 * n)!/n! * v(n) where 48 * v(n) + (-72 * n^2 + 24 * n + 48) * v(n - 1) + (72 * n^3 - 432 * n^2 + 788 * n - 428) * v(n - 2) + (36 * n^4 - 324 * n^3 + 1052 * n^2 - 1428 * n + 664) * v(n - 3) + (36 * n^4 - 360 * n^3 + 1260 * n^2 - 1800 * n + 864) * v(n - 4) + (6 * n^5 - 94 * n^4 + 550 * n^3 - 1490 * n^2 + 1844 * n - 816) * v(n - 5) + (-n^5 + 15 * n^4 - 85 * n^3 + 225 * n^2 - 274 * n + 120) * v(n - 6) = 0. (End)

a(n) = Sum_{i=0..2n} Sum_{k=0..min(floor((3n-i)/3), floor((2n-i)/2))} Sum_{j=0..min(floor(3n-i-3k)/2), floor((2n-i-2k)/2))} ((-1)^(i+j)*(2n)!(2*(3n-i-2j-3k))!)/(2^(5n-i-2j-4k)*3^(2n-i-2j-k)*(3n-i-2j-3k)!i!j!k!(2n-i-2j-2k)!). - Shanzhen Gao, Jun 05 2009

E.g.f.: hypergeom([1/6, 5/6],[],12*x/(x^2+8*x+4)^(3/2))*exp(-log(1/4*x^2+2*x+1)/4 - x/3 + (x^2+8*x+4)^(3/2)/(24*x) - 1/(3*x) - x^2/24 - 1). Multiply x^i by (2*i)! to get the generating function. - Mark van Hoeij, Nov 07 2011

D-finite with recurrence: 3*(3*n-7)*(3*n-4)*a(n) = 9*(n-1)*(2*n-1)*(3*n-7)*(3*n^2 - 4*n + 2)*a(n-1) + (n-1)*(2*n-3)*(2*n-1)*(108*n^3 - 441*n^2 + 501*n - 104)*a(n-2) + 2*(n-2)*(n-1)*(2*n-5)*(2*n-3)*(2*n-1)*(3*n-1)*(9*n^2 - 42*n + 43)*a(n-3) - 2*(n-3)*(n-2)*(n-1)*(2*n-7)*(2*n-5)*(2*n-3)*(2*n-1)*(3*n-4)*(3*n-1)*a(n-4). - Vaclav Kotesovec, Mar 11 2014

a(n) ~ sqrt(2) * 6^n * n^(3*n) / exp(3*n+2). - Vaclav Kotesovec, Mar 11 2014

From R. J. Mathar, Oct 31 2010: (Start)

A002829aux := proc(i) local a, j, k ; a := 0 ; for j from 0 to i do for k from 0 to 2*(i-j) do a := a+(-1)^(j+k)/j!*doublefactorial(2*i+2*k-1)/3^k/k!/(2*i-2*j-k)! ; end do: end do: a*3^i/2^i ; end proc:

A002829 := proc(n) (2*n)!/6^n*add( A002829aux(i)/(n-i)!, i=0..n) ; end proc: seq(A002829(n), n=0..6) ; (End)

egf := hypergeom([1/6, 5/6], [], 12*x/(x^2+8*x+4)^(3/2)) * exp(-ln(1/4*x^2+2*x+1)/4 - x/3 + (x^2+8*x+4)^(3/2)/(24*x) - 1/(3*x) - x^2/24 - 1):

ser := convert(series(egf, x=0, 30), polynom):

seq(coeff(ser, x, i) * (2*i)!, i=0..degree(ser)); # Mark van Hoeij, Nov 07 2011

Flatten[{1, RecurrenceTable[{2 (-3+n) (-2+n) (-1+n) (-7+2 n) (-5+2 n) (-3+2 n) (-1+2 n) (-4+3 n) (-1+3 n) a[-4+n]-2 (-2+n) (-1+n) (-5+2 n) (-3+2 n) (-1+2 n) (-1+3 n) (43-42 n+9 n^2) a[-3+n]-(-1+n) (-3+2 n) (-1+2 n) (-104+501 n-441 n^2+108 n^3) a[-2+n]-9 (-1+n) (-1+2 n) (-7+3 n) (2-4 n+3 n^2) a[-1+n]+3 (-7+3 n) (-4+3 n) a[n]==0, a[1]==0, a[2]==1, a[3]==70, a[4]==19355}, a, {n, 1, 15}]}] (* Vaclav Kotesovec, Mar 11 2014 *)

terms = 14;

egf = HypergeometricPFQ[{1/6, 5/6}, {}, 12x/(x^2 + 8x + 4)^(3/2)] Exp[-Log[ 1/4 x^2 + 2x + 1]/4 - x/3 + (x^2 + 8x + 4)^(3/2)/(24x) - 1/(3x) - x^2/24 - 1] + O[x]^terms;

CoefficientList[egf, x] (2 Range[0, terms-1])! (* Jean-François Alcover, Nov 23 2018, after Mark van Hoeij *)

(PARI) a(n) = sum(i=0, 2*n, sum(k=0, min(floor((3*n-i)/3), floor((2*n-i)/2)), sum(j=0, min(floor((3*n-i-3*k)/2), floor((2*n-i-2*k)/2)), ((-1)^(i+j)*(2*n)!*(2*(3*n-i-2*j-3*k))!)/(2^(5*n-i-2*j-4*k)*3^(2*n-i-2*j-k)*(3*n-i-2*j-3*k)!*i!*j!*k!*(2*n-i-2*j-2*k)!)))); \\ Michel Marcus, Jan 18 2018

A diagonal of A059441. Cf. A005814.

See A004109 for connected graphs of this type.

More terms from Vladeta Jovovic, Mar 25 2001

approved

0,5

a(n) is the number of ways of covering K_n with cycles of length >= 3. Also number of 'frames' on n lines: given n lines in general position (none parallel and no three concurrent), a frame is a subset of n of the e C(n,2) points of intersection such that no three points are on the same line. - Mitch Harris, Jul 06 2006

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 410-411.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 276 and 279.

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.7.

Ph. Flajolet, Singular combinatorics, pp. 561-571, Proc. Internat. Congr. Math., Beijing 2002, Higher Education Press, Beijing, 2002, Vol III.

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, ex. 3.3.6b, 3.3.34.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.8. Also problems 5.23 and 5.15(a), case k=3.

Z. Tan and S. Gao, Enumeration of (0,1)-Symmetric Matrices, submitted [From Shanzhen Gao, Jun 05 2009] [apparently unpublished as of 2016]

H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 77, Eq. 3.9.1.

W. A. Whitworth, Choice and Chance, Bell, 1901, p. 269, ex. 160.

T. D. Noe, Table of n, a(n) for n=0..100

Editorial note, Robinson's constant, Amer. Math. Monthly, 59 (1952), 296-297.

Ph. Flajolet, Singular combinatorics, arXiv:math/0304465 [math.CO], 2003.

Ph. Flajolet and A. Odlyzko, Singularity analysis of generating functions, [Research Report] RR-0826, INRIA. 1988.

Atabey Kaygun, Enumerating Labeled Graphs that Realize a Fixed Degree Sequence, arXiv:2101.02299 [math.CO], 2021.

Rui-Li Liu and Feng-Zhen Zhao, New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.

H. Richter, Analyzing coevolutionary games with dynamic fitness landscapes, arXiv preprint arXiv:1603.06374 [q-bio.PE], 2016.

R. Robinson, A new absolute geometric constant?, Amer. Math. Monthly, 58 (1951), 462-469.

Weiping Wang, Tianming Wang, An automatic approach to the generating functions for some special sequences, Ars. Comb. 116 (2018) 263, Example 4.2

H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 86, Eq. 3.9.1.

a(n) ~ n!*exp(-3/4)/sqrt(Pi*n).

E.g.f.: exp(-x/2-x^2/4)/sqrt(1-x).

D-finite with recurrence a(n+1) = n*(a(n)+a(n-2)*(n-1)/2).

1/4^n * Sum_{b=0..floor(n/2)} Sum_{g=0..n-2*b} (-1)^(b+g) * 2^(2b+g) * n! * (2n-4b-2g)! / (b! * g! * (n-2b-g)!^2). - Shanzhen Gao, Jun 05 2009

a(n) = (-1)^n*n!*Sum_{k=0..n}(3/4)^k*binomial(-1/2, n - k)*hypergeom([1/2, -k], [1/2 - n + k], 1/3)/ k!. - Peter Luschny, Aug 26 2017

a := n -> (-1)^n*n!*add((3/4)^k*binomial(-1/2, n-k)*hypergeom([1/2, -k], [1/2-n+k], 1/3)/ k!, k=0..n): seq(simplify(a(n)), n=0..21); # Peter Luschny, Aug 26 2017

m = 21; CoefficientList[ Series[ Exp[-x/2 - x^2/4] / Sqrt[1-x], {x, 0, m}], x]*Table[n!, {n, 0, m}] (* Jean-François Alcover, Jun 21 2011, after e.g.f. *)

(PARI) a(n)=if(n<0, 0, n!*polcoeff(exp(-x/2-x^2/4+x*O(x^n))/sqrt(1-x+x*O(x^n)), n))

(Maxima)

a(n):=sum(sum(binomial(k, i)*binomial(i-1/2, n-k)*(3^(k-i)*n!)/(4^k*k!)*(-1)^(n-i), i, 0, k), k, 0, n);

makelist(a(n), n, 0, 12); /* Emanuele Munarini, Aug 25 2017 */

Cf. A000985, A000986, A002137. A diagonal of A059441 and A144163.

nonn,easy,nice

approved

1,18

A graph in which every node has r edges is called an r-regular graph. The triangle is symmetric because if an n-node graph is r-regular, than its complement is (n - 1 - r)-regular and two graphs are isomorphic if and only if their complements are isomorphic.

Terms may be computed without generating each graph by enumerating the number of graphs by degree sequence. A PARI program showing this technique for graphs with labeled vertices is given in A295193. Burnside's lemma can be used to extend this method to the unlabeled case. - Andrew Howroyd, Mar 08 2020

Andrew Howroyd, Table of n, a(n) for n = 1..300 (rows 1..24, first 16 rows from Jason Kimberley)

Jason Kimberley, Not necessarily connected connected regular graphs (with girth at least 3)

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

Markus Meringer, Fast generation of regular graphs and construction of cages, J. Graph Theory 30 (2) (1999) 137-146. [Jason Kimberley, Nov 24 2009]

Markus Meringer, Fast Generation of Regular Graphs and Construction of Cages, Univ. Bayreuth, 1999

Markus Meringer, Tables of Regular Graphs

Eric Weisstein's World of Mathematics, Regular Graph.

T(n,r) = A068934(n,r) + A068933(n,r).

T(8,3) = 6. Edge-lists for the 6 3-regular 8-node graphs:

Graph 1: 12, 13, 14, 23, 24, 34, 56, 57, 58, 67, 68, 78

Graph 2: 12, 13, 14, 24, 34, 26, 37, 56, 57, 58, 68, 78

Graph 3: 12, 13, 23, 14, 47, 25, 58, 36, 45, 67, 68, 78

Graph 4: 12, 13, 23, 14, 25, 36, 47, 48, 57, 58, 67, 68

Graph 5: 12, 13, 24, 34, 15, 26, 37, 48, 56, 57, 68, 78

Graph 6: 12, 23, 34, 45, 56, 67, 78, 18, 15, 26, 37, 48.

Triangle starts

1;

1, 1;

1, 0, 1;

1, 1, 1, 1;

1, 0, 1, 0, 1;

1, 1, 2, 2, 1, 1;

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

1, 1, 3, 6, 6, 3, 1, 1;

1, 0, 4, 0, 16, 0, 4, 0, 1;

1, 1, 5, 21, 60, 60, 21, 5, 1, 1;

1, 0, 6, 0, 266, 0, 266, 0, 6, 0, 1;

1, 1, 9, 94, 1547, 7849, 7849, 1547, 94, 9, 1, 1;

...

Row sums give A005176.

Regular graphs of degree k: A008483 (k=2), A005638 (k=3), A033301 (k=4), A165626 (k=5), A165627 (k=6), A165628 (k=7), A180260 (k=8).

Cf. A059441, A295193.

nonn,tabl

More terms and comments from David Wasserman, Feb 22 2002

More terms from Eric W. Weisstein, Oct 19, 2002

Description corrected (changed 'orders' to 'degrees') by Jason Kimberley, Sep 06 2009

Extended to the sixteenth row (in the b-file) by Jason Kimberley, Sep 24 2009

approved

0,5

T(n,k) is the number of k-regular symmetric relations on n labeled nodes.

T(n,k) is the number of k-regular graphs with half-edges on n labeled vertices.

Terms may be computed without generating all graphs by enumerating the number of graphs by degree sequence. A PARI program showing this technique is given below. Burnside's lemma as applied in A122082 and A000666 can be used to extend this method to the case of unlabeled vertices A333159 and A333161 respectively.

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

T(n,k) = T(n,n-k).

Triangle begins:

1,

1, 1;

1, 2, 1;

1, 4, 4, 1;

1, 10, 18, 10, 1;

1, 26, 112, 112, 26, 1;

1, 76, 820, 1760, 820, 76, 1;

1, 232, 6912, 35150, 35150, 6912, 232, 1;

1, 764, 66178, 848932, 1944530, 848932, 66178, 764, 1;

...

(PARI) \\ See script in A295193 for comments.

GraphsByDegreeSeq(n, limit, ok)={

local(M=Map(Mat([x^0, 1])));

my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));

my(recurse(r, p, i, q, v, e) = if(e<=limit && poldegree(q)<=limit, if(i<0, if(ok(x^e+q, r), acc(x^e+q, v)), my(t=polcoeff(p, i)); for(k=0, t, self()(r, p, i-1, (t-k+x*k)*x^i+q, binomial(t, k)*v, e+k)))));

for(k=2, n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], my(p=src[i, 1]); recurse(n-k, p, poldegree(p), 0, src[i, 2], 0))); Mat(M);

}

Row(n)={my(M=GraphsByDegreeSeq(n, n\2, (p, r)->poldegree(p)-valuation(p, x) <= r + 1), v=vector(n+1)); for(i=1, matsize(M)[1], my(p=M[i, 1], d=poldegree(p)); v[1+d]+=M[i, 2]; if(pollead(p)==n, v[2+d]+=M[i, 2])); for(i=1, #v\2, v[#v+1-i]=v[i]); v}

for(n=0, 8, print(Row(n))) \\ Andrew Howroyd, Mar 14 2020

Columns k=0..8 are A000012, A000085, A000986, A110040, A139670, A139671, A139673, A139674, A139675.

Row sums are A322698.

Central coefficients are A333164.

Cf. A188448 (transposed as array).

Cf. A059441, A295193, A333158, A333159, A333161.

nonn,tabl

Andrew Howroyd, Mar 09 2020

approved

0,7

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 411.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 279.

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vaclav Kotesovec, Table of n, a(n) for n = 0..260 (first 100 terms from Vincenzo Librandi)

Élie de Panafieu, Asymptotic expansion of regular and connected regular graphs, arXiv:2408.12459 [math.CO], 2024. See p. 9.

I. P. Goulden, D. M. Jackson, and J. W. Reilly, The Hammond series of a symmetric function and its application to P-recursiveness, SIAM J. Algebraic Discrete Methods 4 (1983), no. 2, 179-193.

Atabey Kaygun, Enumerating Labeled Graphs that Realize a Fixed Degree Sequence, arXiv:2101.02299 [math.CO], 2021.

Vaclav Kotesovec, Recurrence (of order 10)

R. C. Read and N. C. Wormald, Number of labeled 4-regular graphs, J. Graph Theory, 4 (1980), 203-212.

From Vladeta Jovovic, Mar 26 2001: (Start)

E.g.f. f(x) = Sum_{n >= 0} a(n)*x^n/(n)! satisfies the differential equation 16*x^2*(x - 1)^2*(x + 2)^2*(x^5 + 2*x^4 + 2*x^2 + 8*x - 4)*(d^2/dx^2)y(x) - 4*(x^13 + 4*x^12 - 16*x^10 - 10*x^9 - 36*x^8 - 220*x^7 - 348*x^6 - 48*x^5 + 200*x^4 - 336*x^3 - 240*x^2 + 416*x - 96)*(d/dx)y(x) - x^4*(x^5 + 2*x^4 + 2*x^2 + 8*x - 4)^2*y(x) = 0.

Recurrence: a(n) = - 1/384*(( - 256*n^2 - 896*n + 1152)*a(n - 1) + (768*n^3 - 3648*n^2 + 5568*n - 2688)*a(n - 2) + ( - 192*n^4 + 3264*n^3 - 14784*n^2 + 24384*n - 12672)*a(n - 3) + (224*n^6 - 4512*n^5 + 36304*n^4 - 148160*n^3 + 320016*n^2 - 341728*n + 137856)*a(n - 5) + ( - 640*n^5 + 8800*n^4 - 46400*n^3 + 116000*n^2 - 135360*n + 57600)*a(n - 4) + ( - 24*n^10 + 1320*n^9 - 31680*n^8 + 435600*n^7 - 3786552*n^6 + 21649320*n^5 - 82006320*n^4 + 201828000*n^3 - 306085824*n^2 + 255087360*n - 87091200)*a(n - 11) + (64*n^10 - 3480*n^9 + 82692*n^8 - 1127232*n^7 + 9726024*n^6 - 55255032*n^5 + 208179908*n^4 - 510068208*n^3 + 770738352*n^2 - 640484928*n + 218211840)*a(n - 9) + (16*n^11 - 992*n^10 + 27256*n^9 - 437160*n^8 + 4536288*n^7 - 31876656*n^6 + 154182488*n^5 - 510784360*n^4 + 1128552896*n^3 - 1570313952*n^2 + 1223830656*n - 397716480)*a(n - 10) + ( - 128*n^8 + 5488*n^7 - 94576*n^6 + 864976*n^5 - 4606672*n^4 + 14604352*n^3 - 26753984*n^2 + 25611264*n - 9630720)*a(n - 7) + (16*n^9 - 576*n^8 + 8704*n^7 - 71680*n^6 + 348880*n^5 - 1013824*n^4 + 1673376*n^3 - 1333120*n^2 + 226944*n + 161280)*a(n - 8) + (128*n^7 - 2192*n^6 + 12048*n^5 - 8240*n^4 - 151248*n^3 + 565312*n^2 - 765248*n + 349440)*a(n - 6) + ( - 4*n^13 + 364*n^12 - 14924*n^11 + 364364*n^10 - 5897892*n^9 + 66678612*n^8 - 540145892*n^7 + 3163772612*n^6 - 13344475144*n^5 + 39830815024*n^4 - 81255012384*n^3 + 106386868224*n^2 - 79211036160*n + 24908083200)*a(n - 14) + ( - 4*n^13 + 360*n^12 - 14612*n^11 + 353496*n^10 - 5674812*n^9 + 63680760*n^8 - 512439356*n^7 + 2983811688*n^6 - 12520194544*n^5 + 37201987680*n^4 - 75598952832*n^3 + 98660630016*n^2 - 73265264640*n + 22992076800)*a(n - 13) + ( - 16*n^12 + 1244*n^11 - 43208*n^10 + 884620*n^9 - 11860728*n^8 + 109396452*n^7 - 709293464*n^6 + 3243764260*n^5 - 10331326456*n^4 + 22203205904*n^3 - 30301280928*n^2 + 23300910720*n - 7504358400)*a(n - 12) + ( - n^14 + 105*n^13 - 5005*n^12 + 143325*n^11 - 2749747*n^10 + 37312275*n^9 - 368411615*n^8 + 2681453775*n^7 - 14409322928*n^6 + 56663366760*n^5 - 159721605680*n^4 + 310989260400*n^3 - 392156797824*n^2 + 283465647360*n - 87178291200)*a(n - 15)). (End)

a(n) = Sum_{d=0..floor(n/2), c=0..floor(n/2-d), b=0..(n-2c-2d), f=0..(n-2c-2d-b), k=0..min(n-b-2c-2d-f, 2n-2f-2b-3c-4d), j=0..floor(k/2+f)} ((-1)^(k+2f-j+d)*n!*(k+2f)!(2(2n-k-2f-2b-3c-4d))!) / (2^(5n-2k-2f-3b-8c-7d) * 3^(n-b-c-2d-k-f)*(2n-k-2f-2b-3c-4d)!*(k+2f-2j)!*j!*b!*c!*d!*k!*f!*(n-b-2c-2d-k-f)!). - Shanzhen Gao, Jun 05 2009

E.g.f.: (1+x-(1/3)*x^2-(1/6)*x^3)^(-1/2)*hypergeom([1/4, 3/4],[],-12*x*(x+2)*(x-1)/(x^3+2*x^2-6*x-6)^2)*exp(-x*(x^2-6)/(8*x+16)). - Mark van Hoeij, Nov 07 2011

a(n) ~ n^(2*n) * 2^(n+1/2) / (3^n * exp(2*n+15/4)). - Vaclav Kotesovec, Mar 11 2014

egf := (1+x-(1/3)*x^2-(1/6)*x^3)^(-1/2)*hypergeom([1/4, 3/4], [], -12*x*(x+2)*(x-1)/(x^3+2*x^2-6*x-6)^2)*exp(-x*(x^2-6)/(8*x+16));

ser := convert(series(egf, x=0, 40), polynom):

seq(coeff(ser, x, i)*i!, i=0..degree(ser)); # Mark van Hoeij, Nov 07 2011

max = 17; f[x_] := HypergeometricPFQ[{1/4, 3/4}, {}, -12*x*(x + 2)*(x - 1)/(x^3 + 2*x^2 - 6*x - 6)^2]*Exp[-x*(x^2 - 6)/(8*x + 16)]/(1 + x - x^2/3 - x^3/6)^ (1/2); CoefficientList[Series[f[x], {x, 0, max}], x]*Range[0, max]! (* Jean-François Alcover, Jun 19 2012, from e.g.f. *)

Cf. A005814, A002829, A005816, A272905 (connected). A diagonal of A059441.

nonn,nice,easy

More terms from Vladeta Jovovic, Mar 26 2001

approved

0,20

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

Array begins:

=================================================================

n\k | 0 1 2 3 4 5 6 7

----+------------------------------------------------------------

0 | 1 1 1 1 1 1 1 1 ...

1 | 1 0 0 0 0 0 0 0 ...

2 | 1 1 1 1 1 1 1 1 ...

3 | 1 0 1 0 1 0 1 0 ...

4 | 1 3 6 10 15 21 28 36 ...

5 | 1 0 22 0 158 0 654 0 ...

6 | 1 15 130 760 3355 12043 36935 100135 ...

7 | 1 0 822 0 93708 0 3226107 0 ...

8 | 1 105 6202 190050 3535448 45163496 431400774 3270643750 ...

...

(PARI)

MultigraphsByDegreeSeq(n, limit, ok)={

local(M=Map(Mat([0, 1])));

my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));

my(recurse(r, h, p, q, v, e) = if(!p, if(ok(x^e+q, r), acc(x^e+q, v)), my(i=poldegree(p), t=pollead(p)); self()(r, limit, p-t*x^i, q+t*x^i, v, e); for(m=1, h-i, for(k=1, min(t, (limit-e)\m), self()(r, if(k==t, limit, i+m-1), p-k*x^i, q+k*x^(i+m), binomial(t, k)*v, e+k*m)))));

for(r=1, n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], recurse(n-r, limit, src[i, 1], 0, src[i, 2], 0))); Mat(M);

}

T(n, k)={if((n%2&&k%2)||(n==1&&k>0), 0, vecsum(MultigraphsByDegreeSeq(n, k, (p, r)->subst(deriv(p), x, 1)>=(n-2*r)*k)[, 2]))}

{ for(n=0, 8, for(k=0, 7, print1(T(n, k), ", ")); print) }

Rows n=4..6 are A000217(n+1), A244868 (with interspersed zeros), A244878.

Columns k=0..4 are A000012, A123023, A002137, A108243 (with interspersed zeros), A367497.

Cf. A059441 (graphs), A333157, A333330 (unlabeled nodes), A333467 (with loops).

nonn,tabl

Andrew Howroyd, Mar 15 2020

approved

1,1

A graph is regular if all vertices have the same degree. A loop adds 2 to the degree of its vertex.

Wikipedia, Regular graph

Gus Wiseman, The a(4) = 24 regular graphs with loops.

Gus Wiseman, The a(5) = 78 regular graphs with loops.

Table[Sum[SeriesCoefficient[Product[1+Times@@x/@s, {s, Select[Tuples[Range[n], 2], OrderedQ]}], Sequence@@Table[{x[i], 0, k}, {i, n}]], {k, 0, 2n}], {n, 6}]

(PARI) for(n=1, 10, print1(A322635(n), ", ")) \\ See A295193 for script, Andrew Howroyd, Aug 28 2019

Row sums of A333158.

Cf. A000666, A054921, A059441, A295193, A299353, A306017, A306021, A319189, A319190, A319612, A322659, A322661.

Gus Wiseman, Dec 21 2018

a(11)-a(18) from Andrew Howroyd, Aug 28 2019

approved

1,5

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

T(n,k) = Sum_{i=1..n} binomial(n,i)*A059441(i,k) for k > 0. - Andrew Howroyd, Dec 26 2020

Triangle begins:

1

1 1

1 3 1

1 9 7 1

1 25 37 5 1

1 75 207 85 21 1

1 231 1347 525 591 7 1

1 763 10125 21385 23551 3535 113 1

1 2619 86173 180201 1216701 31647 30997 9 1

Table[If[k==0, 1, Sum[Binomial[n, sup]*SeriesCoefficient[Product[1+Times@@x/@s, {s, Subsets[Range[sup], {2}]}], Sequence@@Table[{x[i], 0, k}, {i, sup}]], {sup, n}]], {n, 8}, {k, 0, n-1}]

Row sums are A322555.

Cf. A000569, A005176, A058891, A059441, A295193, A301481, A306017, A306019, A306021, A319169, A319190, A319612.

nonn,tabl

Gus Wiseman, Dec 17 2018

approved

0,2

A graph is regular if all vertices have the same degree. A half-edge is like a loop except it only adds 1 to the degree of its vertex.

Wikipedia, Regular graph

The a(3) = 10 edge sets:

{}

{{1},{2,3}}

{{3},{1,2}}

{{2},{1,3}}

{{1},{2},{3}}

{{1,2},{1,3},{2,3}}

{{1},{3},{1,2},{2,3}}

{{1},{2},{1,3},{2,3}}

{{2},{3},{1,2},{1,3}}

{{1},{2},{3},{1,2},{1,3},{2,3}}

Table[Sum[SeriesCoefficient[Product[1+Times@@x/@s, {s, Union/@Select[Tuples[Range[n], 2], OrderedQ]}], Sequence@@Table[{x[i], 0, k}, {i, n}]], {k, 0, n-1}], {n, 1, 6}]

(PARI) for(n=1, 10, print1(A322698(n), ", ")) \\ See A295193 for script, Andrew Howroyd, Aug 28 2019

Row sums of A333157.

Cf. A058891, A059441, A116539, A283877, A295193, A319189, A319190, A319612, A319729.

Gus Wiseman, Dec 23 2018

a(10)-a(18) from Andrew Howroyd, Aug 28 2019

approved