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.

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

Offset: 0

Author

Steven Finch, Sep 23 2021

Keywords

• nonn
• tabl

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.

Examples

			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;
  ...
		

References

• R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, Chapter 8.

Links

• Alois P. Heinz, Rows n = 0..140, flattened
• Steven Finch, Permute, Graph, Map, Derange, arXiv:2111.05720 [math.CO], 2021.
• D. Panario and B. Richmond, Exact largest and smallest size of components, Algorithmica, 31 (2001), 413-432.

Crossrefs

Columns k=0-1 give: A000007, A350134.

Row sums give A000312.

Right border gives A001865.

T(2n,n) gives A350135.

Cf. A209324, A350157.

Programs

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)):
seq(T(n), n=0..12);  # Alois P. Heinz, Dec 16 2021

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}]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Dec 28 2021, after Alois P. Heinz *)

Formula

T(n,n) = A001865(n) for n >= 1.

Sum_{k=1..n} k * T(n,k) = A350157(n). - Alois P. Heinz, Dec 17 2021

Extensions

Edited by Alois P. Heinz, Dec 15 2021