|
|
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
|
|
|
FORMULA
|
a(n) = Sum_{k=1..n} n!*n^(n-k-1) / (n-k)!.
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.
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
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)];
|
|
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 *)
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|