login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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

%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