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

A350446 Number T(n,k) of endofunctions on [n] with exactly k cycles of length larger than 1; triangle T(n,k), n>=0, 0<=k<=floor(n/2), read by rows.

Original entry on oeis.org

1, 1, 3, 1, 16, 11, 125, 128, 3, 1296, 1734, 95, 16807, 27409, 2425, 15, 262144, 499400, 61054, 945, 4782969, 10346328, 1605534, 42280, 105, 100000000, 240722160, 44981292, 1706012, 11025, 2357947691, 6222652233, 1351343346, 67291910, 763875, 945

Offset: 0

Alois P. Heinz, Dec 31 2021

			Triangle T(n,k) begins:
           1;
           1;
           3,          1;
          16,         11;
         125,        128,          3;
        1296,       1734,         95;
       16807,      27409,       2425,       15;
      262144,     499400,      61054,      945;
     4782969,   10346328,    1605534,    42280,    105;
   100000000,  240722160,   44981292,  1706012,  11025;
  2357947691, 6222652233, 1351343346, 67291910, 763875, 945;
  ...

Alois P. Heinz, Rows n = 0..200, flattened

Column k=0 gives A000272(n+1).
Row sums give A000312.
T(2n,n) gives A001147.
Cf. A055134, A060281, A349454, A350452.
Cf. A136394, A190314, A217701.

c:= proc(n) option remember; add(n!*n^(n-k-1)/(n-k)!, k=2..n) end:
t:= proc(n) option remember; n^(n-1) end:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(
      b(n-i)*binomial(n-1, i-1)*(c(i)*x+t(i)), i=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n/2))(b(n)):
seq(T(n), n=0..12);
# second Maple program:
egf := k-> (LambertW(-x)-log(1+LambertW(-x)))^k/(exp(LambertW(-x))*k!):
A350446 := (n, k)-> n! * coeff(series(egf(k), x, n+1), x, n):
seq(print(seq(A350446(n, k), k=0..n/2)), n=0..10); # Mélika Tebni, Mar 23 2023

c[n_] := c[n] = Sum[n!*n^(n - k - 1)/(n - k)!, {k, 2, n}];
t[n_] := t[n] = n^(n - 1);
b[n_] := b[n] = Expand[If[n == 0, 1, Sum[
     b[n - i]*Binomial[n - 1, i - 1]*(c[i]*x + t[i]), {i, 1, n}]]];
T[n_] :=  With[{p = b[n]}, Table[Coefficient[p, x, i], {i, 0, n/2}]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, May 06 2022, after Alois P. Heinz *)

From Mélika Tebni, Mar 23 2023: (Start)
E.g.f. of column k: (W(-x)-log(1 + W(-x)))^k / (exp(W(-x))*k!), W(x) the Lambert W-function.
T(n,k) = Sum_{j=k..n} n^(n-j)*binomial(n-1,j-1)*A136394(j,k), for n > 0.
T(n,k) = Sum_{j=k..n} (n-j+1)^(n-j-1)*binomial(n,j)*A350452(j,k).
Sum_{k=0..n/2} (k+1)*T(n,k) = A190314(n), for n > 0.
Sum_{k=0..n/2} 2^k*T(n,k) = A217701(n). (End)

A225213 Triangular array read by rows. T(n,k) is the number of cycles in the digraph representation of all functions f:{1,2,...,n}->{1,2,...,n} that have length k; 1<=k<=n.

Original entry on oeis.org

1, 4, 1, 27, 9, 2, 256, 96, 32, 6, 3125, 1250, 500, 150, 24, 46656, 19440, 8640, 3240, 864, 120, 823543, 352947, 168070, 72030, 24696, 5880, 720, 16777216, 7340032, 3670016, 1720320, 688128, 215040, 46080, 5040

Offset: 1

Geoffrey Critzer, May 01 2013

Row sums = A190314(n)
  Sum_{k=1..n} T(n,k)*k = A063169(n)
  T(n,n) = (n-1)!
  Column 1 = n^n = A000312
  Column 2 = A081131

			1,
4,      1,
27,     9,      2,
256,    96,     32,     6,
3125,   1250,   500,    150,   24,
46656,  19440,  8640,   3240,  864,   120,
823543, 352947, 168070, 72030, 24696, 5880, 720

Table[Table[(j-1)!Binomial[n,j]n^(n-j),{j,1,n}],{n,1,8}]//Grid

T(n,k) = (k-1)!*binomial(n,k)*n^(n-k)

E.g.f. for column k: A(x)^k/k * B(x) where A(x) is e.g.f. for A000169 and B(x) is e.g.f. for A000312.

A225723 Triangular array read by rows: T(n,k) is the number of size k components in the digraph representation of all functions f:{1,2,...,n}->{1,2,...,n}; n>=1, 1<=k<=n.

Original entry on oeis.org

1, 2, 3, 12, 9, 17, 108, 72, 68, 142, 1280, 810, 680, 710, 1569, 18750, 11520, 9180, 8520, 9414, 21576, 326592, 196875, 152320, 134190, 131796, 151032, 355081, 6588344, 3919104, 2975000, 2544640, 2372328, 2416512, 2840648, 6805296

Offset: 1

Geoffrey Critzer, May 13 2013

T(n,1) = n*(n-1)^(n-1) = A055897(n).
Row sums = A190314.
T(n,n) = A001865(n).
Sum_{k=1..n} T(n,k)*k = n^(n+1).

			Triangle T(n,k) begins:
       1;
       2,      3;
      12,      9,     17;
     108,     72,     68,    142;
    1280,    810,    680,    710,   1569;
   18750,  11520,   9180,   8520,   9414,  21576;
  326592, 196875, 152320, 134190, 131796, 151032, 355081;
  ...

Alois P. Heinz, Rows n = 1..100, flattened

Cf. A225213.

b:= n-> n!*add(n^(n-k-1)/(n-k)!, k=1..n):
T:= (n, k)-> binomial(n,k)*b(k)*(n-k)^(n-k):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, May 13 2013

nn = 8; tx = Sum[n^(n - 1) x^n/n!, {n, 1, nn}]; txy =
Sum[n^(n - 1) (x y)^n/n!, {n, 1, nn}];
Map[Select[#, # > 0 &] &,
  Drop[Range[0, nn]! CoefficientList[
     Series[Log[1/(1 - txy)]/(1 - tx), {x, 0, nn}], {x, y}],
   1]] // Grid

E.g.f.: log(1/(1 - A(x*y)))/(1 - A(x)) where A(x) is the e.g.f. for A000169.

T(n,k) = C(n,k)*A001865(k)*A000312(n-k). - Alois P. Heinz, May 13 2013

A302581 a(n) = n! * [x^n] -exp(-nx)log(1 - x).

Original entry on oeis.org

0, 1, -3, 20, -186, 2249, -33360, 586172, -11901008, 274098393, -7060189120, 201092672604, -6275340884736, 212915635727313, -7803567334571008, 307245946117223700, -12933084380738398208, 579587518114690731601, -27550568677612746940416, 1384553892443352890245636

Offset: 0

Ilya Gutkovskiy, Apr 10 2018

sign

N. J. A. Sloane, Transforms
Index entries for sequences related to logarithmic numbers

Cf. A002104, A002741, A104150, A134095, A190314.

Table[n! SeriesCoefficient[-Exp[-n x] Log[1 - x], {x, 0, n}], {n, 0, 19}]
Table[Sum[(-n)^(n - k) (k - 1)! Binomial[n, k], {k, 1, n}], {n, 0, 19}]
nmax = 20; CoefficientList[Series[-Log[1 - LambertW[x]]/(1 + LambertW[x]), {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jun 09 2019 *)

a(n) = Sum_{k=1..n} (-n)^(n-k)*(k-1)!*binomial(n,k).
E.g.f.: -log(1 - LambertW(x))/(1 + LambertW(x)). - Vaclav Kotesovec, Jun 09 2019
a(n) ~ -(-1)^n * log(2) * n^n. - Vaclav Kotesovec, Jun 09 2019

A308332 a(n) = n! * [x^n] 1/(1 - x)^exp(n*x).

Original entry on oeis.org

1, 1, 6, 60, 936, 21495, 681480, 28157451, 1455590528, 91689831225, 6907344210400, 612700433073707, 63107430169208832, 7455570223877314721, 999839697339310324224, 150885818035154310155625, 25434297819615665229168640, 4758031551536565527014516561

Offset: 0

Ilya Gutkovskiy, May 20 2019

nonn

Cf. A190314, A191365, A308333.

Table[n! SeriesCoefficient[1/(1 - x)^Exp[n x], {x, 0, n}], {n, 0, 17}]

A185070 Triangular array read by rows. T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} that have exactly k 3-cycles. n>=0, 0<=k<=floor(n/3).

Original entry on oeis.org

1, 1, 4, 25, 2, 224, 32, 2625, 500, 38056, 8560, 40, 657433, 164150, 1960, 13178880, 3526656, 71680, 300585601, 84389928, 2442720, 2240, 7683776000, 2232672000, 83328000, 224000, 217534555161, 64830707370, 2931500880, 14907200

Offset: 0

Geoffrey Critzer, Dec 25 2012

The total number of 3-cycles over all functions on {1,2,...,n} is 2*binomial(n,3)*n^(n-3). So we see that as n gets large the probability that a random function would contain k 3-cycles is a Poisson distribution with mean = 1/3. Generally, the total number of j-cycles over all functions on {1,2,...,n} is (j-1)!*binomial(n,j)*n^(n-j).

			          1;
          1;
          4;
         25,        2;
        224,       32;
       2625,      500;
      38056,     8560,      40;
     657433,   164150,    1960;
   13178880,  3526656,   71680;
  300585601, 84389928, 2442720, 2240;
  ...

Cf. A185025, A055134, A190314.

nn=10;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[ Series[Exp[t^3/3(y-1)]/(1-t),{x,0,nn}],{x,y}]//Grid

E.g.f.: exp(T(x)^3/3*(y - 1))/(1-T(x)) where T(x) is the e.g.f. for A000169.

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

A350446 Number T(n,k) of endofunctions on [n] with exactly k cycles of length larger than 1; triangle T(n,k), n>=0, 0<=k<=floor(n/2), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A225213 Triangular array read by rows. T(n,k) is the number of cycles in the digraph representation of all functions f:{1,2,...,n}->{1,2,...,n} that have length k; 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Programs

Mathematica

Formula

A225723 Triangular array read by rows: T(n,k) is the number of size k components in the digraph representation of all functions f:{1,2,...,n}->{1,2,...,n}; n>=1, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A302581 a(n) = n! * [x^n] -exp(-n*x)*log(1 - x).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A308332 a(n) = n! * [x^n] 1/(1 - x)^exp(n*x).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A185070 Triangular array read by rows. T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} that have exactly k 3-cycles. n>=0, 0<=k<=floor(n/3).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A302581 a(n) = n! * [x^n] -exp(-nx)log(1 - x).