A063169 -id:A063169 - 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

A063170 Schenker sums with n-th term.

Original entry on oeis.org

1, 2, 10, 78, 824, 10970, 176112, 3309110, 71219584, 1727242866, 46602156800, 1384438376222, 44902138752000, 1578690429731402, 59805147699103744, 2428475127395631750, 105224992014096760832, 4845866591896268695010, 236356356027029797011456

Offset: 0

Marijke van Gans (marijke(AT)maxwellian.demon.co.uk)

Urn, n balls, with replacement: how many selections if we stop after a ball is chosen that was chosen already? Expected value is a(n)/n^n.
Conjectures: The exponent in the power of 2 in the prime factorization of a(n) (its 2-adic valuation) equals 1 if n is odd and equals n - A000120(n) if n is even. - Gerald McGarvey, Nov 17 2007, Jun 29 2012
Amdeberhan, Callan, and Moll (2012) have proved McGarvey's conjectures. - Jonathan Sondow, Jul 16 2012
a(n), for n >= 1, is the number of colored labeled mappings from n points to themselves, where each component is one of two colors. - Steven Finch, Nov 28 2021

			a(4) = (1*2*3*4) + 4*(2*3*4) + 4*4*(3*4) + 4*4*4*(4) + 4*4*4*4.
G.f. = 1 + 2*x + 10*x^2 + 78*x^3 + 824*x^4 + 10970*x^5 + 176112*x^6 + ...

D. E. Knuth, The Art of Computer Programming, 3rd ed. 1997, Vol. 1, Addison-Wesley, p. 123, Exercise Section 1.2.11.3 18.

G. C. Greubel, Table of n, a(n) for n = 0..385
Max Alekseyev, Recursion for A063170, answer to question on MathOverflow (2025).
T. Amdeberhan, D. Callan, and V. Moll, p-adic analysis and combinatorics of truncated exponential sums, preprint, 2012.
T. Amdeberhan, D. Callan and V. Moll, Valuations and combinatorics of truncated exponential sums, INTEGERS 13 (2013), #A21.
Steven Finch, Rounds, Color, Parity, Squares, arXiv:2111.14487 [math.CO], 2021.
Helmut Prodinger, An identity conjectured by Lacasse via the tree function, Electronic Journal of Combinatorics, 20(3) (2013), #P7.
David M. Smith and Geoffrey Smith, Tight Bounds on Information Leakage from Repeated Independent Runs, 2017 IEEE 30th Computer Security Foundations Symposium (CSF).
Marijke van Gans, Schenker sums
Eric Weisstein, Exponential Sum Function.

Cf. A000312, A134095, A090878, A036505, A120266, A214402, A219546 (Schenker primes).

seq(simplify(GAMMA(n+1,n)*exp(n)),n=0..20); # Vladeta Jovovic, Jul 21 2005

a[n_] := Round[ Gamma[n+1, n]*Exp[n]]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Feb 16 2012, after Vladeta Jovovic *)
a[ n_] := If[ n < 1, Boole[n == 0], n! Sum[ n^k / k!, {k, 0, n}]]; (* Michael Somos, Jun 05 2014 *)
a[ n_] := If[ n < 0, 0, n! Normal[ Exp[x] + x O[x]^n] /. x -> n]; (* Michael Somos, Jun 05 2014 *)

{a(n) = if( n<0, 0, n! * sum( k=0, n, n^k / k!))};

{a(n) = sum( k=0, n, binomial(n, k) * k^k * (n - k)^(n - k))}; /* Michael Somos, Jun 09 2004 */

for(n=0,17,print1(round(intnum(x=0,[oo,1],exp(-x)*(n+x)^n)),", ")) \\ Gerald McGarvey, Nov 17 2007

from math import comb
def A063170(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<<1) if n else 1 # Chai Wah Wu, Apr 26 2023

10 for N=1 to 42: T=N^N: S=T
20 for K=N to 1 step -1: T/=N: T*=K: S+=T: next K
30 print N,S: next N

