cp's OEIS Frontend

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.

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