A347999 -id:A347999 - 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)

A209324 Triangular array read by rows: T(n,k) is the number of endofunctions f:{1,2,...,n}-> {1,2,...,n} whose largest component has exactly k nodes; n>=1, 1<=k<=n.

Original entry on oeis.org

1, 1, 3, 1, 9, 17, 1, 45, 68, 142, 1, 165, 680, 710, 1569, 1, 855, 6290, 8520, 9414, 21576, 1, 3843, 47600, 134190, 131796, 151032, 355081, 1, 21819, 481712, 1838900, 2372328, 2416512, 2840648, 6805296, 1, 114075, 5025608, 21488292, 50609664, 48934368, 51131664, 61247664, 148869153

Offset: 1

Geoffrey Critzer, Jan 19 2013

Here component means weakly connected component in the functional digraph of f.
Row sums are n^n.
T(n,n) = A001865.
For the statistic "length of the smallest component", see A347999.

			Triangle T(n,k) begins:
  1;
  1,     3;
  1,     9,     17;
  1,    45,     68,     142;
  1,   165,    680,     710,    1569;
  1,   855,   6290,    8520,    9414,   21576;
  1,  3843,  47600,  134190,  131796,  151032,  355081;
  1, 21819, 481712, 1838900, 2372328, 2416512, 2840648, 6805296;
  ...

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

Alois P. Heinz, Rows n = 1..141, 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.

Main diagonal gives A001865.
Row sums give A000312.
Cf. A209327, A347999.

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

nn=8;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[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]]//Grid
(* Second program: *)
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, Max[m, i]]* Binomial[n - 1, i - 1], {i, 1, n}]];
T[n_] := With[{p = b[n, 0]}, Table[Coefficient[p, x, i], {i, 1, n}]];
Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Dec 30 2021, after Alois P. Heinz *)

E.g.f. for column k: exp( Sum_{n=1..k} A001865(n) x^n/n!) - exp( Sum_{n=1..k-1} A001865(n) x^n/n!).

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

A350134 Number of endofunctions on [n] with at least one isolated fixed point.

Original entry on oeis.org

0, 1, 1, 10, 87, 1046, 15395, 269060, 5440463, 124902874, 3208994379, 91208536112, 2841279322871, 96258245162678, 3523457725743059, 138573785311560916, 5827414570508386335, 260928229315498155314, 12393729720071855683739, 622422708333615857463608

Offset: 0

Alois P. Heinz, Dec 15 2021

nonn

			a(3) = 10: 123, 122, 133, 132, 121, 323, 321, 113, 223, 213.

Alois P. Heinz, Table of n, a(n) for n = 0..386

Column k=1 of A347999.

Cf. A000312, A001865, A045531, A069856, A204042, A350212.

g:= proc(n) option remember; add(n^(n-j)*(n-1)!/(n-j)!, j=1..n) end:
b:= proc(n, t) option remember; `if`(n=0, t, add(g(i)*
      b(n-i, `if`(i=1, 1, t))*binomial(n-1, i-1), i=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..23);

g[n_] := g[n] = Sum[n^(n - j)*(n - 1)!/(n - j)!, {j, 1, n}];
b[n_, t_] := b[n, t] = If[n == 0, t, Sum[g[i]*
     b[n - i, If[i == 1, 1, t]]*Binomial[n - 1, i - 1], {i, 1, n}]];
a[n_] := b[n, 0];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Apr 27 2022, after Alois P. Heinz *)

a(n) = A000312(n) - abs(A069856(n)).

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

A350157 Total number of nodes in the smallest connected component summed over all endofunctions on [n].

Original entry on oeis.org

0, 1, 7, 61, 709, 9911, 167111, 3237921, 71850913, 1780353439, 49100614399, 1482061739423, 48873720208853, 1740252983702871, 66793644836081827, 2740470162691675711, 120029057782404141841, 5575505641199441262767, 274412698693082818767335, 14236421024010426118259883

Offset: 0

Alois P. Heinz, Dec 17 2021

nonn

			a(2) = 7 = 2 + 2 + 1 + 2: 11, 22, 12, 21.

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

Column k=1 of A350202.

Cf. A000312, A001865, A007778, A209327, A347999.

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(
      b(n-i, min(m, i))*g(i)*binomial(n-1, i-1), i=1..n))
    end:
a:= n-> (p-> add(coeff(p, x, i)*i, i=0..n))(b(n,n)):
seq(a(n), n=0..23);

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[
     b[n - i, Min[m, i]]*g[i]*Binomial[n - 1, i - 1], {i, 1, n}]];
a[n_] := Function[p, Sum[Coefficient[p, x, i]*i, {i, 0, n}]][b[n, n]];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Apr 27 2022, after Alois P. Heinz *)

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

A350135 Number of endofunctions on [2n] whose smallest connected component has size n.

Original entry on oeis.org

1, 1, 27, 2890, 705740, 310181886, 215071984512, 216357598418676, 298018065222408960, 538758820820128412790, 1237604585414359892787200, 3521561770316172974098259916, 12159265179096745219044911480832, 50086112147669900240287215353718700, 242646275221231775443338250567758643200

Offset: 0

Alois P. Heinz, Dec 15 2021

nonn

a(0) = 1 by convention.

Number of endofunctions on [2n] with two connected components of size n.

			a(1) = 1: 12.

Alois P. Heinz, Table of n, a(n) for n = 0..193

Cf. A001865, A065456, A088218, A347999.

a:= n-> `if`(n=0, 1, add(n^(n-j)*(n-1)!/(n-j)!, j=1..n)^2*binomial(2*n, n)/2):
seq(a(n), n=0..14);

a(n) = A347999(2n,n).

a(n) = A001865(n)^2 * A088218(n) for n >= 1.

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

A209324 Triangular array read by rows: T(n,k) is the number of endofunctions f:{1,2,...,n}-> {1,2,...,n} whose largest component has exactly k nodes; n>=1, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A350134 Number of endofunctions on [n] with at least one isolated fixed point.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A350157 Total number of nodes in the smallest connected component summed over all endofunctions on [n].

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A350135 Number of endofunctions on [2n] whose smallest connected component has size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula