|
%I #11 Mar 12 2015 05:07:43
%S 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,
%T 1,0,0,35,420,3150,15180,36015,1,0,0,56,840,8400,60750,291060,688128,
%U 1,0,0,84,1512,18900,182270,1311240,6300672,14880348,1,0,0,120,2520,37800
%N 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.
%H Alois P. Heinz, <a href="/A144207/b144207.txt">Rows n = 0..140, flattened</a>
%F 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).
%e T(5,4) = 60 = 5*12, because there are 5 possibilities for a single node and T(4,4) = 12:
%e .1-2. .1-2. .1-2. .1.2. .1.2. .1-2. .1.2. .1.2. .1-2. .1-2. .1-2. .1-2.
%e .|X.. .|/|. .|/.. ..X|. .|/|. ../|. .|X.. .|\|. .|\.. ..X|. .|\|. ..\|.
%e .3.4. .3.4. .3-4. .3-4. .3-4. .3-4. .3-4. .3-4. .3-4. .3.4. .3.4. .3-4.
%e Triangle begins:
%e 1;
%e 1, 0;
%e 1, 0, 0;
%e 1, 0, 0, 1;
%e 1, 0, 0, 4, 12;
%e 1, 0, 0, 10, 60, 150;
%p 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);
%t 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 *)
%Y Columns 0, 1+2, 3, 4 give: A000012, A000004, A000292, A033486 or A112415. Diagonal gives: A053507. Row sums give: A144208. Cf. A007318.
%K nonn,tabl
%O 0,14
%A _Alois P. Heinz_, Sep 14 2008
|
