A228697 -id:A228697 - cp's OEIS frontend

A228696 Number of labeled graphs on n nodes with degree set {2,4}, with multiple edges and loops allowed.

1, 2, 9, 65, 751, 13044, 320803, 10609256, 453774440, 24375801464, 1607240682376, 127684970262822, 12034618723574314, 1328262275098167080, 169754658940294717086, 24877923644434862091314, 4145248921431765036724198, 779383143209936088442516156, 164246020015613168238167009350

Offset: 0

N. J. A. Sloane, Sep 02 2013

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 0..260
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).

Cf. A228697.

max = 20; f[x_] := Sum[a[n]*(x^n/n!), {n, 0, max}]; a[0] = 1; a[1] = 2; coef = CoefficientList[-16*(x - 2)^2* x^2*(x + 1)^2*(x^5 - 2*x^4 + 2*x^3 - 2*x^2 + 12*x + 4)*f''[x] + 4*(x^13 - 4*x^12 - 6*x^11 + 36*x^10 - 6*x^9 + 24*x^8 - 352*x^7 + 380*x^6 + 152*x^5 + 2104*x^4 - 1472*x^3 - 688*x^2 + 256*x + 96)* f'[x] + (-x^14 + 6*x^13 + 2*x^12 - 76*x^11 + 112*x^10 + 96*x^9 + 356*x^8 - 1320*x^7 - 568*x^6 + 768*x^5 + 9248*x^4 + 12224*x^3 - 2496*x^2 - 3968*x - 768)*f[x], x]; Table[a[n], {n, 0, max}] /. Solve[Thread[coef[[2 ;; max]] == 0]][[1]] (* Vaclav Kotesovec, Sep 15 2014 *)

See Goulden-Jackson for the e.g.f.

Recurrence (for n>11): 96*(2*n^5 - 8*n^4 - 3*n^3 + 22*n^2 + 69*n - 88)*a(n) = 32*(4*n^7 - 26*n^6 + 34*n^5 + 29*n^4 + 121*n^3 - 554*n^2 + 350*n + 6)*a(n-1) + 32*(n-1)*(4*n^7 + 10*n^6 - 90*n^5 - 130*n^4 + 705*n^3 + 587*n^2 - 1286*n + 26)*a(n-2) - 16*(n-2)*(n-1)*(6*n^7 + 2*n^6 - 151*n^5 - 13*n^4 + 687*n^3 + 1225*n^2 - 2200*n - 64)*a(n-3) - 8*(n-3)*(n-2)*(n-1)*(8*n^7 - 34*n^6 + 96*n^5 + 43*n^4 - 480*n^3 + 249*n^2 + 1524*n - 208)*a(n-4) + 8*(n-4)*(n-3)*(n-2)*(n-1)*(4*n^7 - 58*n^6 + 98*n^5 + 417*n^4 - 621*n^3 - 2092*n^2 + 2042*n + 106)*a(n-5) + 8*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(12*n^6 - 52*n^5 - 167*n^4 + 453*n^3 + 850*n^2 - 1894*n + 58)*a(n-6) + 2*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(8*n^6 + 6*n^5 - 12*n^4 - 11*n^3 - 306*n^2 + 1325*n - 160)*a(n-7) - 2*(n-7)*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(4*n^6 - 16*n^5 - 42*n^4 + 112*n^3 + 340*n^2 - 633*n + 38)*a(n-8) - 2*(n-8)*(n-7)*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(4*n^5 + 2*n^4 - 28*n^3 - 14*n^2 + 54*n + 5)*a(n-9) + (n-9)*(n-8)*(n-7)*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(2*n^5 + 2*n^4 - 15*n^3 - 15*n^2 + 82*n - 6)*a(n-10). - Vaclav Kotesovec, Sep 15 2014

More terms from Vaclav Kotesovec, Sep 15 2014

A333158 Irregular triangle read by rows: T(n,k) is the number of k-regular graphs on n labeled nodes with loops allowed, n >= 1, 0 <= k <= n + 1.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 1, 1, 0, 2, 0, 1, 1, 3, 8, 8, 3, 1, 1, 0, 38, 0, 38, 0, 1, 1, 15, 208, 730, 730, 208, 15, 1, 1, 0, 1348, 0, 20670, 0, 1348, 0, 1, 1, 105, 10126, 188790, 781578, 781578, 188790, 10126, 105, 1, 1, 0, 86174, 0, 37885204, 0, 37885204, 0, 86174, 0, 1

Offset: 1

Andrew Howroyd, Mar 09 2020

A loop adds 2 to the degree of its vertex.

			Triangle begins:
  1,   0,     1;
  1,   1,     1,      1;
  1,   0,     2,      0,      1;
  1,   3,     8,      8,      3,      1;
  1,   0,    38,      0,     38,      0,      1;
  1,  15,   208,    730,    730,    208,     15,     1;
  1,   0,  1348,      0,  20670,      0,   1348,     0,   1;
  1, 105, 10126, 188790, 781578, 781578, 188790, 10126, 105, 1;
  ...

Row sums are A322635.
Columns k=0..4 are A000012, A123023, A108246, A110039 (with interspersed zeros), A228697.
Cf. A059441, A333157.

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

cp's OEIS Frontend

A228696 Number of labeled graphs on n nodes with degree set {2,4}, with multiple edges and loops allowed.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions