A209324 -id:A209324 - cp's OEIS frontend

A060281 Triangle T(n,k) read by rows giving number of labeled mappings (or functional digraphs) from n points to themselves (endofunctions) with exactly k cycles, k=1..n.

1, 3, 1, 17, 9, 1, 142, 95, 18, 1, 1569, 1220, 305, 30, 1, 21576, 18694, 5595, 745, 45, 1, 355081, 334369, 113974, 18515, 1540, 63, 1, 6805296, 6852460, 2581964, 484729, 49840, 2842, 84, 1, 148869153, 158479488, 64727522, 13591116, 1632099, 116172, 4830, 108, 1

Offset: 1

Vladeta Jovovic, Apr 09 2001

Also called sagittal graphs.
T(n,k)=1 iff n=k (counts the identity mapping of [n]). - Len Smiley, Apr 03 2006
Also the coefficients of the tree polynomials t_{n}(y) defined by (1-T(z))^(-y) = Sum_{n>=0} t_{n}(y) (z^n/n!) where T(z) is Cayley's tree function T(z) = Sum_{n>=1} n^(n-1) (z^n/n!) giving the number of labeled trees A000169. - Peter Luschny, Mar 03 2009

			Triangle T(n,k) begins:
        1;
        3,       1;
       17,       9,       1;
      142,      95,      18,      1;
     1569,    1220,     305,     30,     1;
    21576,   18694,    5595,    745,    45,    1;
   355081,  334369,  113974,  18515,  1540,   63,  1;
  6805296, 6852460, 2581964, 484729, 49840, 2842, 84, 1;
  ...
T(3,2)=9: (1,2,3)--> [(2,1,3),(3,2,1),(1,3,2),(1,1,3),(1,2,1), (1,2,2),(2,2,3),(3,2,3),(1,3,3)].
From _Peter Luschny_, Mar 03 2009: (Start)
  Tree polynomials (with offset 0):
  t_0(y) = 1;
  t_1(y) = y;
  t_2(y) = 3*y + y^2;
  t_3(y) = 17*y + 9*y^2 + y^3; (End)

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.
W. Szpankowski. Average case analysis of algorithms on sequences. John Wiley & Sons, 2001. - Peter Luschny, Mar 03 2009

Alois P. Heinz, Rows n = 1..141, flattened
Julia Handl and Joshua Knowles, An Investigation of Representations and Operators for Evolutionary Data Clustering with a Variable Number of Clusters, in Parallel Problem Solving from Nature-PPSN IX, Lecture Notes in Computer Science, Volume 4193/2006, Springer-Verlag. [From _N. J. A. Sloane_, Jul 09 2009]
D. E. Knuth, Convolution polynomials, The Mathematica J., 2 (1992), 67-78.
D. E. Knuth and B. Pittel, A recurrence related to trees, Proceedings of the American Mathematical Society, 105(2):335-349, 1989. [From _Peter Luschny_, Mar 03 2009]
J. Riordan, Enumeration of Linear Graphs for Mappings of Finite Sets, Ann. Math. Stat., 33, No. 1, Mar. 1962, pp. 178-185.
David M. Smith and Geoffrey Smith, Tight Bounds on Information Leakage from Repeated Independent Runs, 2017 IEEE 30th Computer Security Foundations Symposium (CSF).

Columns k=1-10 give: A001865, A065456, A273434, A273435, A273436, A273437, A273438, A273439, A273440, A273441.
Row sums: A000312.
Main diagonal and first lower diagonal give: A000012, A045943.
Cf. A000169, A190314, A242027, A209324, A273442, A347999.

A060281:= func< n,k | (&+[Binomial(n-1,j)*n^(n-1-j)*(-1)^(k+j+1)*StirlingFirst(j+1,k): j in [0..n-1]]) >;
[A060281(n,k): k in [1..n], n in [1..12]]; // G. C. Greubel, Nov 06 2024

with(combinat):T:=array(1..8,1..8):for m from 1 to 8 do for p from 1 to m do T[m,p]:=sum(binomial(m-1,k)*m^(m-1-k)*(-1)^(p+k+1)*stirling1(k+1,p),k=0..m-1); print(T[m,p]) od od; # Len Smiley, Apr 03 2006
From Peter Luschny, Mar 03 2009: (Start)
T := z -> sum(n^(n-1)*z^n/n!,n=1..16):
p := convert(simplify(series((1-T(z))^(-y),z,12)),'polynom'):
seq(print(coeff(p,z,i)*i!),i=0..8); (End)

t=Sum[n^(n-1) x^n/n!,{n,1,10}];
Transpose[Table[Rest[Range[0, 10]! CoefficientList[Series[Log[1/(1 - t)]^n/n!, {x, 0, 10}], x]], {n,1,10}]]//Grid (* Geoffrey Critzer, Mar 13 2011*)
Table[k! SeriesCoefficient[1/(1 + ProductLog[-t])^x, {t, 0, k}, {x, 0, j}], {k, 10}, {j, k}] (* Jan Mangaldan, Mar 02 2013 *)

@CachedFunction
def A060281(n,k): return sum(binomial(n-1,j)*n^(n-1-j)*stirling_number1(j+1,k) for j in range(n))
flatten([[A060281(n,k) for k in range(1,n+1)] for n in range(1,13)]) # G. C. Greubel, Nov 06 2024

E.g.f.: 1/(1 + LambertW(-x))^y.
T(n,k) = Sum_{j=0..n-1} C(n-1,j)*n^(n-1-j)*(-1)^(k+j+1)*A008275(j+1,k) = Sum_{j=0..n-1} binomial(n-1,j)*n^(n-1-j)*s(j+1,k). [Riordan] (Note: s(m,p) denotes signless Stirling cycle number (first kind), A008275 is the signed triangle.) - Len Smiley, Apr 03 2006
T(2*n, n) = A273442(n), n >= 1. -  Alois P. Heinz, May 22 2016
From Alois P. Heinz, Dec 17 2021: (Start)
Sum_{k=1..n} k * T(n,k) = A190314(n).
Sum_{k=1..n} (-1)^(k+1) * T(n,k) = A000169(n) for n>=1. (End)

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.

Original entry on oeis.org

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

Steven Finch, Sep 23 2021

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.

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

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

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.

Columns k=0-1 give: A000007, A350134.
Row sums give A000312.
Right border gives A001865.
T(2n,n) gives A350135.
Cf. A209324, A350157.

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

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

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

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

Edited by Alois P. Heinz, Dec 15 2021

A209327 Total number of nodes in the largest connected component of a functional digraph summed over all endofunctions f:{1,2,...,n}-> {1,2,...,n}.

Original entry on oeis.org

1, 7, 70, 863, 13056, 231187, 4737986, 109531991, 2835638008, 80950287311, 2533758258912, 86089196479255, 3161596017956936, 124590870125959343, 5251666647713483356, 235497961945975068767, 11205025852314462333408, 563351626162952600815087, 29864689571162209608920060, 1663796497123214306448307031

Offset: 1

Geoffrey Critzer, Jan 19 2013

nonn

a(n)/n^n is the average size of the largest component.

a(n)/n^(n + 1) is the probability that a particular node is in the largest component of the digraph.

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

Alois P. Heinz, Table of n, a(n) for n = 1..385

Cf. A001865, A209324, A350157.

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, max(m, i))*binomial(n-1, i-1), i=1..n))
    end:
a:= n-> (p-> add(coeff(p, x, i)*i, i=1..n))(b(n, 0)):
seq(a(n), n=1..20);  # Alois P. Heinz, Dec 17 2021

nn=20;g[list_]:= Sum[list[[i]]*i,{i,1,Length[list]}];t=Sum[n^(n-1)x^n/n!,{n,1,nn}];c=Log[1/(1-t)];b=Drop[Range[0,nn]!CoefficientList[Series[c,{x,0,nn}],x],1];f[list_]:=Select[list,#>0&];Map[g,Map[ f,Drop[Transpose[Table[Range[0,nn]!CoefficientList[Series[ Exp[Sum[b[[i]]x^i/i!,{i,1,n+1}]]-Exp[Sum[b[[i]]x^i/i!,{i,1,n}]],{x,0,nn}],x],{n,0,nn-1}]],1]]]

a(n) = Sum_{k=1..n} k * A209324(n,k).

cp's OEIS Frontend

A060281 Triangle T(n,k) read by rows giving number of labeled mappings (or functional digraphs) from n points to themselves (endofunctions) with exactly k cycles, k=1..n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A209327 Total number of nodes in the largest connected component of a functional digraph summed over all endofunctions f:{1,2,...,n}-> {1,2,...,n}.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula