A144161 Triangle read by rows: T(n,k) = number of simple graphs on n labeled nodes with k edges that are node-disjoint unions of undirected cycle subgraphs.
1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 4, 3, 1, 0, 0, 10, 15, 12, 1, 0, 0, 20, 45, 72, 70, 1, 0, 0, 35, 105, 252, 490, 465, 1, 0, 0, 56, 210, 672, 1960, 3720, 3507, 1, 0, 0, 84, 378, 1512, 5880, 16740, 31563, 30016, 1, 0, 0, 120, 630, 3024, 14700, 55800, 157815, 300160, 286884
Offset: 0
Examples
T(4,3) = 4, because there are 4 simple graphs with 3 edges that are node-disjoint unions of undirected cycle subgraphs: .1.2. .1.2. .1-2. .1-2. ../|. .|\.. ..\|. .|/.. .3-4. .3-4. .3.4. .3.4. T(6,6) = C(6,3)/2+5!/2 = 70. Triangle begins: 1; 1, 0; 1, 0, 0; 1, 0, 0, 1; 1, 0, 0, 4, 3; 1, 0, 0, 10, 15, 12; 1, 0, 0, 20, 45, 72, 70; ...
Links
- Alois P. Heinz, Rows n = 0..140, flattened
Crossrefs
Programs
-
Maple
T:= proc(n,k) option remember; local i,j; if k=0 then 1 elif k<0 or n
-
Mathematica
T[n_, k_] := T[n, k] = Module[{i, j}, If[k == 0, 1, If[k < 0 || n < k, 0, T[n - 1, k] + Sum[Product[n - i, {i, 1, j}]*T[n - 1 - j, k - j - 1], {j, 2, k}]/2 ]]]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Dec 27 2013, translated from Maple *) -
Python
from sympy.core.cache import cacheit from operator import mul from functools import reduce @cacheit def T(n, k): return 1 if k==0 else 0 if k<0 or n
Indranil Ghosh, Aug 07 2017
Formula
T(n,0) = 1, T(n,k) = 0 if k<0 or n
A110039 Number of 3-regular labeled graphs on 2n vertices with no multiple edges, but loops are allowed. (3-regular = trivalent and a loop incident on a vertex counts as two edges.)
1, 1, 8, 730, 188790, 102737670, 102172297920, 167870491048260, 423971126389110300, 1559445481095305703900, 8010574937878696134151200, 55572909620219147733302926200, 506607333530572584517841616582600, 5931728848766374810152582924943605000
Offset: 0
Keywords
Examples
a(1)=1: {(1,1), (1,2), (2,2)}
References
- 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)
Programs
-
Mathematica
max = 30; f[x_] := Sum[a[n]*(x^n/n!), {n, 0, max}]; a[0] = 1; a[1] = 1; coef = CoefficientList[ 9*x^3*(x^4 - 2)*f''[x] + 3*(x^10 - 2*x^8 - 5*x^6 - 18*x^2 + 8)*f'[x] - x*(x^4 - 4*x^2 + 2)*(x^6 - 2*x^2 + 12)*f[x], x]; Table[a[n], {n, 0, max, 2}]/. Solve[Thread[coef[[2 ;; max]] == 0]][[1]] (* Vaclav Kotesovec, Sep 15 2014 *)
Formula
Differential equation satisfied by the e.g.f. F(t) = sum_n a(n)/2n! t^n: {F(0) = 1, (-t^5+4*t^4+52*t-20*t^2-24)*F(t) + (-144*t+48-12*t^3-12*t^4+6*t^5)*(d/dt)F(t) + (36*t^4-72*t^2)*(d^2/dt^2)F(t)}.
Recurrence: {(123200*n^9 + 30135960*n + 8448*n^10 + 256*n^11 + 105258076*n^3 + 4989600 + 53358140*n^5 + 75458988*n^2 + 91991460*n^4 + 21100464*n^6 + 5718768*n^7 + 1045440*n^8)*a(n) + (-24948000 - 12736*n^9 - 90804600*n - 384*n^10 - 134879084*n^3 - 32082204*n^5 - 145393020*n^2 - 80308236*n^4 - 8713656*n^6 - 1589856*n^7 - 186624*n^8)*a(n + 1) + (11840760*n + 6932520*n^3 + 4989600 + 544320*n^5 + 12084468*n^2 + 2446668*n^4 + 74592*n^6 + 5760*n^7 + 192*n^8)*a(n + 2) + (-1108800 - 2428000*n - 1014166*n^3 - 44740*n^5 - 2148828*n^2 - 278430*n^4 - 3912*n^6 - 144*n^7)*a(n + 3) + (-6435 - 3887*n - 780*n^2 - 52*n^3)*a(n + 4) + (3003 + 1635*n + 297*n^2 + 18*n^3)*a(n + 5) - 3*a(n + 6)}.
Goulden and Jackson give a differential equation satisfied by the e.g.f, which presumably agrees with the above. - N. J. A. Sloane, Sep 02 2013
Recurrence (for n > 5): 3*(9*n^2 - 27*n + 16)*a(n) = 3*(2*n - 1)*(27*n^4 - 108*n^3 + 138*n^2 - 63*n + 4)*a(n-1) - (n-1)*(2*n - 3)*(2*n - 1)*(3*n - 4)*(18*n^2 - 27*n - 13)*a(n-2) + 2*(n-2)*(n-1)*(2*n - 5)*(2*n - 3)*(2*n - 1)*(27*n^3 - 90*n^2 + 57*n + 8)*a(n-3) - 2*(n-3)*(n-2)*(n-1)*(2*n - 7)*(2*n - 5)*(2*n - 3)*(2*n - 1)*(9*n^2 - 9*n - 2)*a(n-4). - Vaclav Kotesovec, Sep 15 2014
a(n) ~ sqrt(2) * 6^n * n^(3*n) / exp(3*n). - Vaclav Kotesovec, Sep 15 2014
Extensions
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.
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
Comments
A loop adds 2 to the degree of its vertex.
Examples
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; ...
Crossrefs
Formula
T(n,k) = T(n, n+1-k).
Comments