|
|
A347999
|
|
Triangular array read by rows: T(n,k) is the number of endofunctions f:{1,2,...,n}-> {1,2,...,n} whose smallest connected component has exactly k nodes; n >= 0, 0 <= k <= n.
|
|
6
|
|
|
1, 0, 1, 0, 1, 3, 0, 10, 0, 17, 0, 87, 27, 0, 142, 0, 1046, 510, 0, 0, 1569, 0, 15395, 6795, 2890, 0, 0, 21576, 0, 269060, 114912, 84490, 0, 0, 0, 355081, 0, 5440463, 2332029, 1493688, 705740, 0, 0, 0, 6805296, 0, 124902874, 53389746, 32186168, 28072548, 0, 0, 0, 0, 148869153
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
COMMENTS
|
Here component means weakly connected component in the functional digraph of f.
If the mapping has no component, then the smallest component is defined to have size 0.
For the statistic "length of the largest component", see A209324.
|
|
REFERENCES
|
R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, Chapter 8.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
Triangle begins:
1;
0, 1;
0, 1, 3;
0, 10, 0, 17;
0, 87, 27, 0, 142;
0, 1046, 510, 0, 0, 1569;
0, 15395, 6795, 2890, 0, 0, 21576;
0, 269060, 114912, 84490, 0, 0, 0, 355081;
0, 5440463, 2332029, 1493688, 705740, 0, 0, 0, 6805296;
...
|
|
MAPLE
|
g:= proc(n) option remember; add(n^(n-j)*(n-1)!/(n-j)!, j=1..n) end:
b:= proc(n, m) option remember; `if`(n=0, x^m, add(g(i)*
b(n-i, min(m, i))*binomial(n-1, i-1), i=1..n))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n$2)):
|
|
MATHEMATICA
|
g[n_] := g[n] = Sum[n^(n - j)*(n - 1)!/(n - j)!, {j, 1, n}];
b[n_, m_] := b[n, m] = If[n == 0, x^m, Sum[g[i]*b[n - i, Min[m, i]]* Binomial[n - 1, i - 1], {i, 1, n}]];
T[n_] := With[{p = b[n, n]}, Table[Coefficient[p, x, i], {i, 0, n}]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|