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.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 37
L. Katz, Probability of indecomposability of a random mapping function, Ann. Math. Statist. 26, (1955), 512-517.
J. 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.
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
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
More terms from James A. Sellers, May 23 2000
STATUS
approved