A001865 -id:A001865 - cp's OEIS frontend

A063169 a(n) = n*A001865(n).

1, 6, 51, 568, 7845, 129456, 2485567, 54442368, 1339822377, 36602156800, 1099126705611, 35986038303744, 1275815323139149, 48693140873545728, 1990581237014772375, 86778247940387209216, 4018626330009931930833, 197009947951733259436032, 10193206233792610863520867

Offset: 1

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

Schenker sums without n-th term.
a(n)/n^n = Q(n) (called Ramanujan's function by Knuth).
Urn, n balls, with replacement: how many selections before a ball is chosen that was chosen already? Expected value is a(n)/n^n.
a(n) is the total number of recurrent elements over all endofunctions on n labeled points. a(n) = Sum_{k=1..n} A066324(n,k)*k. - Geoffrey Critzer, Dec 05 2011

			a(4) = (1*2*3*4) + 4*(2*3*4) + 4*4*(3*4) + 4*4*4*(4) = 568.

D. E. Knuth, The Art of Computer Programming, 3rd ed. 1997, Vol. 1, Addison-Wesley, Reading, MA, 1.2.11.3 p. 116

Alois P. Heinz, Table of n, a(n) for n = 1..150
Marijke van Gans, Schenker sums
Don Zagier, Partitions, Modular Forms and Moduli Spaces, Youtube video of a lecture at Institut Henri Poincaré, Feb 28 2017.

Cf. A001865, A066324, A219706.

Flatten[Range[0, 20]! CoefficientList[Series[D[1/(1 - y t), y] /. y -> 1, {x, 0, 20}], {x, y}]]
(* Second program: *)
a[n_] := Exp[n]*Gamma[n+1, n] - n^n; Array[a, 19] (* Jean-François Alcover, Jan 25 2018 *)

a(n)=sum(k=1,n,binomial(n,k)*n^(n-k)*k!) /* Michael Somos, Jun 09 2004 */

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

a(n)=sum(k=0,n-1,n!/k!*n^k) \\ Ruud H.G. van Tol, Jan 14 2023

from math import comb
def A063169(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 # Chai Wah Wu, Apr 25-26 2023

10 for N=1 to 42 : T=N^N : S=0
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-1} n^k * n!/k!.
a(n)/n! = Sum_{k=0..n-1} n^k/k! (first n terms of e^n power series).
E.g.f.: T/(1-T)^2, where T=T(x) is Euler's tree function (see A000169) - Len Smiley, Nov 28 2001
E.g.f.: -LambertW(-x)/(1+LambertW(-x))^2. - Alois P. Heinz, Nov 16 2011
a(n) = A063170(n) - n^n.
a(n) = Sum_{k=1..n} C(n,k) * (n-k)^(n-k) * k^k. - Paul D. Hanna, Jul 04 2013
a(n) ~ n^(n+1/2)*sqrt(Pi/2). - Vaclav Kotesovec, Oct 05 2013
a(n) = Sum_{k=1..n} (n!/(n-k)!) * k^2 * n^(n-k-1). - Brian P Hawkins, Feb 07 2024

A053506 a(n) = (n-1)*n^(n-2).

Original entry on oeis.org

0, 1, 6, 48, 500, 6480, 100842, 1835008, 38263752, 900000000, 23579476910, 681091006464, 21505924728444, 737020860878848, 27246730957031250, 1080863910568919040, 45798768824157052688, 2064472028642102280192, 98646963440126439346902, 4980736000000000000000000

Offset: 1

N. J. A. Sloane, Jan 15 2000

nonn

a(n) is the number of endofunctions f of [n] which interchange a pair a<->b and for all x in [n] some iterate f^k(x) = a. E.g., a(3) = 6: 1<->2<-3; 3->1<->2; 2<->3<-1; 1->2<->3; 1<->3<-2; 2->1<->3. - Len Smiley, Nov 27 2001
If offset is 0: right side of the binomial sum n-> sum( i^(i-1) * (n-i+1)^(n-i)*binomial(n, i), i=1..n) - Yong Kong (ykong(AT)curagen.com), Dec 28 2000
a(n) is the number of birooted labeled trees on n nodes in which the two root nodes are adjacent. - N. J. A. Sloane, May 01 2018
a(n) is the number of ways to partition the complete graph K_n into two components and choose an arborescence on each component. - Harry Richman, May 11 2022

A. P. Prudnikov, Yu. A. Brychkov and O. I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992, Eq. (4.2.2.36)
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Prop. 5.3.2.

G. C. Greubel, Table of n, a(n) for n = 1..250
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
Eric Weisstein's World of Mathematics, Graph Edge

Cf. A000169, A000312, A053507, A053508, A053509, A083483, A195242.

Cf. A001865 which is the sum of A000169 + A053506 + A065513 + A065888 + ...

List([1..20], n-> (n-1)*n^(n-2)) # G. C. Greubel, May 15 2019

[(n-1)*n^(n-2): n in [1..20]]; // G. C. Greubel, May 15 2019

Mathematica
```
Table[(n-1)*n^(n-2), {n,20}]
```

vector(20, n, (n-1)*n^(n-2)) \\ G. C. Greubel, Jan 18 2017

[(n-1)*n^(n-2) for n in (1..20)] # G. C. Greubel, May 15 2019

E.g.f.: LambertW(-x)^2/2. - Vladeta Jovovic, Apr 07 2001
E.g.f. if offset 0: W(-x)^2/((1+W(-x))*x), W(x) Lambert's function (principal branch).
The sequence 1, 1, 6, 48, ... satisfies a(n) = (n*(n+1)^n + 0^n)/(n+1); it is the main diagonal of A085388. - Paul Barry, Jun 30 2003
a(n) = Sum_{i=1..n-1} binomial(n-1,i-1)*i^(i-2)*(n-i)^(n-i). - Dmitry Kruchinin, Oct 28 2013
If offset = 0 and a(0) = 1 then a(n) = Sum_{k=0..n} (-1)^(n-k)* binomial(-k,-n)*n^k (cf. A195242). - Peter Luschny, Apr 11 2016

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.

Original entry on oeis.org

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)

