A144207 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 3.
1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 4, 12, 1, 0, 0, 10, 60, 150, 1, 0, 0, 20, 180, 900, 2160, 1, 0, 0, 35, 420, 3150, 15180, 36015, 1, 0, 0, 56, 840, 8400, 60750, 291060, 688128, 1, 0, 0, 84, 1512, 18900, 182270, 1311240, 6300672, 14880348, 1, 0, 0, 120, 2520, 37800
Offset: 0
Examples
T(5,4) = 60 = 5*12, because there are 5 possibilities for a single node and T(4,4) = 12: .1-2. .1-2. .1-2. .1.2. .1.2. .1-2. .1.2. .1.2. .1-2. .1-2. .1-2. .1-2. .|X.. .|/|. .|/.. ..X|. .|/|. ../|. .|X.. .|\|. .|\.. ..X|. .|\|. ..\|. .3.4. .3.4. .3-4. .3-4. .3-4. .3-4. .3-4. .3-4. .3-4. .3.4. .3.4. .3-4. Triangle begins: 1; 1, 0; 1, 0, 0; 1, 0, 0, 1; 1, 0, 0, 4, 12; 1, 0, 0, 10, 60, 150;
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, Binomial[n-1, 2]*n^(n-3), True, t[n-1, k] + Sum[Binomial[n-1, j]*t[j+1, j+1]*t[n-1-j, k-j-1], {j, 2, k-1}]]; Table[Table[t[n, k], {k, 0, n}], {n, 0, 11}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from Maple *)
Formula
T(n,0) = 1, T(n,k) = 0 if k<0 or n