A060281 -id:A060281 - cp's OEIS frontend

A001865 Number of connected functions on n labeled nodes.

1, 3, 17, 142, 1569, 21576, 355081, 6805296, 148869153, 3660215680, 99920609601, 2998836525312, 98139640241473, 3478081490967552, 132705415800984825, 5423640496274200576, 236389784118231290049, 10944997108429625524224, 536484538620663729658993

Offset: 1

N. J. A. Sloane

If one randomly selects a ball from an urn containing n different balls, with replacement, until exactly one ball has been selected twice, the probability that that ball was also the first ball selected once is a(n)/n^n. See also A000435. - Matthew Vandermast, Jun 15 2004

a(n) equals the permanent of the (n-1) X (n-1) matrix with n+1's along the main diagonal and 1's everywhere else. - John M. Campbell, Apr 20 2012

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 1, p. 112.
Ulrike Sattler, Decidable classes of formal power series with nice closure properties, Diplomarbeit im Fach Informatik, Univ. Erlangen - Nuernberg, Jul 27 1994
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..380 (first 50 terms from T. D. Noe)
H. Bergeron, E. M. F. Curado, J. P. Gazeau and L. M. C. S. Rodrigues, A note about combinatorial sequences and Incomplete Gamma function, arXiv preprint arXiv: 1309.6910 [math.CO], 2013.
Christian Brouder, William J. Keith, and Ângela Mestre, Closed forms for a multigraph enumeration, arXiv preprint arXiv:1301.0874 [math.CO], 2013.
Giulio Cerbai and Anders Claesson, Counting fixed-point-free Cayley permutations, arXiv:2507.09304 [math.CO], 2025. See pp. 8, 19.
Camille Combe, A geometric and combinatorial exploration of Hochschild lattices, arXiv:2007.00048 [math.CO], 2020. See p. 22.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 37
Leo Katz, Probability of indecomposability of a random mapping function, Ann. Math. Statist. 26, (1955), 512-517.
John Riordan, Letter to N. J. A. Sloane, Aug. 1970
Frank Schmidt and Rodica Simion, Card shuffling and a transformation on S_n, Aequationes Math. 44 (1992), no. 1, 11-34.
Bernd Sturmfels and Ngoc Mai Tran, Combinatorial Types of Tropical Eigenvectors, arXiv:1105.5504 [math.CO], 2011-2012.

a(n) = A000435(n) + n^(n-1). See also A063169.

Column k=1 of A060281.

spec := [B, {A=Prod(Z,Set(A)), B=Cycle(A)}, labeled]; [seq(combstruct[count](spec,size=n), n=0..20)];
seq(simplify(GAMMA(n,n)*exp(n)),n=1..20); # Vladeta Jovovic, Jul 21 2005

t=Sum[n^(n-1)x^n/n!,{n,1,20}];
Range[0,20]! CoefficientList[Series[Log[1/(1-t)]+1,{x,0,20}],x] (* Geoffrey Critzer, Mar 12 2011 *)
f[n_] := Sum[n! n^(n - k - 1)/(n - k)!, {k, n}]; Array[f, 18] (* Robert G. Wilson v *)
a[n_] := Exp[n]*Gamma[n, n]; Table[a[n] // FunctionExpand, {n, 1, 18}] (* Jean-François Alcover, May 13 2013, after Vladeta Jovovic *)

a(n)=if(n<0,0,n!*sum(k=1,n,n^(n-k-1)/(n-k)!))

a(n)=(1/n)*sum(k=1,n,binomial(n,k)*(n-k)^(n-k)*k^k) \\ Paul D. Hanna, Jul 04 2013

N=20; x='x+O('x^N); Vec(serlaplace(log(sum(k=0, N, (k*x)^k/k!)))) \\ Seiichi Manyama, May 27 2019

from math import comb
def A001865(n): return ((sum(comb(n,k)*(n-k)**(n-k)*k**k for k in range(1,(n+1>>1)))<<1) + (0 if n&1 else comb(n,m:=n>>1)*m**n))//n + n**(n-1) # Chai Wah Wu, Apr 25-26 2023

a(n) = Sum_{k=1..n} n!*n^(n-k-1) / (n-k)!.
E.g.f.: -log(1+LambertW(-x)). - Vladeta Jovovic, Apr 11 2001
E.g.f. satisfies 0=2y'^4+2y''^2-y'''y'-y''y'^2. - Michael Somos, Aug 23 2003
Integral representation in terms of the incomplete Gamma function: a(n) = exp(n+1)*Gamma(n+1,n+1) = exp(n+1)*Integral_{x=n+1..oo} x^n exp(-x) dx.
Asymptotics: sqrt(Pi*n/2)*n^(n-1). - N-E. Fahssi, Jan 25 2008, corrected by Vaclav Kotesovec, Nov 27 2012
a(n) = exp(1)*Integral_{x=1..oo} (n+x)^n*exp(-x) dx. - Gerald McGarvey, Apr 16 2008
a(n) = (1/n) * Sum_{k=1..n} C(n,k) * (n-k)^(n-k) * k^k. - Paul D. Hanna, Jul 04 2013
From Peter Bala, Jun 29 2016: (Start)
It appears that a(n) = (n-1)!*( e^n - Sum_{k >= 0} n^(n + k)/(n + k)! ) = (n-1)!*( e^n - Sum_{k >= 0} k^2*n^(n + k - 1)/(n + k)! ).
Note that (n-1)!*( e^n - Sum_{k >= 0} k^3*n^(n + k - 1)/(n + k)! ) also appears to be an integer sequence beginning [1, 5, 37, 370, 4681, 71736, 1292005, ...]. (End)
a(n) = Sum_{k=1..n} (n!/(n-k)!) * k^2 * n^(n-k-2). - Brian P Hawkins, Feb 07 2024

More terms from James Sellers, May 23 2000

A052182 Determinant of n X n matrix whose rows are cyclic permutations of 1..n.

Original entry on oeis.org

1, -3, 18, -160, 1875, -27216, 470596, -9437184, 215233605, -5500000000, 155624547606, -4829554409472, 163086595857367, -5952860799406080, 233543408203125000, -9799832789158199296, 437950726881001816329, -20766159817517617053696, 1041273502979112415328410

Offset: 1

Henry M. Gunn High School Mathematical Circle (Joshua Zucker), Jan 26 2000

Each row is a cyclic shift to the right by one place of the previous row. See the example below. - N. J. A. Sloane, Jan 07 2019
|a(n)| = number of labeled mappings from n points to themselves (endofunctions) with an odd number of cycles. - Vladeta Jovovic, Mar 30 2006
|a(n)| = number of functions from {1,2,...,n}->{1,2,...,n} such that of all recurrent elements the least is always mapped to the greatest. - Geoffrey Critzer, Aug 29 2013

			a(3) = 18 because this is the determinant of [(1,2,3), (3,1,2), (2,3,1) ].

T. D. Noe, Table of n, a(n) for n = 1..100
P. J. Cameron and P. Cara, Independent generating sets and geometries for symmetric groups, J. Algebra, Vol. 258, no. 2 (2002), 641-650.

Cf. A000312, A070896, A060281, A060435.

1,seq(LinearAlgebra:-Determinant(Matrix(n,shape=Circulant[$1..n])),n=2..30); # Robert Israel, Aug 31 2014

f[n_] := Det[ Table[ RotateLeft[ Range@ n, -j], {j, 0, n - 1}]]; Array[f, 19] (* or *)
f[n_] := (-1)^(n - 1)*n^(n - 2)*(n^2 + n)/2; Array[f, 19]
(* Robert G. Wilson v, Aug 31 2014 *)
Table[Det[Table[RotateRight[Range[k],n],{n,0,k-1}]],{k,30}] (* Harvey P. Dale, Jun 20 2024 *)

(1+n)^(n-1)*binomial(n+2,n)*(-1)^(n) $ n=0..16 // Zerinvary Lajos, Apr 01 2007

a(n) = (n+1)*(-n)^(n-1)/2; \\ Altug Alkan, Dec 17 2017

