The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)

## Using the Email Server

• If the Internet is slow, or if you are using a device that can send electronic mail but cannot access the Internet, it is possible to consult the OEIS via email.
• Simply send an email message to sequences@oeis.org saying (for example):

```lookup 1 3 16 125 1296 16807 262144
lookup 1 2 5 14 42 132 429 1430 4862
```

• The entries should be separated by spaces rather than commas.
The "Subject" line should say "None" or be left blank.
Sending an empty message will produce the "Help" file, which has more information about the things you can do.
• The reply normally comes back almost at once.
• Here for example is the response to the first of the two requests above. (Of course exactly how this appears will depend on the mail program that you are using.)

```From sequences-reply@oeis.org Wed Sep 28 12:49:39 2011
Date: Wed, 28 Sep 2011 12:49:22 -0400
To: njasloane@gmail.com
Subject: Reply from On-Line Encyclopedia of Integer Sequences

# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: seq:1,3,16,125,1296,16807,262144
Showing 1-1 of 1

%I A000272 M3027 N1227
%S A000272 1,1,1,3,16,125,1296,16807,262144,4782969,100000000,2357947691,
%T A000272 61917364224,1792160394037,56693912375296,1946195068359375,
%U A000272 72057594037927936,2862423051509815793,121439531096594251776,5480386857784802185939
%N A000272 Number of trees on n labeled nodes: n^(n-2).
%C A000272 Number of spanning trees in complete graph K_n on n labeled nodes.
%C A000272 Robert Castelo (rcastelo(AT)imim.es), Jan 06 2001, observes that n^(n-2) is also the number of transitive subtree acyclic digraphs on n-1 vertices.
%C A000272 a(n) is also the number of ways of expressing an n-cycle in the symmetric group S_n as a product of n-1 transpositions, see example. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 12 2001
%C A000272 Also counts parking functions, noncrossing partitions, critical configurations of the chip firing game, allowable pairs sorted by a priority queue [Hamel].
%C A000272 a(n+1) = sum( i * n^(n-1-i) * binomial(n, i), i=1..n) - Yong Kong (ykong(AT)curagen.com), Dec 28 2000
%C A000272 a(n+1) = number of endofunctions with no cycles of length > 1; number of forests of rooted labeled trees on n vertices. - Mitch Harris (Harris.Mitchell(AT)mgh.harvard.edu), Jul 06 2006
%C A000272 a(n) is also the number of nilpotent partial bijections (of an n-element set). Equivalently, the number of nilpotents in the partial symmetric semigroup, P sub n. [From A. Umar (aumarh(AT)squ.edu.om), Aug 25 2008]
%C A000272 a(n) is also the number of edge-labeled rooted trees on n nodes. [From Nikos Apostolakis (nikos.ap(AT)gmail.com), Nov 30 2008]
%C A000272 a(n+1) is the number of length n sequences on an alphabet of {1,2,...,n} that have a partial sum equal to n. For example a(4)=16 because there are 16 length 3 sequences on {1,2,3} in which the terms (beginning with the first term and proceeding sequentialy) sum to 3 at some point in the sequence. {1, 1, 1}, {1, 2, 1}, {1, 2, 2}, {1, 2, 3}, {2, 1, 1}, {2, 1, 2}, {2, 1, 3}, {3, 1, 1}, {3, 1, 2}, {3, 1, 3}, {3, 2, 1}, {3, 2, 2}, {3, 2, 3}, {3, 3, 1}, {3, 3, 2}, {3, 3, 3}} [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), Jul 20 2009]
%C A000272 a(3) = 3 is the only prime value in the sequence. There are no semiprime values. Generally, the number of distinct primes dividing a(n) = omega(a(n)) = A001221(a(n)) = omega(n). Similarly, the number of prime divisors of a(n) (counted with multiplicity) = bigomega(a(n)) = A001222(a(n)) = Product (p_j^k_j) = Sum (k_j) where a(n) = Product (p_j^k_j), which is an obvious function of n and n-2. [From Jonathan Vos Post (jvospost3(AT)gmail.com), May 27 2010]
%C A000272 a(n) is the number of acyclic functions from {1,2,...,n-1} to {1,2,...,n}. An acyclic function f satisfies the following property: for any x in the domain, there exists a positive integer k  such that (f^k)(x) is not in the domain. Note that f^k denotes the k-fold composition of f with itself, e.g., (f^2)(x)=f(f(x)). [From Dennis Walsh, March 2 2011]
%D A000272 M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 1999; see p. 142.
%D A000272 M. D. Atkinson and R. Beals, Priority queues and permutations, SIAM J. Comput. 23 (1994), 1225-1230.
%D A000272 N. L. Biggs, Chip-firing and the critical group of a graph, J. Algeb. Combin., 9 (1999), 25-45.
%D A000272 N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 51.
%D A000272 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 A000272 J. Denes, The representation of a permutation as the product of a minimal number of transpositions ..., Pub. Math. Inst. Hung. Acad. Sci., 4 (1959), 63-70.
%D A000272 J. Gilbey and L. Kalikow, Parking functions, valet functions and priority queues, Discrete Math., 197 (1999), 351-375.
%D A000272 M. Golin and S. Zaks, Labeled trees and pairs of input-output permutations in priority queues, Theoret. Comput. Sci., 205 (1998), 99-114.
%D A000272 I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, ex. 3.3.33.
%D A000272 I. P. Goulden and S. Pepper, Labeled trees and factorizations of a cycle into transpositions, Discrete Math., 113 (1993), 263-268.
%D A000272 I. P. Goulden and A. Yong, Tree-like properties of cycle factorizations, J. Combin. Theory, A 98 (2002), 106-117.
%D A000272 J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 524.
%D A000272 A. M. Hamel, Priority queue sorting and labeled trees, Annals Combin., 7 (2003), 49-54.
%D A000272 D. M. Jackson - Some Combinatorial Problems Associated with Products of Conjugacy Classes of the Symmetric Group, Journal of Combinatorial Theory, Seies A, 49 363-369(1988).
%D A000272 S. Janson, D. E. Knuth, T. Luczak and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.
%D A000272 L. Kalikow, Symmetries in trees and parking functions, Discrete Math., 256 (2002), 719-741.
%D A000272 Laradji, A. and Umar, A. On the number of nilpotents in the partial symmetric semigroup, Comm. Algebra 32 (2004), 3017-3023. [From A. Umar (aumarh(AT)squ.edu.om), Aug 25 2008]
%D A000272 J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge Univ. Press, 1992.
%D A000272 G. Martens, On Algebraic Solutions of Polynomial Equations of Degree n in one Variable, GH Consulting EPI-01-06 preprint, 2006
%D A000272 F. McMorris and F. Harary (1992), Subtree acyclic digraphs, Ars Comb., vol. 34.
%D A000272 A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992, Eq. (4.2.2.37)
%D A000272 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 128.
%D A000272 M. P. Schutenberger, On an Enumeration Problem, Journal of Combinatorial Theory 4, 219-221 (1968). [A 1-1 correspondence between maps under permutations and acyclics maps.]
%D A000272 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000272 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A000272 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see page 25, Prop. 5.3.2.
%D A000272 R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 55-68.
%D A000272 Zvonkine, D., An algebra of power series arising in the intersection theory of moduli spaces of curves and in the enumeration of ramified coverings of the sphere. Preprint 2004.
%H A000272 N. J. A. Sloane, Table of n, a(n) for n = 0..100
%H A000272 David Callan, A Combinatorial Derivation of the Number of Labeled Forests, J. Integer Seqs., Vol. 6, 2003.
%H A000272 Saverio Caminiti and Emanuele G. Fusco, On the Number of Labeled k-arch Graphs, Journal of Integer Sequences, Vol 10 (2007), Article 07.7.5
%H A000272 Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions.
%H A000272 R. Castelo and A. Siebes, A characterization of moral transitive directed acyclic graph ..., Report CS-2000-44, Department of Computer Science, Univ. Utrecht.
%H A000272 S. Coulomb and M. Bauer, On vertex covers, matchings and random trees
%H A000272 INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 78
%H A000272 C. Lamathe, The Number of Labeled k-Arch Graphs, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.1.
%H A000272 G. Martens, Polynomial Equations of Degree n.
%H A000272 J. Pitman, Coalescent Random Forests, J. Combin. Theory, A85 (1999), 165-193.
%H A000272 S. Ramanujan, Question 738, J. Ind. Math. Soc.
%H A000272 Eric Weisstein's World of Mathematics, Complete Graph
%H A000272 Eric Weisstein's World of Mathematics, Labeled Tree
%H A000272 Eric Weisstein's World of Mathematics, Spanning Tree
%H A000272 D. Zeilberger, The n^(n-2)-th Proof Of The Formula For The Number Of Labeled Trees
%H A000272 D. Zeilberger, Yet Another Proof For The Enumeration Of Labeled Trees
%H A000272 D. Zvonkine, An algebra of power series...
%H A000272 Index entries for sequences related to trees
%H A000272 Index entries for "core" sequences
%H A000272 Dennis Walsh, Notes on acyclic functions and their directed graphs
%F A000272 E.g.f.: T - (1/2)T^2; where T=T(x) is Euler's tree function (see A000169, also A001858). - Len Smiley (smiley(AT)math.uaa.alaska.edu), Nov 19 2001
%F A000272 E.g.f.: ((W(-x)/x)^2)/(1+W(-x)), W(x): Lambert's function (principal branch).
%F A000272 Number of labeled k-trees on n nodes is binomial(n, k) * (k(n-k)+1)^(n-k-2).
%F A000272 Determinant of the symmetric matrix H generated for a polynomial of degree n by: for(i=1,n-1, for(j=1,i, H[i,j]=(n*i^3-3*n*(n+1)*i^2/2+n*(3*n+1)*i/2+(n^4-n^2)/2)/6-(i^2-(2*n+1)*i+n*(n+1))*(j-1)*j/4; H[j,i]=H[i,j]; ); ); - Gerry Martens (GerryMrt(AT)aol.com), May 04 2007
%F A000272 For n>=1, a(n+1)= Sum(n^(n-i)*Binomial(n-1,i-1),i=1...n) [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), Jul 20 2009]
%F A000272 E.g.f. for b(n)=a(n+1): exp(-W(-x)), where W is Lambert's function satisfying W(x)exp(W(x))=x. Proof is contained in link "Notes on acyclic functions..." [From Dennis Walsh, March 2 2011]
%e A000272 a(7)=matdet([196, 175, 140, 98, 56, 21; 175, 160, 130, 92, 53, 20; 140, 130, 110, 80, 47, 18; 98, 92, 80, 62, 38, 15; 56, 53, 47, 38, 26, 11; 21, 20, 18, 15, 11, 6])=16807
%e A000272 a(3)=3 since there are 3 acyclic functions f:[2]->[3], namely, {(1,2),(2,3)}, {(1,3),(2,1)}, and {(1,3),(2,3)}.
%e A000272 The following products of 3 transpositions lead to a 4-cycle in S_4:
%e A000272 (1,2)*(1,3)*(1,4);
%e A000272 (1,2)*(1,4)*(3,4);
%e A000272 (1,2)*(3,4)*(1,3);
%e A000272 (1,3)*(1,4)*(2,3);
%e A000272 (1,3)*(2,3)*(1,4);
%e A000272 (1,4)*(2,3)*(2,4);
%e A000272 (1,4)*(2,4)*(3,4);
%e A000272 (1,4)*(3,4)*(2,3);
%e A000272 (2,3)*(1,2)*(1,4);
%e A000272 (2,3)*(1,4)*(2,4);
%e A000272 (2,3)*(2,4)*(1,2);
%e A000272 (2,4)*(1,2)*(3,4);
%e A000272 (2,4)*(3,4)*(1,2);
%e A000272 (3,4)*(1,2)*(1,3);
%e A000272 (3,4)*(1,3)*(2,3);
%e A000272 (3,4)*(2,3)*(1,2).  [Joerg Arndt and Greg Stevenson, Jul 11 2011]
%p A000272 A000272 := n->n^(n-2); [ seq(n^(n-2), n=1..20) ];
%p A000272 Contribution from Thomas Wieder (thomas.wieder(AT)t-online.de), Feb 07 2010: (Start)
%p A000272 for n to 7 do ST := [seq(seq(i, j = 1 .. n+1), i = 1 .. n)]; PST := powerset(ST);
%p A000272 Result[n] := nops(PST) end do; seq(Result[n], n = 1 .. 7) (End)
%t A000272 << DiscreteMath`Combinatorica` Table[NumberOfSpanningTrees[CompleteGraph[n]], {n, 1, 20}] - Artur Jasinski (grafix(AT)csl.pl), Dec 06 2007
%o A000272 (PARI) a(n)=if(n<1,0,n^(n-2))
%o A000272 (MAGMA) [ n^(n-2) : n in [1..10]]; - from Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006
%o A000272 (PARI) /* GP Function for Determinant of Hermitian (square symmetric) matrix for univariate polynomial of degree n by G. Martens: */
%o A000272 Hn(n=2)= {local(H=matrix(n-1,n-1),i,j); for(i=1,n-1, for(j=1,i, H[i,j]=(n*i^3-3*n*(n+1)*i^2/2+n*(3*n+1)*i/2+(n^4-n^2)/2)/6-(i^2-(2*n+1)*i+n*(n+1))*(j-1)*j/4; H[j,i]=H[i,j]; ); ); print("a(",n,")=matdet(",H,")"); print("Determinant H =",matdet(H)); return(matdet(H)); } { print(Hn(7)); } /* Gerry Martens (GerryMrt(AT)aol.com), May 04 2007 */
%Y A000272 Cf. A000055, A000169, A000312, A007778, A007830, A008785-A008791. a(n)= A033842(n-1, 0) (first column of triangle).
%Y A000272 Cf. A000272 (labeled trees), A036361 (labeled 2-trees), A036362 (labeled 3-trees), A036506 (labeled 4-trees), A000055 (unlabeled trees), A054581 (unlabeled 2-trees).
%Y A000272 Cf. A097170.
%Y A000272 Cf. A058127 where a(n)= A058127(n-1,n) (right edge of triangle)
%K A000272 easy,nonn,core,nice
%O A000272 0,4
%A A000272 N. J. A. Sloane

are of general interest), please submit them using the
submission form http://oeis.org/Submit.html
and they will (probably) be added!  Thanks!

Subject line of incoming message (if any): Subject: test 5

Search was carried out on Wed Sep 28 12:49:21 EDT 2011

o  You can look up sequences online at the OEIS web site http://oeis.org/
o  For an explanation of the format used in the OEIS,
see http://oeis.org/wiki/Style_Sheet
o  If your sequence was not in the OEIS and is of general interest,
please submit it using the submission form http://oeis.org/Submit.html
o  There is a second sequence server (superseeker@oeis.org)
that tries hard to find an explanation.  Only 1 request per person
o  If the word "lookup" does not appear you will be sent the help file.

Sequentially yours, The On-Line Encyclopedia of Integer Sequences.
Maintained by The OEIS Foundation Inc., http://oeisf.org.
```

• Note that the reply shows the sequence represented in the "internal" format used in the database, rather than in the "beautified" format provided by the web pages. (Regular users prefer this format.)
• The internal format is described in the file eishelp1.html.
• You can also request copies of sequences by their A-numbers. Send an email message to sequences@oeis.org saying (for example):

```lookup A000088
lookup A000272
```
• Superseeker, a much more sophisticated program for analyzing sequences, and also accessed via email, is described in the next demonstration.

Click the single right arrow to go to the next demonstration page, or the single left arrow to return to the previous page.

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 23 14:40 EDT 2024. Contains 374549 sequences. (Running on oeis4.)