a(n) = Sum_{k=0..n} n^k n!/k!.
a(n)/n! = Sum_{k=0..n} n^k/k!. (First n+1 terms of e^n power series.)
a(n) = A063169(n) + n^n.
E.g.f.: 1/(1-T)^2, where T=T(x) is Euler's tree function (see A000169).
E.g.f.: 1 / (1 - F), where F = F(x) is the e.g.f. of A003308. - Michael Somos, May 27 2012
a(n) = Sum_{k=0..n} binomial(n,k)*(n+k)^k*(-k)^(n-k). - Vladeta Jovovic, Oct 11 2007
Asymptotics of the coefficients: sqrt(Pi*n/2)*n^n. - N-E. Fahssi, Jan 25 2008
a(n) = A120266(n)*A214402(n) for n > 0. - Jonathan Sondow, Jul 16 2012
a(n) = Integral_{0..oo} exp(-x) * (n + x)^n dx. - Michael Somos, May 18 2004
a(n) = Integral_{0..oo} exp(-x)*(1+x/n)^n dx * n^n = A090878(n)/A036505(n-1) * n^n. - Gerald McGarvey, Nov 17 2007
EXP-CONV transform of A000312. - Tilman Neumann, Dec 13 2008
a(n) = n! * [x^n] exp(n*x)/(1 - x). - Ilya Gutkovskiy, Sep 23 2017
a(n) = (n+1)! - Sum_{k=0..n-1} binomial(n, k)*a(k)*(-k)^(n-k) for n > 0 with a(0) = 1 (see Max Alekseyev link). - Mikhail Kurkov, Jan 14 2025

A066324 Number of endofunctions on n labeled points constructed from k rooted trees.

Original entry on oeis.org

1, 2, 2, 9, 12, 6, 64, 96, 72, 24, 625, 1000, 900, 480, 120, 7776, 12960, 12960, 8640, 3600, 720, 117649, 201684, 216090, 164640, 88200, 30240, 5040, 2097152, 3670016, 4128768, 3440640, 2150400, 967680, 282240, 40320, 43046721

Offset: 1

Christian G. Bower, Dec 14 2001

T(n,k) = number of endofunctions with k recurrent elements. - Mitch Harris, Jul 06 2006

The sum of row n is n^n, for any n. Basically the same sequence arises when studying random mappings (see A243203, A243202). - Stanislav Sykora, Jun 01 2014

			Triangle T(n,k) begins:
       1;
       2,      2;
       9,     12,      6;
      64,     96,     72,     24;
     625,   1000,    900,    480,   120;
    7776,  12960,  12960,   8640,  3600,   720;
  117649, 201684, 216090, 164640, 88200, 30240, 5040;
  ...

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 87, see (2.3.28).
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, ex. 3.3.32.

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

Column 1: A000169.
Main diagonal: A000142.
T(n, n-1): A062119.
Row sums give A000312.
Cf. A001864, A021010, A063169, A122525, A144084, A243203.

T:= (n, k)-> k*n^(n-k)*(n-1)!/(n-k)!:
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Aug 22 2012

