|
Search: id:A144207
|
|
|
| A144207 |
|
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. |
|
+0
3
|
|
| 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, 1, 0, 0, 35, 420, 3150, 15180, 36015, 1, 0, 0, 56, 840, 8400, 60750, 291060, 688128, 1, 0, 0, 84, 1512, 18900, 182270, 1311240, 6300672, 14880348, 1, 0, 0, 120, 2520, 37800
(list; table; graph; listen)
|
|
|
OFFSET
|
0,14
|
|
|
FORMULA
|
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).
|
|
EXAMPLE
|
T(5,4) = 60 = 5*12, because there are 5 possibilities for a single node and T(4,4) = 12:
.1-2. .1-2. .1-2. .1.2. .1.2. .1-2. .1.2. .1.2. .1-2. .1-2. .1-2. .1-2.
.|X.. .|/|. .|/.. ..X|. .|/|. ../|. .|X.. .|\|. .|\.. ..X|. .|\|. ..\|.
.3.4. .3.4. .3-4. .3-4. .3-4. .3-4. .3-4. .3-4. .3-4. .3.4. .3.4. .3-4.
Triangle begins:
1
1, 0
1, 0, 0
1, 0, 0, 1
1, 0, 0, 4, 12
1, 0, 0, 10, 60, 150
|
|
MAPLE
|
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);
|
|
CROSSREFS
|
Columns 0, 1+2, 3, 4 give: A000012, A000004, A000292, A033486 or A112415. Diagonal gives: A053507. Row sums give: A144208. Cf. A007318.
Sequence in context: A113314 A014458 A099733 this_sequence A016487 A104063 A010296
Adjacent sequences: A144204 A144205 A144206 this_sequence A144208 A144209 A144210
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 14 2008
|
|
|
Search completed in 0.002 seconds
|