a(n) = (-1)^(n-1) * n^(n-2) * (n^2 + n)/2.
E.g.f.[A052182] = E.g.f.[A000312] * E.g.f.[A000272], so A052182(unsigned) is "tree-like". E.g.f.: (T-T^2/2)/(1-T), where T=T(x) is Euler's tree function (see A000169). E.g.f. for signed sequence: (W+W^2/2)/(1+W), where W=W(x)=-T(-x) is the Lambert W function. - Len Smiley, Dec 13 2001
Conjecture: a(n) = -Res( f(n), x^n - 1), where Res is the resultant and f(n) = Sum_{k=1..n} k*x^k. - Benedict W. J. Irwin, Dec 07 2016

More terms from James Sellers, Jan 31 2000

A242027 Number T(n,k) of endofunctions on [n] with cycles of k distinct lengths; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Original entry on oeis.org

1, 0, 1, 0, 4, 0, 24, 3, 0, 206, 50, 0, 2300, 825, 0, 31742, 14794, 120, 0, 522466, 294987, 6090, 0, 9996478, 6547946, 232792, 0, 218088504, 160994565, 8337420, 0, 5344652492, 4355845868, 299350440, 151200, 0, 145386399554, 128831993037, 11074483860, 18794160

Offset: 0

Alois P. Heinz, Aug 11 2014

			T(3,2) = 3: (1,3,2), (3,2,1), (2,1,3).
Triangle T(n,k) begins:
00 :  1;
01 :  0,          1;
02 :  0,          4;
03 :  0,         24,          3;
04 :  0,        206,         50;
05 :  0,       2300,        825;
06 :  0,      31742,      14794,       120;
07 :  0,     522466,     294987,      6090;
08 :  0,    9996478,    6547946,    232792;
09 :  0,  218088504,  160994565,   8337420;
10 :  0, 5344652492, 4355845868, 299350440, 151200;

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

Columns k=0-10 give: A000007, A241980 for n>0, A246283, A246284, A246285, A246286, A246287, A246288, A246289, A246290, A246291.
Row sums give A000312.
T(A000217(n),n) gives A246292.
Cf. A003056, A060281, A218868 (the same for permutations).

with(combinat):
b:= proc(n, i, k) option remember; `if`(n=0, `if`(k=0, 1, 0),
      `if`(i<1 or k<1, 0, add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1, k-`if`(j=0, 0, 1)), j=0..n/i)))
    end:
T:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j$2, k), j=0..n):
seq(seq(T(n, k), k=0..floor((sqrt(1+8*n)-1)/2)), n=0..14);

multinomial[n_, k_] := n!/Times @@ (k!); b[n_, i_, k_] := b[n, i, k] = If[n == 0, If[k==0, 1, 0], If[i<1 || k<1, 0, Sum[(i-1)!^j*multinomial[n, Join[ {n-i*j}, Array[i&, j]]]/j!*b[n-i*j, i-1, k-If[j==0, 0, 1]], {j, 0, n/i}]] ]; T[0, 0] = 1; T[n_, k_] := Sum[Binomial[n-1, j-1]*n^(n-j)*b[j, j, k], {j, 0, n}]; Table[T[n, k], {n, 0, 14}, {k, 0, Floor[(Sqrt[1+8n]-1)/2]}] // Flatten (* Jean-François Alcover, Feb 18 2017, translated from Maple *)

A344855 Number T(n,k) of permutations of [n] having k cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 3, 1, 0, 4, 11, 6, 1, 0, 8, 40, 35, 10, 1, 0, 16, 148, 195, 85, 15, 1, 0, 32, 560, 1078, 665, 175, 21, 1, 0, 64, 2160, 5992, 5033, 1820, 322, 28, 1, 0, 128, 8448, 33632, 37632, 17913, 4284, 546, 36, 1, 0, 256, 33344, 190800, 280760, 171465, 52941, 9030, 870, 45, 1

Offset: 0

Alois P. Heinz, May 30 2021

The sequence of column k satisfies a linear recurrence with constant coefficients of order k*(k+1)/2 = A000217(k).

			T(4,1) = 4: (1234), (1243), (1423), (1432).
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  1,    1;
  0,  2,    3,    1;
  0,  4,   11,    6,    1;
  0,  8,   40,   35,   10,    1;
  0, 16,  148,  195,   85,   15,   1;
  0, 32,  560, 1078,  665,  175,  21,  1;
  0, 64, 2160, 5992, 5033, 1820, 322, 28, 1;
  ...

Alois P. Heinz, Rows n = 0..140, flattened
Wikipedia, Permutation

Columns k=0-10 give: A000007, A166444, A346317, A346318, A346319, A346320, A346321, A346322, A346323, A346324, A346325.
Row sums give A187251.
Main diagonal gives A000012, lower diagonal gives A000217, second lower diagonal gives A000914.
T(n+1,n) gives A000217.
T(n+2,n) gives A000914.
T(2n,n) gives A345342.
Cf. A060281, A132393, A186366, A345341.

b:= proc(n) option remember; `if`(n=0, 1, add(expand(x*
      b(n-j)*binomial(n-1, j-1)*ceil(2^(j-2))), j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n)):
seq(T(n), n=0..12);

b[n_] := b[n] = If[n == 0, 1, Sum[Expand[x*b[n-j]*
     Binomial[n-1, j-1]*Ceiling[2^(j-2)]], {j, n}]];
T[n_] := CoefficientList[b[n], x];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Aug 23 2021, after Alois P. Heinz *)

Sum_{k=1..n} k * T(n,k) = A345341(n).

For fixed k, T(n,k) ~ (2*k)^n / (4^k * k!). - Vaclav Kotesovec, Jul 15 2021

A070896 Determinant of the Cayley addition table of Z_{n}.

Original entry on oeis.org

0, -1, -9, 96, 1250, -19440, -352947, 7340032, 172186884, -4500000000, -129687123005, 4086546038784, 139788510734886, -5159146026151936, -204350482177734375, 8646911284551352320, 389289535005334947848, -18580248257778920521728

Offset: 1

Santi Spadaro, May 23 2002

sign

a(n) is the determinant of the n X n matrix M_(i,j) = ((i+j) mod n) where i and j range from 0 to n-1. - Benoit Cloitre, Nov 29 2002

|a(n)| = number of labeled mappings from n points to themselves (endofunctions) with an even number of cycles. E.g.f.: (1/2)*LambertW(-x)^2/(1+LambertW(-x)). - Vladeta Jovovic, Mar 30 2006

			a(3) = -9 because the determinant of {{0,1,2}, {1,2,0}, {2,0,1}} is -9.

G. C. Greubel, Table of n, a(n) for n = 1..385

Cf. A000312, A052182, A060281, A060435.

[(-1)^Floor(n/2)*(1/2)*(n-1)*n^(n-1): n in [1..50]]; // G. C. Greubel, Nov 14 2017

Table[(-1)^Floor[n/2]*(1/2)*(n - 1)*n^(n - 1), {n, 1, 50}] (* G. C. Greubel, Nov 14 2017 *)

a(n)=(-1)^floor(n/2)*(1/2)*(n-1)*n^(n-1)

a(n) = (-1)^floor(n/2)*(1/2)*(n-1)*n^(n-1). - Benoit Cloitre, Nov 29 2002

A116956 Number of functions f:{1,2,...,n}->{1,2,...,n} with odd cycles only.

Original entry on oeis.org

1, 1, 3, 18, 157, 1800, 25551, 432376, 8494809, 190029888, 4768313275, 132626098176, 4049755214517, 134677876657792, 4845193429684167, 187490897290080000, 7765153170076158001, 342721890859339812864, 16058392049508837366771, 796093438190851834236928

Offset: 0

Vladeta Jovovic, Mar 30 2006

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

Cf. A070896, A060281, A060435, A070896.

Cf. A212599.

b:= proc(n) option remember; `if`(n=0, 1, add(`if`(j::odd,
       (j-1)!*b(n-j)*binomial(n-1, j-1), 0), j=1..n))
    end:
a:= n-> add(b(j)*n^(n-j)*binomial(n-1, j-1), j=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, May 20 2016

t = Sum[n^(n - 1) x^n/n!, {n, 1, 20}]; Range[0, 20]! CoefficientList[
Series[((1 + t)/(1 - t))^(1/2), {x, 0, 20}], x]  (* Geoffrey Critzer, Dec 07 2011 *)

E.g.f.: sqrt((1-LambertW(-x))/(1+LambertW(-x))).
Sum_{k=0..n} binomial(n,k)*a(k)*a(n-k) = 2*n^n, n>0. - Vladeta Jovovic, Oct 11 2007
a(n) ~ n! * 2^(3/4)*Gamma(3/4)*exp(n)/(2*Pi*n^(3/4)). - Vaclav Kotesovec, Sep 24 2013

A190314 The number of cycles in the digraph representation of all endofunctions on {1,2,...,n}.

Original entry on oeis.org

0, 1, 5, 38, 390, 5049, 78960, 1447886, 30461872, 723267369, 19130274880, 557794986814, 17775137850624, 614607897664305, 22917282895782912, 916671255921364950, 39152092883971954688, 1778431981539189344177, 85607684151779322519552, 4353142694568849287025142, 233169669255877689516032000

Offset: 0

Geoffrey Critzer, May 08 2011

nonn

Equivalently, since each component contains exactly one cycle, a(n) is the number of connected components in all endofuntions on {1,2,...,n}.  An endofunction on {1,2,...,n} is a function from {1,2,...,n} into {1,2,...,n}. Here we are counting self loops as a cycle.
The total number of j-cycles over all functions on {1,2,...,n} is (j-1)!*binomial(n,j)*n^(n-j). - Geoffrey Critzer, Dec 26 2012
a(n) was "not easy to estimate" in 1953 according to the Metropolis-Ulam reference. - David Callan, Jun 15 2018

			a(2) = 5 because there are four functions from {1,2} into {1,2} but only one of these is not connected: 1->1,2->2 so there is a total of 5 components in all. - _Geoffrey Critzer_, Mar 22 2012

Alois P. Heinz, Table of n, a(n) for n = 0..150
Giulio Cerbai and Anders Claesson, Counting fixed-point-free Cayley permutations, arXiv:2507.09304 [math.CO], 2025. See p. 23.
N. Metropolis and S. Ulam, A Property of Randomness of an Arithmetical Function, American Mathematical Monthly, Vol. 60, No. 4 (Apr., 1953), pp. 252-253.

Cf. A060281.

a:= n-> add((k-1)!*binomial(n, k)*n^(n-k), k=1..n):
seq(a(n), n=0..20);  # Alois P. Heinz, Dec 26 2012

f[list_] := Total[Table[i * list[[i]], {i,1,Length[list]}]]; t=Sum[n^(n-1)x^n/n!, {n,1,20}]; Map[f,Transpose[Table[Drop[Range[0,20]! CoefficientList[Series[Log[1/(1-t)]^k/k!, {x,0,20}], x], 1], {k,0,20}]]]
nmax = 20; CoefficientList[Series[-Log[1 + LambertW[-x]]/(1 + LambertW[-x]), {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jun 09 2019 *)

E.g.f.: Log[1/(1-T(x))]/(1-T(x)) where T(x) is the e.g.f. for A000169. - Geoffrey Critzer, Mar 22 2012
a(n) = Sum_{k=1..n} (k-1)!*C(n,k)*n^(n-k). - Geoffrey Critzer, Dec 26 2012
a(n) ~ n^n*(log(2*n) + gamma)/2, where gamma is the Euler-Mascheroni constant (A001620). - Vaclav Kotesovec, Oct 08 2013
a(n) = Sum_{k=1..n} A066324(n,k)*H(k) where H(k) is the k-th harmonic number. - Geoffrey Critzer, Nov 02 2014
a(n) = n! * [x^n] -exp(n*x)*log(1 - x). - Ilya Gutkovskiy, Jan 18 2018
a(n) = Sum_{k=1..n} k * A060281(n,k). - Alois P. Heinz, Dec 15 2021
Conjectures from Velin Yanev, Apr 14 2024: (Start)
a(n) = (n^n)*Integral_{t=0..oo} ((t + 1)^n - 1)/(t*e^(n*t)) dt for n > 0.
a(n) = (e^n)*Gamma(n) + (n^n)*(n*hypergeom([1, 1], [2, n + 2], n)/(n + 1) - ((-1)^n)*Gamma(n)*Gamma(1 - n, -n) + log(n) - polygamma(n) - 1/n + i*Pi) for n > 0, where polygamma is the digamma function and the bivariate gamma function is the upper incomplete gamma function. (End)

A350212 Number T(n,k) of endofunctions on [n] with exactly k isolated fixed points; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Original entry on oeis.org

1, 0, 1, 3, 0, 1, 17, 9, 0, 1, 169, 68, 18, 0, 1, 2079, 845, 170, 30, 0, 1, 31261, 12474, 2535, 340, 45, 0, 1, 554483, 218827, 43659, 5915, 595, 63, 0, 1, 11336753, 4435864, 875308, 116424, 11830, 952, 84, 0, 1, 262517615, 102030777, 19961388, 2625924, 261954, 21294, 1428, 108, 0, 1

Offset: 0

Alois P. Heinz, Dec 19 2021

			T(3,1) = 9: 122, 133, 132, 121, 323, 321, 113, 223, 213.
Triangle T(n,k) begins:
         1;
         0,       1;
         3,       0,      1;
        17,       9,      0,      1;
       169,      68,     18,      0,     1;
      2079,     845,    170,     30,     0,   1;
     31261,   12474,   2535,    340,    45,   0,  1;
    554483,  218827,  43659,   5915,   595,  63,  0, 1;
  11336753, 4435864, 875308, 116424, 11830, 952, 84, 0, 1;
  ...

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

Columns k=0-1 give: |A069856|, A348590.
Row sums give A000312.
T(n+1,n-1) gives A045943.
Cf. A001865, A008290, A008291, A055134, A055897, A060281, A086659, A124323, A350134, A349454.

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, m+`if`(i=1, 1, 0))*binomial(n-1, i-1), i=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):
seq(T(n), n=0..10);
# second Maple program:
A350212 := (n,k)-> add((-1)^(j-k)*binomial(j,k)*binomial(n,j)*(n-j)^(n-j), j=0..n):
seq(print(seq(A350212(n, k), k=0..n)), n=0..9); # Mélika Tebni, Nov 24 2022

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, m + If[i == 1, 1, 0]]*Binomial[n - 1, i - 1], {i, 1, n}]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, 0]];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Mar 11 2022, after Alois P. Heinz *)

Sum_{k=0..n} k * T(n,k) = A055897(n).
Sum_{k=1..n} T(n,k) = A350134(n).
From Mélika Tebni, Nov 24 2022: (Start)
T(n,k) = binomial(n, k)*|A069856(n-k)|.
E.g.f. column k: exp(-x)*x^k / ((1 + LambertW(-x))*k!).
T(n,k) = Sum_{j=0..n} (-1)^(j-k)*binomial(j, k)*binomial(n, j)*(n-j)^(n-j). (End)

A065456 Number of functions on n labeled nodes whose representation as a digraph has two components.

Original entry on oeis.org

0, 1, 9, 95, 1220, 18694, 334369, 6852460, 158479488, 4085349936, 116193701393, 3615197586912, 122165572502324, 4456126288810624, 174520484866919385, 7304657490838627072, 325420940777809245152, 15374940186972235659264, 767898500931828204443769

Offset: 1

John W. Layman, Nov 24 2001

nonn

			a(3)=9 since, on {1,2,3}, these functions and no others have two components: (3->1->3)(2->2), (1->3->1)(2->2), (3->2->2)(1->1), (2->3->2)(1->1), (2->1->2)(3->3), (1->2->1)(3->3), (1->2->2)(3->3), (1->3->3)(2->2) and (2->3->3)(1->1).

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

Column k=2 of A060281.

See A001865 for the numbers of one-component (i.e. connected) functions on n labeled nodes.

