login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001865 Number of connected functions on n labeled nodes.
(Formerly M3040 N1232)
39
1, 3, 17, 142, 1569, 21576, 355081, 6805296, 148869153, 3660215680, 99920609601, 2998836525312, 98139640241473, 3478081490967552, 132705415800984825, 5423640496274200576, 236389784118231290049, 10944997108429625524224, 536484538620663729658993 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
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.
Camille Combe, A geometric and combinatorial exploration of Hochschild lattices, arXiv:2007.00048 [math.CO], 2020. See p. 22.
L. Katz, Probability of indecomposability of a random mapping function, Ann. Math. Statist. 26, (1955), 512-517.
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.
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
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 *)
PROG
(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
CROSSREFS
a(n) = A000435(n) + n^(n-1). See also A063169.
Column k=1 of A060281.
Sequence in context: A322137 A062873 A120022 * A189001 A087885 A178685
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
More terms from James A. Sellers, May 23 2000
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 07:18 EDT 2024. Contains 370954 sequences. (Running on oeis4.)