|
|
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.
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,14
|
|
LINKS
|
|
|
FORMULA
|
T(n,0) = 1, T(n,k) = 0 if k<0 or n<k, else T(n,k) = C(n-1,2)*n^(n-3) if k=n, else T(n,k) = T(n-1,k) + Sum_{j=2..k-1} C(n-1,j) T(j+1,j+1) T(n-1-j,k-j-1).
|
|
EXAMPLE
|
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;
|
|
MAPLE
|
T:= proc(n, k) option remember; if k=0 then 1 elif k<0 or n<k then 0 elif k=n then binomial(n-1, 2) *n^(n-3) else T(n-1, k) +add(binomial(n-1, j) * T(j+1, j+1) *T(n-1-j, k-j-1), j=2..k-1) fi end: seq(seq(T(n, k), k=0..n), n=0..11);
|
|
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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|