katz := n->(n-1)!*sum(n^k/k!,k=0..n-1); A001865 := []; for m from 1 to 30 do A001865 := [op(A001865),katz(m)] od; A065456 := []; for n from 1 to 29 do unequal_splits := sum(binomial(n,k)*A001865[k]*A001865[n-k],k=1..floor((n-1)/2)); if (n mod 2=0) then A065456 := [op(A065456),unequal_splits+binomial(n,n/2)*(A001865[n/2])^2/2] fi; if (n mod 2=1) then A065456 := [op(A065456),unequal_splits] fi od; print(A065456); #if the connected components are of equal size, we correct the double counting. The Katz reference is at A001865. - Len Smiley, Nov 26 2001
# second Maple program:
g:= proc(n) option remember; add(n^(n-j)*(n-1)!/(n-j)!, j=1..n) end:
a:= n-> add(binomial(n, i)*g(i)*g(n-i)/2, i=0..n):
seq(a(n), n=1..20);  # Alois P. Heinz, Dec 19 2021

t=Sum[n^(n-1)x^n/n!,{n,1,20}];  Range[0, 20]! CoefficientList[Series[Log[1/(1 - t)]^2/2, {x, 0, 20}],
x] (* Geoffrey Critzer, Oct 06 2011 *)
Rest[CoefficientList[Series[Log[1+LambertW[-x]]^2, {x, 0, 20}], x]/2* Range[0, 20]!] (* Vaclav Kotesovec, Oct 05 2013 *)

x='x+O('x^20); concat([0], Vec(serlaplace(log(1+lambertw(-x))^2/2 ))) \\ G. C. Greubel, Jan 18 2018

E.g.f.: 1/2 * log(1+LambertW(-x))^2. - Vladeta Jovovic, Nov 25 2001

a(n) ~ (n-1)! * exp(n)*(log(n/2) + gamma)/4, where gamma is the Euler-Mascheroni constant (A001620). - Vaclav Kotesovec, Oct 05 2013

More terms from Vladeta Jovovic, Nov 25 2001

A239761 Number of pairs of functions (f, g) on a set of n elements into itself satisfying f(g(x)) = f(x).

Original entry on oeis.org

1, 1, 10, 159, 3496, 98345, 3373056, 136535455, 6371523712, 336784920849, 19888195110400, 1297716672601151, 92721494240225280, 7199830049013964921, 603715489091812335616, 54366622743565012989375, 5233114241479255004839936, 536180296483497244155041825

Offset: 0

Chad Brewbaker, Mar 26 2014

nonn

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

Cf. A181162, A239769, A239773.
Column k=1 of A245910.
Cf. A001622, A295188.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(b(n-j, i-1)*binomial(n, j)*j^j, j=0..n)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..20);  # Alois P. Heinz, Jul 17 2014

f4[n_] := Sum[n^k Sum[Binomial[n - 1, j]*n^(n - 1 - j)*StirlingS1[j + 1, k] *(-1)^(j + k + 1), {j, 0, n - 1}], {k, 1, n}] (* David Einstein, Oct 31 2016 *)

a(n) ~ 5^(-1/4) * ((1+sqrt(5))/2)^(3*n-1/2) * n^n / exp(2*n/(1+sqrt(5))). - Vaclav Kotesovec, Aug 07 2014
a(n) = Sum_{k = 1..n} A060281(n,k) n^k. - David Einstein, Oct 31 2016
a(n) = n! * [x^n] 1/(1 + LambertW(-x))^n. - Ilya Gutkovskiy, Oct 03 2017

a(6)-a(7) from Giovanni Resta, Mar 28 2014

a(8)-a(17) from Alois P. Heinz, Jul 17 2014

cp's OEIS Frontend

A001865 Number of connected functions on n labeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A052182 Determinant of n X n matrix whose rows are cyclic permutations of 1..n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

MuPAD

PARI

Formula

Extensions

A242027 Number T(n,k) of endofunctions on [n] with cycles of k distinct lengths; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A344855 Number T(n,k) of permutations of [n] having k cycles of the form (c1, c2, ..., c_m) where c1 = min_{i>=1} c_i and c_j = min_{i>=j} c_i or c_j = max_{i>=j} c_i; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A070896 Determinant of the Cayley addition table of Z_{n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A116956 Number of functions f:{1,2,...,n}->{1,2,...,n} with odd cycles only.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A190314 The number of cycles in the digraph representation of all endofunctions on {1,2,...,n}.

Views