|
|
A209324
|
|
Triangular array read by rows: T(n,k) is the number of endofunctions f:{1,2,...,n}-> {1,2,...,n} whose largest component has exactly k nodes; n>=1, 1<=k<=n.
|
|
4
|
|
|
1, 1, 3, 1, 9, 17, 1, 45, 68, 142, 1, 165, 680, 710, 1569, 1, 855, 6290, 8520, 9414, 21576, 1, 3843, 47600, 134190, 131796, 151032, 355081, 1, 21819, 481712, 1838900, 2372328, 2416512, 2840648, 6805296, 1, 114075, 5025608, 21488292, 50609664, 48934368, 51131664, 61247664, 148869153
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Here component means weakly connected component in the functional digraph of f.
Row sums are n^n.
For the statistic "length of the smallest component", see A347999.
|
|
REFERENCES
|
R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, Chapter 8.
|
|
LINKS
|
|
|
FORMULA
|
E.g.f. for column k: exp( Sum_{n=1..k} A001865(n) x^n/n!) - exp( Sum_{n=1..k-1} A001865(n) x^n/n!).
|
|
EXAMPLE
|
Triangle T(n,k) begins:
1;
1, 3;
1, 9, 17;
1, 45, 68, 142;
1, 165, 680, 710, 1569;
1, 855, 6290, 8520, 9414, 21576;
1, 3843, 47600, 134190, 131796, 151032, 355081;
1, 21819, 481712, 1838900, 2372328, 2416512, 2840648, 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, max(m, i))*binomial(n-1, i-1), i=1..n))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 0)):
|
|
MATHEMATICA
|
nn=8; t=Sum[n^(n-1)x^n/n!, {n, 1, nn}]; c=Log[1/(1-t)]; b=Drop[Range[0, nn]!CoefficientList[Series[c, {x, 0, nn}], x], 1]; f[list_]:=Select[list, #>0&]; Map[f, Drop[Transpose[Table[Range[0, nn]!CoefficientList[Series[ Exp[Sum[b[[i]]x^i/i!, {i, 1, n+1}]]-Exp[Sum[b[[i]]x^i/i!, {i, 1, n}]], {x, 0, nn}], x], {n, 0, nn-1}]], 1]]//Grid
(* Second program: *)
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, Max[m, i]]* Binomial[n - 1, i - 1], {i, 1, n}]];
T[n_] := With[{p = b[n, 0]}, Table[Coefficient[p, x, i], {i, 1, n}]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|