|
|
A215861
|
|
Number T(n,k) of simple labeled graphs on n nodes with exactly k connected components that are trees or cycles; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
|
|
18
|
|
|
1, 0, 1, 0, 1, 1, 0, 4, 3, 1, 0, 19, 19, 6, 1, 0, 137, 135, 55, 10, 1, 0, 1356, 1267, 540, 125, 15, 1, 0, 17167, 15029, 6412, 1610, 245, 21, 1, 0, 264664, 218627, 90734, 23597, 3990, 434, 28, 1, 0, 4803129, 3783582, 1515097, 394506, 70707, 8694, 714, 36, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,8
|
|
COMMENTS
|
Also the Bell transform of A215851(n+1). For the definition of the Bell transform see A264428 and the links given there. - Peter Luschny, Jan 21 2016
|
|
LINKS
|
|
|
FORMULA
|
T(0,0) = 1, T(n,k) = 0 for k<0 or k>n, and otherwise T(n,k) = Sum_{i=0..n-k} C(n-1,i)*T(n-1-i,k-1)*h(i) with h(i) = 1 for i<2 and h(i) = i!/2 + (i+1)^(i-1) else.
|
|
EXAMPLE
|
T(4,2) = 19:
.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.
.| . . / . .|/ . . \ . . |. . \|. . . .| |. . X .
.4 3. .4 3. .4 3. .4 3. .4 3. .4 3. .4-3. .4 3. .4 3.
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 1;
0, 4, 3, 1;
0, 19, 19, 6, 1;
0, 137, 135, 55, 10, 1;
0, 1356, 1267, 540, 125, 15, 1;
0, 17167, 15029, 6412, 1610, 245, 21, 1;
...
|
|
MAPLE
|
T:= proc(n, k) option remember; `if`(k<0 or k>n, 0,
`if`(n=0, 1, add(binomial(n-1, i)*T(n-1-i, k-1)*
`if`(i<2, 1, i!/2 +(i+1)^(i-1)), i=0..n-k)))
end:
seq(seq(T(n, k), k=0..n), n=0..12);
# Alternatively, with the function BellMatrix defined in A264428:
BellMatrix(n -> `if`(n<2, 1, n!/2+(n+1)^(n-1)), 8); # Peter Luschny, Jan 21 2016
|
|
MATHEMATICA
|
t[0, 0] = 1; t[n_, k_] /; k < 0 || k > n = 0; t[n_, k_] := t[n, k] =Sum[ Binomial[n-1, i]*t[n-1-i, k-1]* If[i < 2, 1, i!/2 + (i+1)^(i-1)], {i, 0, n-k}]; Table[t[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 07 2013 *)
(* Alternatively, with the function BellMatrix defined in A264428: *)
g[n_] = If[n < 2, 1, n!/2 + (n+1)^(n-1)]; BellMatrix[g, 8] (* Peter Luschny, Jan 21 2016 *)
rows = 11;
t = Table[If[n<2, 1, n!/2 + (n+1)^(n-1)], {n, 0, rows}];
T[n_, k_] := BellY[n, k, t];
|
|
PROG
|
(Sage) # uses[bell_matrix from A264428]
bell_matrix(lambda n: factorial(n)//2 + (n+1)^(n-1) if n>=2 else 1, 8) # Peter Luschny, Jan 21 2016
|
|
CROSSREFS
|
Columns k=0-10 give: A000007, A215851, A215852, A215853, A215854, A215855, A215856, A215857, A215858, A215859, A215860.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|