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,15

Links

Alois P. Heinz, Rows n = 0..140, flattened

Formula

T(n,0) = 1, T(n,k) = 0 if k<0 or n<k, else T(n,k) = 3*C(n-1,3)*n^(n-4) if k=n, else T(n,k) = T(n-1,k) + Sum_{j=3..k-1} C(n-1,j) T(j+1,j+1) T(n-1-j,k-j-1).

Example

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;

Maple

T:= proc(n, k) option remember; if k=0 then 1 elif k<0 or n<k then 0 elif k=n then 3*binomial(n-1, 3)*n^(n-4) else T(n-1, k) +add(binomial(n-1, j) * T(j+1, j+1) *T(n-1-j, k-j-1), j=3..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, 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 *)

Crossrefs

Columns 0, 1+2+3, 4 give: A000012, A000004, A050534.

Main diagonal gives A065889.

Row sums give A144210.

Cf. A007318.

Sequence in context: A350449 A185664 A300812 * A094544 A062734 A336567

Adjacent sequences: A144206 A144207 A144208 * A144210 A144211 A144212

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 14 2008

Status

approved