|
%I M1946 N0771
%S 1,2,9,64,625,7776,117649,2097152,43046721,1000000000,25937424601,
%T 743008370688,23298085122481,793714773254144,29192926025390625,
%U 1152921504606846976,48661191875666868481,2185911559738696531968,104127350297911241532841,5242880000000000000000000
%N Number of labeled rooted trees with n nodes: n^(n-1).
%C Also the number of connected transitive subtree acyclic digraphs on n vertices. - Robert Castelo (rcastelo(AT)imim.es), Jan 06 2001
%C For any given integer k a(n) is also is the number of functions from {1,2,...,n} to {1,2,...,n} such that the sum of the function values is k mod n. - Sharon Sela (sharonsela(AT)hotmail.com), Feb 16 2002
%C The n-th term of a geometric progression with first term 1 and common ratio n: a(1) = 1 -> 1,1,1,1,... a(2) = 2 -> 1,2,... a(3) = 9 -> 1,3,9,... a(4) = 64 -> 1,4,16,64,... - Amarnath Murthy (amarnath_murthy(AT)yahoo.com), Mar 25 2004
%C All rational solutions to the equation x^y = y^x, with x < y, are given by x = A000169(n+1)/A000312(n), y = A000312(n+1)/A007778(n), where n = 1, 2, 3, ... . - Nick Hobson Nov 30 2006
%C a(n+1) is also the number of partial functions on n labeled objects. - Franklin T. Adams-Watters, Dec 25 2006
%C In other words, if A is a finite set of size n-1, then a(n) is the number of binary relations on A that are also functions. Note that a(n) = sum(binomial(n-1,k)*(n-1)^k, k=0..n-1)=n^(n-1), where binomial(n-1,k) is the number of ways to select a domain D of size k from A and (n-1)^k is the number of functions from D to A. [_Dennis P. Walsh_, April 21 2011]
%C More generally, consider the class of sequences of the form a(n)=[n*c(1)*...*c(i)]^(n-1). This sequence has c(1)=1. A052746 has a(n) = [2*n]^(n-1), A052756 has a(n)=[3*n]^(n-1),A052764 has a(n)=[4*n]^(n-1), A052789 has a(n)=[5*n]^(n-1). These sequences have a combinatorial structure like simple grammars. - Ctibor O. ZIZKA, Feb 23 2008
%C a(n) is equal to the logarithmic transform of the sequence b(n) = n^(n-2) starting at b(2). [From Kevin Hu (10thsymphony(AT)gmail.com), Aug 23 2010]
%C Also, number of labeled connected multigraphs of order n without cycles except one loop. See link below to have a picture showing the bijection between rooted trees and multigraphs of this kind. (Note that there are no labels in the picture, but the bijection remains true if we label the nodes.) [From W. Bomfim, Sep 04 2010]
%C a(n) is also the number of functions f:{1,2,...,n} -> {1,2,...,n} such that f(1) = 1.
%C For a signed version of A000169 arising from the Vandermonde determinant of (1,1/2,...,1/n), see the Mathematica section. [_Clark Kimberling_, Jan 02 2012]
%C Numerator of (1+1/(n-1))^(n-1) for n>1 - _Jean-François Alcover_, Jan 14 2013
%C Right edge of triangle A075513. - _Michel Marcus_, May 17 2013
%D Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8.- From _N. J. A. Sloane_, Oct 08 2012
%D P. J. Cameron and P. Cara, Independent generating sets and geometries for symmetric groups, J. Algebra, Vol. 258, no. 2 (2002), 641-650.
%D R. Castelo and A. Siebes, A characterization of moral transitive acyclic directed graph Markov models as labeled trees, J. Statist. Planning Inference, 115(1):235-259, 2003.
%D J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 524.
%D Hannes Heikinheimo, Heikki Mannila and Jouni K. Seppnen, Finding Trees from Unordered 01 Data, in Knowledge Discovery in Databases: PKDD 2006, Lecture Notes in Computer Science, Volume 4213/2006, Springer-Verlag. [From _N. J. A. Sloane_, Jul 09 2009]
%D Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 63.
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 128.
%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).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see page 25, Prop. 5.3.2.
%H N. J. A. Sloane, <a href="/A000169/b000169.txt">Table of n, a(n) for n = 1..100</a>
%H W. Bomfim, <a href="http://en.wikipedia.org/wiki/File:Bijecao.gif">Bijection between rooted forests and multigraphs without cycles except one loop in each connected component.</a> [From W. Bomfim, Sep 04 2010]
%H David Callan, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">A Combinatorial Derivation of the Number of Labeled Forests</a>, J. Integer Seqs., Vol. 6, 2003.
%H R. Castelo and A. Siebes, <a href="http://ftp.cs.uu.nl:/pub/RUU/CS/techreps/CS-2000/2000-44.ps.gz">A characterization of moral transitive directed acyclic graph Markov models as trees</a>, Technical Report CS-2000-44, Faculty of Computer Science, University of Utrecht.
%H N. Hobson, <a href="http://www.qbyte.org/puzzles/p048s.html">Exponential equation</a>.
%H INRIA Algorithms Project, <a href="http://algo.inria.fr/ecs/ecs?searchType=1&service=Search&searchTerms=67">Encyclopedia of Combinatorial Structures 67</a>
%H F. Ruskey, <a href="http://www.theory.cs.uvic.ca/~cos/inf/tree/RootedTree.html">Information on Rooted Trees</a>
%H N. J. A. Sloane, <a href="/A000081/a000081.html">Illustration of initial terms</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphVertex.html">Graph Vertex</a>
%H D. Zvonkine, <a href="http://www.arXiv.org/abs/math.AG/0403092">An algebra of power series...</a>
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F The e.g.f. T(x) = Sum_{n=1..infinity} n^(n-1)*x^n/n! satisfies T(x) = x*exp(T(x)), so T(x) is the functional inverse (series reversion) of x*exp(-x).
%F Also T(x) = -LambertW(-x) where W(x) is the principal branch of Lambert's function.
%F T(x) is sometimes called Euler's tree function.
%F a(n) = A000312(n-1)*A128434(n,1)/A128433(n,1). - _Reinhard Zumkeller_, Mar 03 2007
%F E.g.f.: LambertW(x)=x*G(0) ; G(k)= 1 - x*((2*k+2)^(2*k))/(((2*k+1)^(2*k)) - x*((2*k+1)^(2*k))*((2*k+3)^(2*k+1))/(x*((2*k+3)^(2*k+1)) - ((2*k+2)^(2*k+1))/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Dec 30 2011
%e For n=3, a(3)=9 because there are exactly 9 binary relations on A={1, 2} that are functions, namely: {}, {(1,1)}, {(1,2)}, {(2,1)}, {(2,2)}, {(1,1),(2,1)}, {(1,1),(2,2)}, {(1,2),(2,1)} and {(1,2),(2,2)}. [From Dennis P. Walsh, April 21 2011]
%e x + 2*x^2 + 9*x^3 + 64*x^4 + 625*x^5 + 7776*x^6 + 117649*x^7 + ...
%p A000169 := n-> n^(n-1);
%p spec := [A, {A=Prod(Z,Set(A))}, labeled]; [seq(combstruct[count](spec,size=n), n=1..20)];
%p Contribution from Thomas Wieder, Feb 07 2010: (Start)
%p for n to 7 do ST := [seq(seq(i, j = 1 .. n), i = 1 .. n)]; PST := powerset(ST);
%p Result[n] := nops(PST) end do; seq(Result[n], n = 1 .. 7); (End)
%t Table[n^(n - 1), {n, 1, 20}] - Stefan Steinerberger, Apr 01 2006
%t Range[0, 18]! CoefficientList[ Series[ Exp[ Log[1 - LambertW[-x]]], {x, 0, 18}], x] (* _Robert G. Wilson v_ *)
%t (* Next, a signed version A000169 from the Vandermonde determinant of (1,1/2,...,1/n) *)
%t f[j_] := 1/j; z = 12;
%t v[n_] := Product[Product[f[k] - f[j], {j, 1, k - 1}], {k, 2, n}]
%t Table[v[n], {n, 1, z}]
%t 1/% (* A203421 *)
%t Table[v[n]/v[n + 1], {n, 1, z - 1}] (* A000169 signed *)
%t (* _Clark Kimberling_, Jan 02 2012 *)
%o (PARI) {a(n) = if( n<1, 0, n^(n-1))}
%o (Mupad) n^(n-1) $ n=1..20 - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 01 2007
%o (PARI) /* Computation via e.g.f. by series reversion of x*exp(-x): */
%o N=66; x='x+O('x^N);
%o egf=serreverse(x*exp(-x));
%o Vec(serlaplace(egf))
%o /* _Joerg Arndt_, May 25 2011 */
%Y Cf. A000055, A000081, A000272, A000312, A007778, A007830, A008785-A008791, A055860.
%Y See also A053506-A053509.
%Y Cf. A002061.
%Y Cf. A052746, A052756, A052764, A052789.
%K easy,core,nonn,nice,changed
%O 1,2
%A _N. J. A. Sloane_.
|
