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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

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

References

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

Links

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

Crossrefs

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

Column k=1 of A060281.

Programs

Maple

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

Mathematica

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

PARI

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

PARI

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

PARI

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

Python

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

Formula

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

Extensions

More terms from James Sellers, May 23 2000