A144209 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 consists of a single node or has a unique cycle of length 4.
1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 3, 1, 0, 0, 0, 15, 60, 1, 0, 0, 0, 45, 360, 1080, 1, 0, 0, 0, 105, 1260, 7560, 20580, 1, 0, 0, 0, 210, 3360, 30240, 164640, 430080, 1, 0, 0, 0, 378, 7560, 90720, 740880, 3873240, 9920232, 1, 0, 0, 0, 630, 15120, 226800, 2469600, 19367460, 99406440, 252000000
Offset: 0
Examples
T(5,4) = 15 = 5*3, because there are 5 possibilities for a single node and T(4,4) = 3: .1-2. .1-2. .1.2. .|.|. ..X.. .|X|. .3-4. .3-4. .3.4. Triangle begins: 1; 1, 0; 1, 0, 0; 1, 0, 0, 0; 1, 0, 0, 0, 3; 1, 0, 0, 0, 15, 60;
Links
- Alois P. Heinz, Rows n = 0..140, flattened
Crossrefs
Programs
-
Maple
T:= proc(n,k) option remember; if k=0 then 1 elif k<0 or n
-
Mathematica
T[n_, k_] := T[n, k] = Which[k == 0, 1, k < 0 || n < k, 0, k == n, 3*Binomial[n-1, 3]*n^(n-4), True, T[n-1, k] + Sum[Binomial[n-1, j]*T[j+1, j+1]*T[n-1-j, k-j-1], {j, 3, k-1}]]; Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Aug 29 2014, translated from Maple *)
Formula
T(n,0) = 1, T(n,k) = 0 if k<0 or n
A144212 Triangle T(n,k), n>=3, 3<=k<=n, read by rows: T(n,k) = number of simple graphs on n labeled nodes, where each maximally connected subgraph consists of a single node or has a unique cycle of length k.
2, 17, 4, 221, 76, 13, 3261, 1486, 433, 61, 54801, 29506, 11593, 2941, 361, 1049235, 628531, 296353, 102481, 23041, 2521, 22695027, 14633011, 7795873, 3270961, 1010881, 204121, 20161, 548904831, 373486051, 217126225, 104038201, 39355201
Offset: 3
Examples
T(4,4) = 4, because there are 4 simple graphs on 4 labeled nodes, where each maximally connected subgraph consists of a single node or has a unique cycle of length 4:
.1.2. .1-2. .1-2. .1.2.
..... .|.|. ..X.. .|X|.
.3.4. .3-4. .3-4. .3.4.
Triangle begins:
2;
17, 4;
221, 76, 13;
3261, 1486, 433, 61;
54801, 29506, 11593, 2941, 361;
Links
- Alois P. Heinz, Rows n = 3..102, flattened
Crossrefs
Programs
-
Maple
B:= proc(n,c,k) option remember; if c=0 then 1 elif c<0 or n
add(B(n,c,k), c=0..n): seq(seq(T(n,k), k=3..n), n=3..11); -
Mathematica
B[n_, c_, k_] := B[n, c, k] = Which[c == 0, 1, c<0 || n
Formula
See program.