|
%I #52 Dec 28 2021 13:46:38
%S 1,0,1,0,1,3,0,10,0,17,0,87,27,0,142,0,1046,510,0,0,1569,0,15395,6795,
%T 2890,0,0,21576,0,269060,114912,84490,0,0,0,355081,0,5440463,2332029,
%U 1493688,705740,0,0,0,6805296,0,124902874,53389746,32186168,28072548,0,0,0,0,148869153
%N 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.
%C Here component means weakly connected component in the functional digraph of f.
%C If the mapping has no component, then the smallest component is defined to have size 0.
%C For the statistic "length of the largest component", see A209324.
%D R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, Chapter 8.
%H Alois P. Heinz, <a href="/A347999/b347999.txt">Rows n = 0..140, flattened</a>
%H Steven Finch, <a href="https://arxiv.org/abs/2111.05720">Permute, Graph, Map, Derange</a>, arXiv:2111.05720 [math.CO], 2021.
%H D. Panario and B. Richmond, <a href="https://doi.org/10.1007/s00453-001-0047-1">Exact largest and smallest size of components</a>, Algorithmica, 31 (2001), 413-432.
%F T(n,n) = A001865(n) for n >= 1.
%F Sum_{k=1..n} k * T(n,k) = A350157(n). - _Alois P. Heinz_, Dec 17 2021
%e Triangle begins:
%e 1;
%e 0, 1;
%e 0, 1, 3;
%e 0, 10, 0, 17;
%e 0, 87, 27, 0, 142;
%e 0, 1046, 510, 0, 0, 1569;
%e 0, 15395, 6795, 2890, 0, 0, 21576;
%e 0, 269060, 114912, 84490, 0, 0, 0, 355081;
%e 0, 5440463, 2332029, 1493688, 705740, 0, 0, 0, 6805296;
%e ...
%p g:= proc(n) option remember; add(n^(n-j)*(n-1)!/(n-j)!, j=1..n) end:
%p b:= proc(n, m) option remember; `if`(n=0, x^m, add(g(i)*
%p b(n-i, min(m, i))*binomial(n-1, i-1), i=1..n))
%p end:
%p T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n$2)):
%p seq(T(n), n=0..12); # _Alois P. Heinz_, Dec 16 2021
%t g[n_] := g[n] = Sum[n^(n - j)*(n - 1)!/(n - j)!, {j, 1, n}];
%t 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 T[n_] := With[{p = b[n, n]}, Table[Coefficient[p, x, i], {i, 0, n}]];
%t Table[T[n], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, Dec 28 2021, after _Alois P. Heinz_ *)
%Y Columns k=0-1 give: A000007, A350134.
%Y Row sums give A000312.
%Y Right border gives A001865.
%Y T(2n,n) gives A350135.
%Y Cf. A209324, A350157.
%K nonn,tabl
%O 0,6
%A _Steven Finch_, Sep 23 2021
%E Edited by _Alois P. Heinz_, Dec 15 2021
|
