|
Search: id:A144209
|
|
|
| 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. |
|
+0
3
|
|
| 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
(list; table; graph; listen)
|
|
|
OFFSET
|
0,15
|
|
|
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);
|
|
CROSSREFS
|
Columns 0, 1+2+3, 4 give: A000012, A000004, A050534. Diagonal gives: A065889. Row sums give: A144210. Cf. A007318.
Sequence in context: A099725 A128208 A154721 this_sequence A094544 A062734 A117389
Adjacent sequences: A144206 A144207 A144208 this_sequence A144210 A144211 A144212
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 14 2008
|
|
|
Search completed in 0.002 seconds
|