A000435 Normalized total height of all nodes in all rooted trees with n labeled nodes.

Original entry on oeis.org

0, 1, 8, 78, 944, 13800, 237432, 4708144, 105822432, 2660215680, 73983185000, 2255828154624, 74841555118992, 2684366717713408, 103512489775594200, 4270718991667353600, 187728592242564421568, 8759085548690928992256, 432357188322752488126152, 22510748754252398927872000

Offset: 1

N. J. A. Sloane

This is the sequence that started it all: the first sequence in the database!
The height h(V) of a node V in a rooted tree is its distance from the root. a(n) = Sum_{all nodes V in all n^(n-1) rooted trees on n nodes} h(V)/n.
In the trees which have [0, n-1] = (0, 1, ..., n-1) as their ordered set of nodes, the number of nodes at distance i from node 0 is f(n,i) = (n-1)...(n-i)(i+1)n^(j-1), 0 <= i < n-1, i+j = n-1 (and f(n,n-1) = (n-1)!): (n-1)...(n-i) counts the words coding the paths of length i from any node to 0, n^(j-1) counts the Pruefer codes of the rest, words build by iterated deletion of the greater node of degree 1 ... except the last one, (i+1), necessary pointing at the path. If g(n,i) = (n-1)...(n-i)n^j, i+j = n-1, f(n,i) = g(n,i) - g(n,i+1), g(n,i) = Sum_{k>=i} f(n,k), the sequence is Sum_{i=1..n-1} g(n,i). - Claude Lenormand (claude.lenormand(AT)free.fr), Jan 26 2001
If one randomly selects one ball from an urn containing n different balls, with replacement, until exactly one ball has been selected twice, the probability that this ball was also the second ball to be selected once is a(n)/n^n. See also A001865. - Matthew Vandermast, Jun 15 2004
a(n) is the number of connected endofunctions with no fixed points. - Geoffrey Critzer, Dec 13 2011
a(n) is the number of weakly connected simple digraphs on n labeled nodes where every node has out-degree 1. A digraph where all out-degrees are 1 can be called a functional digraph due to the correspondence with endofunctions. - Andrew Howroyd, Feb 06 2024

			For n = 3 there are 3^2 = 9 rooted labeled trees on 3 nodes, namely (with o denoting a node, O the root node):
   o
   |
   o     o   o
   |      \ /
   O       O
