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