A144212 Triangle T(n,k), n>=3, 3<=k<=n, read by rows: T(n,k) = number of simple graphs on n labeled nodes, where each maximally connected subgraph consists of a single node or has a unique cycle of length k.

2, 17, 4, 221, 76, 13, 3261, 1486, 433, 61, 54801, 29506, 11593, 2941, 361, 1049235, 628531, 296353, 102481, 23041, 2521, 22695027, 14633011, 7795873, 3270961, 1010881, 204121, 20161, 548904831, 373486051, 217126225, 104038201, 39355201

Offset

3,1

Links

Alois P. Heinz, Rows n = 3..102, flattened

Formula

See program.

Example

T(4,4) = 4, because there are 4 simple graphs on 4 labeled nodes, where each maximally connected subgraph consists of a single node or has a unique cycle of length 4:
.1.2. .1-2. .1-2. .1.2.
..... .|.|. ..X.. .|X|.
.3.4. .3-4. .3-4. .3.4.
Triangle begins:
        2;
       17,     4;
      221,    76,    13;
     3261,  1486,   433,   61;
    54801, 29506, 11593, 2941, 361;

Maple

B:= proc(n, c, k) option remember; if c=0 then 1 elif c<0 or n<c then 0 elif c=n then binomial(n-1, k-1) *(k-1)! /2 *n^(n-k) else B(n-1, c, k) +add(binomial(n-1, j) * B(j+1, j+1, k) *B(n-1-j, c-j-1, k), j=k-1..c-1) fi end: T:= (n, k)-> add(B(n, c, k), c=0..n): seq(seq(T(n, k), k=3..n), n=3..11);

Mathematica

B[n_, c_, k_] := B[n, c, k] = Which[c == 0, 1, c<0 || n<c, 0, c == n, Binomial[n-1, k-1]*(k-1)!/2*n^(n-k), True, B[n-1, c, k] + Sum[Binomial[n-1, j]*B[j+1, j+1, k]*B[n-1-j, c-j-1, k], {j, k-1, c-1}]]; T[n_, k_] := Sum [B[n, c, k], {c, 0, n}]; Table[Table [T[n, k], {k, 3, n}], {n, 3, 11}] // Flatten (* Jean-François Alcover, Jan 21 2014, translated from Alois P. Heinz's Maple code *)

Crossrefs

Columns k=3, 4 give: A144208, A144210. Diagonal gives: A139149. Cf. A053507, A065889, A098909, A144207, A144209, A007318, A000142.

Sequence in context: A165234 A155895 A293179 * A186683 A210492 A355555

Adjacent sequences: A144209 A144210 A144211 * A144213 A144214 A144215

Keyword

nonn,tabl,look

Author

Alois P. Heinz, Sep 14 2008

Status

approved