The first can be labeled in 6 ways and contains nodes at heights 1 and 2 above the root, so contributes 6*(1+2) = 18 to the total; the second can be labeled in 3 ways and contains 2 nodes at height 1 above the root, so contributes 3*2=6 to the total, giving 24 in all. Dividing by 3 we get a(3) = 24/3 = 8.
For n = 4 there are 4^3 = 64 rooted labeled trees on 4 nodes, namely (with o denoting a node, O the root node):
   o
   |
   o     o        o   o
   |     |         \ /
   o     o   o      o     o o o
   |      \ /       |      \|/
   O       O        O       O
  (1)     (2)      (3)     (4)
Tree (1) can be labeled in 24 ways and contains nodes at heights 1, 2, 3 above the root, so contributes 24*(1+2+3) = 144 to the total;
tree (2) can be labeled in 24 ways and contains nodes at heights 1, 1, 2 above the root, so contributes 24*(1+1+2) = 96 to the total;
tree (3) can be labeled in 12 ways and contains nodes at heights 1, 2, 2 above the root, so contributes 12*(1+2+2) = 60 to the total;
tree (4) can be labeled in 4 ways and contains nodes at heights 1, 1, 1 above the root, so contributes 4*(1+1+1) = 12 to the total;
giving 312 in all. Dividing by 4 we get a(4) = 312/4 = 78.

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

Robert G. Wilson v, Table of n, a(n) for n = 1..1000 (first 100 terms from T. D. Noe)
Vijayakumar Ambat, Article in the Malayalam newspaper Ayala Manorama - Padhippura, 12 June 2015, that mentions the OEIS, and in particular this sequence.
V. I. Arnold, Topological classification of complex trigonometric polynomials and the combinatorics of graphs with the same number of edges and vertices, Functional Anal. Appl., 30 (1996), 1-17.
Shalosh B. Ekhad and Doron Zeilberger, Going Back to Neil Sloane's FIRST LOVE (OEIS Sequence A435): On the Total Heights in Rooted Labeled Trees, arXiv:1607.05776 [math.CO], 2016.
Shalosh B. Ekhad and Doron Zeilberger, Going Back to Neil Sloane's FIRST LOVE (OEIS Sequence A435): On the Total Heights in Rooted Labeled Trees, Version on DZ's home page with more links; Local copy, pdf file only, no active links
I. P. Goulden and D. M. Jackson, A proof of a conjecture for the number of ramified coverings of the sphere by the torus, arXiv:math/9902009 [math.AG], 1999.
I. P. Goulden, D. M. Jackson, and A. Vainshtein, The number of ramified coverings of the sphere by the torus and surfaces of higher genera, arXiv:math/9902125 [math.AG], 1999.
I. P. Goulden, D. M. Jackson, and A. Vainshtein, The number of ramified coverings of the sphere by the torus and surfaces of higher genera Ann. Comb. 4 (2000), no. 1, 27-46. (See Theorem 1.1.)
Brady Haran, The Number Collector (with Neil Sloane), Numberphile Podcast (2019)
Andrew Lohr and Doron Zeilberger, On the limiting distributions of the total height on families of trees, Integers (2018) 18, Article #A32.
T. Kyle Petersen, Exponential generating functions and Bell numbers, Inquiry-Based Enumerative Combinatorics (2019) Chapter 7, Undergraduate Texts in Mathematics, Springer, Cham, 98-99.
A. Rényi and G. Szekeres, On the height of trees, Journal of the Australian Mathematical Society 7.04 (1967): 497-507. See (4.7).
Marko Riedel et al., Connected endofunctions with no fixed points, Mathematics Stack Exchange, Dec 2014.
J. Riordan, Letter to N. J. A. Sloane, Aug. 1970
J. Riordan and N. J. A. Sloane, Enumeration of rooted trees by total height, J. Austral. Math. Soc., vol. 10 pp. 278-282, 1969.
N. J. A. Sloane, Page from 1964 notebook showing start of OEIS [includes A000027, A000217, A000292, A000332, A000389, A000579, A000110, A007318, A000058, A000215, A000289, A000324, A234953 (= A001854(n)/n), A000435, A000169, A000142, A000272, A000312, A000111]
N. J. A. Sloane, Cover of same notebook
N. J. A. Sloane, Lengths of Cycle Times in Random Neural Networks, Ph. D. Dissertation, Cornell University, February 1967; also Report No. 10, Cognitive Systems Research Program, Cornell University, 1967. This sequence appears on page 119.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
N. J. A. Sloane, Illustration of a(3) and a(4)
Yukun Yao and Doron Zeilberger, An Experimental Mathematics Approach to the Area Statistic of Parking Functions, arXiv:1806.02680 [math.CO], 2018.
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 3.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A001863, A001864, A001854, A002862 (unlabeled version), A234953, A259334.