f[list_] := Select[list, # > 0 &]; t = Sum[n^(n - 1) x^n/n!, {n, 1, 20}]; Flatten[Map[f, Drop[Range[0, 10]! CoefficientList[Series[1/(1 - y*t), {x, 0, 10}], {x, y}], 1]]] (* Geoffrey Critzer, Dec 05 2011 *)

T(n, k)=k*n^(n-k)*(n-1)!/(n-k)! \\ Charles R Greathouse IV, Dec 05 2011

T(n,k) = k*n^(n-k)*(n-1)!/(n-k)!.
E.g.f. (relative to x): A(x, y)=1/(1-y*B(x)) - 1 = y*x +(2*y+2*y^2)*x^2/2! + (9*y+12*y^2+6*y^3)*x^3/3! + ..., where B(x) is e.g.f. A000169.
From Peter Bala, Sep 30 2011: (Start)
Let F(x,t) = x/(1+t*x)*exp(-x/(1+t*x)) = x*(1 - (1+t)*x + (1+4*t+2*t^2)*x^2/2! - ...). F is essentially the e.g.f. for A144084 (see also A021010). Then the e.g.f. for the present table is t*F(x,t)^(-1), where the compositional inverse is taken with respect to x.
Removing a factor of n from the n-th row entries results in A122525 in row reversed form.
(End)
Sum_{k=2..n} (k-1) * T(n,k) = A001864(n). - Geoffrey Critzer, Aug 19 2013
Sum_{k=1..n} k * T(n,k) = A063169(n). - Alois P. Heinz, Dec 15 2021

A219706 Total number of nonrecurrent elements in all functions f:{1,2,...,n}->{1,2,...,n}.

Original entry on oeis.org

0, 0, 2, 30, 456, 7780, 150480, 3279234, 79775360, 2146962024, 63397843200, 2039301671110, 71007167075328, 2661561062560140, 106874954684266496, 4577827118698118250, 208369657238965616640, 10044458122057793060176, 511225397403604416921600

Offset: 0

Geoffrey Critzer, Nov 25 2012

nonn

x in {1,2,...,n} is a recurrent element if there is some k such that f^k(x) = x where f^k(x) denotes iterated functional composition. In other words, a recurrent element is in a cycle of the functional digraph. An element that is not recurrent is a nonrecurrent element.

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

Cf. A000169, A063169, A219694.

b:= proc(n) option remember; `if`(n=0, [1, 0], add((p->p+
      [0, p[1]*j])((j-1)!*b(n-j)*binomial(n-1, j-1)), j=1..n))
    end:
a:= n-> (p-> n*p[1]-p[2])(add(b(j)*n^(n-j)
         *binomial(n-1, j-1), j=0..n)):
seq(a(n), n=0..25);  # Alois P. Heinz, May 22 2016

nn=20; f[list_] := Select[list,#>0&]; t=Sum[n^(n-1)x^n y^n/n!, {n,1,nn}]; Range[0,nn]! CoefficientList[Series[D[1/(1-x Exp[t]), y]/.y->1, {x,0,nn}], x]

from math import comb
def A219706(n): return (n-1)*n**n-(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) if n else 0 # Chai Wah Wu, Apr 26 2023

E.g.f.: T(x)^2/(1-T(x))^3 where T(x) is the e.g.f. for A000169.
a(n) = Sum_{k=1..n-1} A219694(n,k)*k.
a(n) = n^(n+1) - A063169(n).

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.

A347993 a(n) = n! * Sum_{k=1..n} (-1)^(k+1) * n^(n-k) / (n-k)!.

Original entry on oeis.org

1, 2, 15, 136, 1645, 24336, 426979, 8658560, 199234809, 5128019200, 145969492471, 4552809182208, 154404454932325, 5656950010320896, 222655633595044875, 9369696305273798656, 419790650812640438641, 19950175280765680680960, 1002394352017754098219999, 53092232229227200348160000

Offset: 1

Ilya Gutkovskiy, Sep 23 2021

nonn

Cf. A000169, A000312, A001865, A063169, A133297, A134095, A277458, A347994.

Table[n! Sum[(-1)^(k + 1) n^(n - k)/(n - k)!, {k, 1, n}], {n, 1, 20}]
nmax = 20; CoefficientList[Series[-LambertW[-x]/(1 - LambertW[-x]^2), {x, 0, nmax}], x] Range[0, nmax]! // Rest

a(n) = n! * sum(k=1, n, (-1)^(k+1)*n^(n-k)/(n-k)!); \\ Michel Marcus, Sep 23 2021

E.g.f.: -LambertW(-x) / (1 - LambertW(-x)^2).

a(n) = n * A133297(n).

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

A063170 Schenker sums with n-th term.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Python

UBASIC

Formula

A066324 Number of endofunctions on n labeled points constructed from k rooted trees.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A219706 Total number of nonrecurrent elements in all functions f:{1,2,...,n}->{1,2,...,n}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

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

A347993 a(n) = n! * Sum_{k=1..n} (-1)^(k+1) * n^(n-k) / (n-k)!.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Formula