login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001865 Number of connected functions on n labeled nodes.
(Formerly M3040 N1232)
18
1, 3, 17, 142, 1569, 21576, 355081, 6805296, 148869153, 3660215680, 99920609601, 2998836525312, 98139640241473, 3478081490967552, 132705415800984825, 5423640496274200576, 236389784118231290049, 10944997108429625524224 (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

L. Katz, Probability of indecomposability of a random mapping function. Ann. Math. Statist. 26, (1955), 512-517.

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

F. Schmidt and R. Simion, Card shuffling and a transformation on S_n, Aequationes Math. 44 (1992), no. 1, 11-34.

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

T. D. Noe and 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, 2013

Christian Brouder, William J. Keith, Ângela Mestre, Closed forms for a multigraph enumeration, arXiv preprint arXiv:1301.0874, 2013.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 37

Bernd Sturmfels, Ngoc Mai Tran, COMBINATORIAL TYPES OF TROPICAL EIGENVECTORS, Arxiv preprint arXiv:1105.5504, 2011.

FORMULA

Sum n! n^(n-k-1) / (n-k)!, k = 1 . . n.

E.g.f.: -ln(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 incomplete Gamma function: a(n)=exp(n+1)*Integral_{x=n+1..infinity} 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..infinity} (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

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

CROSSREFS

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

Sequence in context: A136727 A062873 A120022 * A189001 A087885 A178685

Adjacent sequences:  A001862 A001863 A001864 * A001866 A001867 A001868

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane.

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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified September 20 11:51 EDT 2014. Contains 246995 sequences.