Column k=1 of A350452.

A000435 := n-> (n-1)!*add (n^k/k!, k=0..n-2);
seq(simplify((n-1)*GAMMA(n-1,n)*exp(n)),n=1..20); # Vladeta Jovovic, Jul 21 2005

f[n_] := (n - 1)! Sum [n^k/k!, {k, 0, n - 2}]; Array[f, 18] (* Robert G. Wilson v, Aug 10 2010 *)
nx = 18; Rest[ Range[0, nx]! CoefficientList[ Series[ LambertW[-x] - Log[1 + LambertW[-x]], {x, 0, nx}], x]] (* Robert G. Wilson v, Apr 13 2013 *)

x='x+O('x^30); concat(0, Vec(serlaplace(lambertw(-x)-log(1+lambertw(-x))))) \\ Altug Alkan, Sep 05 2018

A000435(n)=(n-1)*A001863(n) \\ M. F. Hasler, Dec 10 2018

from math import comb
def A000435(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 # Chai Wah Wu, Apr 25-26 2023

a(n) = (n-1)! * Sum_{k=0..n-2} n^k/k!.
a(n) = A001864(n)/n.
E.g.f.: LambertW(-x) - log(1+LambertW(-x)). - Vladeta Jovovic, Apr 10 2001
a(n) = A001865(n) - n^(n-1).
a(n) = A001865(n) - A000169(n). - Geoffrey Critzer, Dec 13 2011
a(n) ~ sqrt(Pi/2)*n^(n-1/2). - Vaclav Kotesovec, Aug 07 2013
a(n)/A001854(n) ~ 1/2 [See Renyi-Szekeres, (4.7)]. Also a(n) = Sum_{k=0..n-1} k*A259334(n,k). - David desJardins, Jan 20 2017
a(n) = (n-1)*A001863(n). - M. F. Hasler, Dec 10 2018

Additional references from Valery A. Liskovets
Editorial changes by N. J. A. Sloane, Feb 03 2012
Edited by M. F. Hasler, Dec 10 2018

A069856 E.g.f.: exp(x)/(1+LambertW(x)).

Original entry on oeis.org

1, 0, 3, -17, 169, -2079, 31261, -554483, 11336753, -262517615, 6791005621, -194103134499, 6074821125385, -206616861429575, 7588549099814957, -299320105069298459, 12619329503201165281, -566312032570838608863, 26952678355224681891685

Offset: 0

Joe Keane (jgk(AT)jgk.org), May 03 2002

sign

Inverse binomial transform of A000312. - Tilman Neumann, Dec 13 2008

The |a(n)| is the number of functions f:{1,2,...,n}->{1,2,...,n} such that the digraph representation of f has no isolated vertices. - Geoffrey Critzer, Nov 13 2011

sci.math article 3CBC2B66.224E(AT)olympus.mons

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A086331.

Cf. A350212.

t = Sum[n^(n - 1) x^n/n!, {n, 1, 20}]; Range[0, 20]! CoefficientList[Series[Exp[-x]/(1 - t), {x, 0, 20}], x] (* Geoffrey Critzer, Nov 13 2011 *)
Range[0, 18]! CoefficientList[ Series[ Exp[x]/(1 + LambertW[x]), {x, 0, 18}], x] (* Robert G. Wilson v, Nov 28 2012 *)

my(x='x+O('x^20)); Vec(serlaplace(exp(x)/(1+lambertw(x)))) \\ G. C. Greubel, Jun 11 2017

