login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 6
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 (list; table; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 22 23:50 EST 2022. Contains 350504 sequences. (Running on oeis4.)