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,6

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.

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.

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

Example

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

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 *)

Crossrefs

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

Row sums give A000312.

Right border gives A001865.

T(2n,n) gives A350135.

Cf. A209324, A350157.

Sequence in context: A336710 A294106 A094472 * A028850 A138364 A095364

Adjacent sequences: A347996 A347997 A347998 * A348000 A348001 A348002

Keyword

nonn,tabl

Author

Steven Finch, Sep 23 2021

Extensions

Edited by Alois P. Heinz, Dec 15 2021

Status

approved