a(n) = n! * Sum_{k=0..n} (-1)^k*k^k/(k!*(n - k)!).
E.g.f. for absolute value of {a(n)}: exp(C(x)-x) where C(x) is the e.g.f for A001865. - Geoffrey Critzer, Nov 13 2011, corrected by Vaclav Kotesovec, Nov 27 2012
abs(a(n)) ~ (exp(1)*n-1/2)/exp(1+exp(-1)) * n^(n-1). - Vaclav Kotesovec, Nov 27 2012
a(n) = (-1)^n * A350212(n,0). - Alois P. Heinz, Dec 19 2021

A029767 a(n) = (n-1)!*(2^n-1) for n>=1, a(0)=0.

Original entry on oeis.org

0, 1, 3, 14, 90, 744, 7560, 91440, 1285200, 20603520, 371226240, 7428153600, 163459296000, 3923502105600, 102017281766400, 2856571067750400, 85698439706880000, 2742370993410048000, 93240969463369728000, 3356681303055015936000, 127554011161191014400000

Offset: 0

N. J. A. Sloane

Labeled octopuses with n nodes.

a(n) is the number of connected endofunctions on n points such that every nonrecurrent element has at most one element in its preimage and every recurrent element has at most two elements in its preimage. - Geoffrey Critzer, Dec 07 2011

François Bergeron, Gilbert Labelle, and Pierre Leroux, Combinatorial Species and Tree-Like Structures, Cambridge University Press, 1998, pp. 12, 55, 409.
Richard P. Stanley, Enumerative Combinatorics, Cambridge University Press, Vol. 2, 1999; see Example 5.1.5.

G. C. Greubel, Table of n, a(n) for n = 0..400
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 498.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 777.

Cf. A001865.

Concatenation([0],List([1..20],n->Factorial(n-1)*(2^n-1))); # Muniru A Asiru, Aug 09 2018

[0] cat [Factorial(n-1)*(2^n-1): n in [1..20]]; // Vincenzo Librandi, Apr 18 2015

with(combinat): seq(stirling1(j,1)*stirling2(j+1,2)*(-1)^(j+1), j=0..16); # Zerinvary Lajos, Mar 30 2007

a=x/(1-x); Range[0,20]! CoefficientList[Series[Log[1/(1-a)], {x,0,20}], x]  (* Geoffrey Critzer, Dec 07 2011 *)
Join[{0}, Table[(n - 1)! (2^n - 1), {n, 20}]] (* Vincenzo Librandi, Apr 18 2015 *)

concat([0], for(n=1,25, print1((n-1)!*(2^n -1), ", "))) \\ G. C. Greubel, Jan 19 2017

