|
Search: id:A144163
|
|
|
| A144163 |
|
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 is either a tree or a cycle. |
|
+0
2
|
|
| 1, 1, 0, 1, 1, 0, 1, 3, 3, 1, 1, 6, 15, 20, 3, 1, 10, 45, 120, 150, 12, 1, 15, 105, 455, 1185, 1473, 70, 1, 21, 210, 1330, 5565, 14469, 18424, 465, 1, 28, 378, 3276, 19635, 81060, 213990, 280200, 3507, 1, 36, 630, 7140, 57393, 334656, 1385076, 3732300, 5029218
(list; table; graph; listen)
|
|
|
OFFSET
|
0,8
|
|
|
LINKS
|
Index entries for sequences related to trees
|
|
FORMULA
|
T(n,k) = A138464(n,k) + Sum_{j=3..k} C(n,j) A138464(n-j,k-j) A144161 (j,j).
|
|
EXAMPLE
|
T(4,3) = 20, because there are 20 simple graphs on 4 labeled nodes with 3 edges, where each maximally connected subgraph is either a tree or a cycle, 16 of these graphs consist of a single tree with 4 nodes and 4 consist of a cycle with 3 and a tree with 1 node:
.1-2. .1-2. .1.2. .1.2. .1-2. .1-2. .1-2. .1-2. .1-2. .1.2.
.|\.. ../|. ..\|. .|/.. .|... ...|. ../.. ..\.. .|.|. .|.|.
.4.3. .4.3. .4-3. .4-3. .4-3. .4-3. .4-3. .4-3. .4.3. .4-3.
.1.2. .1.2. .1-2. .1.2. .1.2. .1.2. .1.2. .1.2. .1-2. .1-2.
.|/|. .|\|. ..X.. ..X|. ..X.. .|X.. ../|. .|\.. .|/.. ..\|.
.4.3. .4.3. .4.3. .4.3. .4-3. .4.3. .4-3. .4-3. .4.3. .4.3.
Triangle begins:
1
1, 0
1, 1, 0
1, 3, 3, 1
1, 6, 15, 20, 3
1, 10, 45, 120, 150, 12
|
|
MAPLE
|
f:= proc(n, k) option remember; local j; if k=0 then 1 elif k<0 or n<=k then 0 elif k=n-1 then n^(n-2) else add (binomial (n-1, j) * f(j+1, j) *f(n-1-j, k-j), j=0..k) fi end: c:= proc(n, k) option remember; local i, j; if k=0 then 1 elif k<0 or n<k then 0 else c(n-1, k) +add (mul (n-i, i=1..j) *c(n-1-j, k-j-1), j=2..k)/2 fi end: T:= proc(n, k) f(n, k) +add (binomial(n, j) *f(n-j, k-j) *c(j, j), j=3..k) end: seq (seq (T(n, k), k=0..n), n=0..12);
|
|
CROSSREFS
|
Columns 0-3 give: A000012, A000217, A050534, A093566. Diagonal gives: A001205. Row sums give: A144164. Cf. A138464, A144161, A007318, A000142.
Sequence in context: A015109 A157636 A086626 this_sequence A080858 A144228 A083029
Adjacent sequences: A144160 A144161 A144162 this_sequence A144164 A144165 A144166
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 12 2008
|
|
|
Search completed in 0.003 seconds
|
