A001865 - OEIS

%I M3040 N1232 #129 Dec 27 2024 03:49:19

%S 1,3,17,142,1569,21576,355081,6805296,148869153,3660215680,

%T 99920609601,2998836525312,98139640241473,3478081490967552,

%U 132705415800984825,5423640496274200576,236389784118231290049,10944997108429625524224,536484538620663729658993

%N Number of connected functions on n labeled nodes.

%C 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

%C 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 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 1, p. 112.

%D Ulrike Sattler, Decidable classes of formal power series with nice closure properties, Diplomarbeit im Fach Informatik, Univ. Erlangen - Nuernberg, Jul 27 1994

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A001865/b001865.txt">Table of n, a(n) for n = 1..380</a> (first 50 terms from T. D. Noe)

%H H. Bergeron, E. M. F. Curado, J. P. Gazeau and L. M. C. S. Rodrigues, <a href="http://arxiv.org/abs/1309.6910">A note about combinatorial sequences and Incomplete Gamma function</a>, arXiv preprint arXiv: 1309.6910 [math.CO], 2013.

%H Christian Brouder, William J. Keith, and Ângela Mestre, <a href="http://arxiv.org/abs/1301.0874">Closed forms for a multigraph enumeration</a>, arXiv preprint arXiv:1301.0874 [math.CO], 2013.

%H Camille Combe, <a href="https://arxiv.org/abs/2007.00048">A geometric and combinatorial exploration of Hochschild lattices</a>, arXiv:2007.00048 [math.CO], 2020. See p. 22.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=37">Encyclopedia of Combinatorial Structures 37</a>

%H L. Katz, <a href="http://dx.doi.org/10.1214/aoms/1177728496">Probability of indecomposability of a random mapping function</a>, Ann. Math. Statist. 26, (1955), 512-517.

%H J. Riordan, <a href="/A001863/a001863.pdf">Letter to N. J. A. Sloane, Aug. 1970</a>

%H Frank Schmidt and Rodica Simion, <a href="http://dx.doi.org/10.1007/BF01834201">Card shuffling and a transformation on S_n</a>, Aequationes Math. 44 (1992), no. 1, 11-34.

%H Bernd Sturmfels and Ngoc Mai Tran, <a href="http://arxiv.org/abs/1105.5504">Combinatorial Types of Tropical Eigenvectors</a>, arXiv:1105.5504 [math.CO], 2011-2012.

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

%F E.g.f.: -log(1+LambertW(-x)). - _Vladeta Jovovic_, Apr 11 2001

%F E.g.f. satisfies 0=2y'^4+2y''^2-y'''y'-y''y'^2. - _Michael Somos_, Aug 23 2003

%F 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.

%F Asymptotics: sqrt(Pi*n/2)*n^(n-1). - _N-E. Fahssi_, Jan 25 2008, corrected by _Vaclav Kotesovec_, Nov 27 2012

%F a(n) = exp(1)*Integral_{x=1..oo} (n+x)^n*exp(-x) dx. - _Gerald McGarvey_, Apr 16 2008

%F a(n) = (1/n) * Sum_{k=1..n} C(n,k) * (n-k)^(n-k) * k^k. - _Paul D. Hanna_, Jul 04 2013

%F From _Peter Bala_, Jun 29 2016: (Start)

%F 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)! ).

%F 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)

%F a(n) = Sum_{k=1..n} (n!/(n-k)!) * k^2 * n^(n-k-2). - _Brian P Hawkins_, Feb 07 2024

%p spec := [B, {A=Prod(Z,Set(A)), B=Cycle(A)}, labeled]; [seq(combstruct[count](spec,size=n), n=0..20)];

%p seq(simplify(GAMMA(n,n)*exp(n)),n=1..20); # _Vladeta Jovovic_, Jul 21 2005

%t t=Sum[n^(n-1)x^n/n!,{n,1,20}];

%t Range[0,20]! CoefficientList[Series[Log[1/(1-t)]+1,{x,0,20}],x] (* _Geoffrey Critzer_, Mar 12 2011 *)

%t f[n_] := Sum[n! n^(n - k - 1)/(n - k)!, {k, n}]; Array[f, 18] (* _Robert G. Wilson v_ *)

%t a[n_] := Exp[n]*Gamma[n, n]; Table[a[n] // FunctionExpand, {n, 1, 18}] (* _Jean-François Alcover_, May 13 2013, after _Vladeta Jovovic_ *)

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

%o (PARI) a(n)=(1/n)*sum(k=1,n,binomial(n,k)*(n-k)^(n-k)*k^k) \\ _Paul D. Hanna_, Jul 04 2013

%o (PARI) N=20; x='x+O('x^N); Vec(serlaplace(log(sum(k=0, N, (k*x)^k/k!)))) \\ _Seiichi Manyama_, May 27 2019

%o (Python)

%o from math import comb

%o 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

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

%Y Column k=1 of A060281.

%K nonn,easy,nice

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _James A. Sellers_, May 23 2000