E.g.f.: log(1-x)-log(1-2*x).
From Karol A. Penson, Oct 15 2002: (Start)
Representation as an infinite sum: a(n) = (1/2)*Sum_{k>=0} (n+k)!/((k+1)!*2^k), n >= 1.
Representation as n-th moment of a positive function on a positive half-axis: a(n) = Integral_{x=0..oo} x^n*(1/2)*exp(-x)/x*(2*exp(1/2*x)-2), n >= 1. (End)
D-finite with recurrence: a(n) +3*(-n+1)*a(n-1) +2*(n-1)*(n-2)*a(n-2) = 0. - R. J. Mathar, Jan 08 2013
a(n) = n!*Sum_{k=0..n-1} binomial(n-1,k)/(k+1). - J. M. Bergot, Jul 30 2015
a(n) = (1/zeta(n)) * Integral_{x=0..1} (log(1/x))^(n-1) / (sqrt(x) * (1-x)) dx. - Amrik Singh Nimbran, May 06 2018
a(n) = polygamma(n-1, 1/2) / ((-1)^n*zeta(n)) for n >= 2. - Amiram Eldar, Aug 08 2025

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

Original entry on oeis.org

0, 1, 1, 5, 34, 329, 4056, 60997, 1082320, 22137201, 512801920, 13269953861, 379400765184, 11877265764025, 404067857880064, 14843708906336325, 585606019079612416, 24693567694861202273, 1108343071153648926720, 52757597474618636748421, 2654611611461360017408000

Offset: 0

Vladeta Jovovic, Oct 17 2007

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

Cf. A001865 (Gamma(n, n)/exp(-n)).

Cf. A000272, A000435, A277458, A292977.

a:= function(n)
    if n=0 then return 0;
    else return Factorial(n)*Sum([1..n], k-> (-1)^(k+1)*n^(n-k-1)/Factorial(n-k));
    fi;
  end;
List([0..25], n-> a(n) ); # G. C. Greubel, Aug 02 2019

a:= func< n | n eq 0 select 0 else Factorial(n)*(&+[(-1)^(k+1)*n^(n-k-1)/Factorial(n-k): k in [1..n]]) >;
[a(n): n in [0..25]]; // G. C. Greubel, Aug 02 2019

Table[n!*Sum[(-1)^(k+1)*n^(n-k-1)/(n-k)!, {k,n}], {n,0,25}] (* Stefan Steinerberger, Oct 19 2007 *)
With[{m=25}, CoefficientList[Series[Log[1-LambertW[-x]], {x,0,m}], x]*Range[0,m]!] (* G. C. Greubel, Aug 02 2019 *)

my(x='x+O('x^25)); concat([0], Vec(serlaplace( log(1-lambertw(-x)) ))) \\ G. C. Greubel, Aug 02 2019

def a(n):
    if (n==0): return 0
    else: return factorial(n)*sum((-1)^(k+1)*n^(n-k-1)/factorial(n-k) for k in (1..n))
[a(n) for n in (0..25)] # G. C. Greubel, Aug 02 2019

E.g.f.: log(1-LambertW(-x)).
a(n) ~ n^(n-1)/2. - Vaclav Kotesovec, Sep 25 2013
Conjecture: a(n) = (n-1)!*( Sum_{k >= 0} (-1)^k * n^(n+k)/(n+k)! - (-1/e)^n ) for n >= 1. Cf. A000435. - Peter Bala, Jul 23 2021
From Thomas Scheuerle, Nov 17 2023: (Start)
This conjecture is true. Let "gamma" be the lower incomplete gamma function: gamma(n, x) = (n-1)! (1 - exp(-x)*Sum_{k = 0..n-1} x^k/k! ), then we can get the upper incomplete gamma function Gamma(n, x) = gamma(n, oo) - gamma(n, x). By inserting according the formula below, we will obtain the formula from Peter Bala.
a(n) = (-1)^(n+1)*Gamma(n, -n)/exp(n) = (-1)^(n+1)*A292977(n-1, n), for n > 0, where Gamma is the upper incomplete gamma function. (End)

More terms from Stefan Steinerberger, Oct 19 2007

A277489 Expansion of e.g.f. -LambertW(-log(1+x)).

Original entry on oeis.org

