login
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.
3
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
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
KEYWORD
nonn,tabl,look
AUTHOR
Alois P. Heinz, Sep 14 2008
STATUS
approved