|
| |
|
|
A144161
|
|
Triangle read by rows: T(n,k) = number of simple graphs on n labeled nodes with k edges that are node-disjoint unions of undirected cycle subgraphs.
|
|
4
| |
|
|
1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 4, 3, 1, 0, 0, 10, 15, 12, 1, 0, 0, 20, 45, 72, 70, 1, 0, 0, 35, 105, 252, 490, 465, 1, 0, 0, 56, 210, 672, 1960, 3720, 3507, 1, 0, 0, 84, 378, 1512, 5880, 16740, 31563, 30016, 1, 0, 0, 120, 630, 3024, 14700, 55800, 157815, 300160, 286884
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,14
|
|
|
LINKS
| Alois P. Heinz, Rows n = 0..140, flattened
|
|
|
FORMULA
| T(n,0) = 1, T(n,k) = 0 if k<0 or n<k, else T(n,k) = T(n-1,k) + 1/2 * Sum_{j=2..k} T(n-1-j,k-j-1) * Product_{i=1..j} (n-i).
|
|
|
EXAMPLE
| T(4,3) = 4, because there are 4 simple graphs with 3 edges that are node-disjoint unions of undirected cycle subgraphs:
.1.2. .1.2. .1-2. .1-2.
../|. .|\.. ..\|. .|/..
.3-4. .3-4. .3.4. .3.4.
T(6,6) = C(6,3)/2+5!/2 = 70.
Triangle begins:
1;
1, 0;
1, 0, 0;
1, 0, 0, 1;
1, 0, 0, 4, 3;
1, 0, 0, 10, 15, 12;
1, 0, 0, 20, 45, 72, 70;
|
|
|
MAPLE
| T:= proc(n, k) option remember; local i, j; if k=0 then 1 elif k<0 or n<k then 0 else T(n-1, k) +add (mul (n-i, i=1..j) *T(n-1-j, k-j-1), j=2..k)/2 fi end: seq (seq (T(n, k), k=0..n), n=0..12);
|
|
|
CROSSREFS
| Columns 0, 1+2, 3-4 give: A000012, A000004, A000292, A050534. Diagonal gives: A001205. Row sums give: A108246. Cf. A007318, A000142.
Sequence in context: A136160 A120362 A010102 * A054669 A131027 A133475
Adjacent sequences: A144158 A144159 A144160 * A144162 A144163 A144164
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 12 2008
|
| |
|
|