0, 1, 1, 5, 26, 224, 2244, 28496, 417976, 7122384, 136770960, 2937770472, 69626588976, 1806936836184, 50936933449752, 1550292926398680, 50661309325357824, 1769286989373994752, 65762170385201959680, 2591979585702305271552, 107982615297265761991680

Offset: 0

Vaclav Kotesovec, Oct 17 2016

nonn

G. C. Greubel, Table of n, a(n) for n = 0..395
Index entries for reversions of series

Cf. A001865, A052807, A133297.

Cf. A357337, A357338.

CoefficientList[Series[-LambertW[-Log[1+x]], {x, 0, 20}], x] * Range[0, 20]!
Table[Sum[StirlingS1[n, k]*k^(k-1), {k, 1, n}], {n, 0, 20}]

my(x='x+O('x^50)); concat([0], Vec(serlaplace(-lambertw(-log(1+x))))) \\ G. C. Greubel, Jun 21 2017

a(n) = Sum_{k=1..n} Stirling1(n, k)*k^(k-1).
a(n) ~ (exp(exp(-1))-1)^(1/2-n) * exp(-exp(-1)/2+1/2-n) * n^(n-1).
E.g.f.: Series_Reversion( exp(x * exp(-x)) - 1 ). - Seiichi Manyama, Sep 10 2024

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

A350078 Irregular triangle read by rows: T(n,k) is the number of endofunctions on [n] whose second-largest component has size exactly k; n >= 0, 0 <= k <= floor(n/2).

Original entry on oeis.org

1, 1, 3, 1, 17, 10, 142, 87, 27, 1569, 911, 645, 21576, 11930, 10260, 2890, 355081, 189610, 174132, 104720, 6805296, 3543617, 3229275, 2493288, 705740, 148869153, 76060087, 67843521, 60223520, 34424208, 3660215680, 1842497914, 1605373560, 1530575960, 1051155000, 310181886

Offset: 0

Steven Finch, Dec 12 2021

An endofunction on [n] is a function from {1,2,...,n} to {1,2,...,n}.

If the mapping has no second component, then its second-largest component is defined to have size 0.

			Triangle begins:
       1;
       1;
       3,      1;
      17,     10;
     142,     87,     27;
    1569,    911,    645;
   21576,  11930,  10260,   2890;
  355081, 189610, 174132, 104720;
  ...

Alois P. Heinz, Rows n = 0..140, flattened
Steven Finch, Second best, Third worst, Fourth in line, arxiv:2202.07621 [math.CO], 2022.

Column 0 gives gives 1 together with A001865.
Row sums give A000312.
Cf. A001865, A350079, A350080, A350081, A350275, A350276.

g:= proc(n) option remember; add(n^(n-j)*(n-1)!/(n-j)!, j=1..n) end:
b:= proc(n, l) option remember; `if`(n=0, x^l[1], add(g(i)*
      b(n-i, sort([l[], i])[-2..-1])*binomial(n-1, i-1), i=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, [0$2])):
seq(T(n), n=0..10);  # Alois P. Heinz, Dec 17 2021

g[n_] := g[n] = Sum[n^(n - j)*(n - 1)!/(n - j)!, {j, 1, n}];
b[n_, l_] := g[n, l] = If[n == 0, x^l[[1]], Sum[g[i]*b[n - i, Sort[ Append[l, i]][[-2 ;; -1]]]*Binomial[n - 1, i - 1], {i, 1, n}]];
T[n_] := With[{p = b[n, {0, 0}]}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Dec 28 2021, after Alois P. Heinz *)

More terms (three rows) from Alois P. Heinz, Dec 15 2021

cp's OEIS Frontend

A063169 a(n) = n*A001865(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Python

UBASIC

Formula

A053506 a(n) = (n-1)*n^(n-2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

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

A000435 Normalized total height of all nodes in all rooted trees with n labeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A069856 E.g.f.: exp(x)/(1+LambertW(x)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A029767 a(n) = (n-1)!*(2^n-1) for n>=1, a(0)=0.

Views

Author

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