%I A000272 M3027 N1227
%S A000272 1,1,1,3,16,125,1296,16807,262144,4782969,100000000,2357947691,61917364224,
%T A000272 1792160394037,56693912375296,1946195068359375,72057594037927936,
%U A000272 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. - 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]
%D A000272 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences,
Academic Press, 1995 (includes this sequence).
%D A000272 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973
(includes this sequence).
%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 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 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.
%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]
%H A000272 N. J. A. Sloane, <a href="b000272.txt">Table of n, a(n) for n = 0..100</
a>
%H A000272 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 A000272 Saverio Caminiti and Emanuele G. Fusco, <a href="http://www.cs.uwaterloo.ca/
journals/JIS/VOL10/Caminiti/caminiti.html">On the Number of Labeled
k-arch Graphs</a>, Journal of Integer Sequences, Vol 10 (2007), Article
07.7.5
%H A000272 Huantian Cao, <a href="http://www.cs.uga.edu/~rwr/STUDENTS/hcao.html">
AutoGF</a>: An Automated System to Calculate Coefficients of Generating
Functions.
%H A000272 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 ...</a>, Report CS-2000-44, Department of Computer
Science, Univ. Utrecht.
%H A000272 S. Coulomb and M. Bauer, <a href="http://arXiv.org/abs/math.CO/0407456">
On vertex covers, matchings and random trees</a>
%H A000272 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=78">
Encyclopedia of Combinatorial Structures 78</a>
%H A000272 C. Lamathe, <a href="http://www.cs.uwaterloo.ca/journals/JIS/">The Number
of Labeled k-Arch Graphs</a>, Journal of Integer Sequences, Vol.
7 (2004), Article 04.3.1.
%H A000272 G. Martens, <a href="http://arXiv.org/abs/math/0605183v1">Polynomial
Equations of Degree n</a>.
%H A000272 J. Pitman, <a href="http://www.stat.berkeley.edu/users/pitman/457.pdf">
Coalescent Random Forests</a>, J. Combin. Theory, A85 (1999), 165-193.
%H A000272 S. Ramanujan, <a href="http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/
question/q738.htm">Question 738</a>, J. Ind. Math. Soc.
%H A000272 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
LabeledTree.html">Link to a section of The World of Mathematics.</
a>
%H A000272 D. Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/
mamarimPDF/labtree.pdf">The n^(n-2)-th Proof Of The Formula For The
Number Of Labeled Trees</a>
%H A000272 D. Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/
mamarimPDF/cayley.pdf">Yet Another Proof For The Enumeration Of Labeled
Trees</a>
%H A000272 D. Zvonkine, <a href="http://www.arXiv.org/abs/math.AG/0403092">An algebra
of power series...</a>
%H A000272 D. Zvonkine, <a href="http://www.math.jussieu.fr/~zvonkine/">Home Page</
a>
%H A000272 <a href="Sindx_Tra.html#trees">Index entries for sequences related to
trees</a>
%H A000272 <a href="Sindx_Cor.html#core">Index entries for "core" sequences</a>
%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]
%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
%p A000272 A000272 := n->n^(n-2); [ seq(n^(n-2), n=1..20) ];
%p A000272 seq(mul((n), k=3..n), n=1..19); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com),
Sep 14 2007
%p A000272 a:=n->mul(denom (1/(n+3)), k=0..n): seq(a(n), n=-3..16); - Zerinvary
Lajos (zerinvarylajos(AT)yahoo.com), Apr 26 2008
%p A000272 a:=n->mul(1+add(1, j=0..n),j=1..n):seq(a(n), n=-2..18);# [From Zerinvary
Lajos (zerinvarylajos(AT)yahoo.com), Dec 06 2008]
%p A000272 with(finance):seq(futurevalue( 1,n+1,n), n=0..17);# [From Zerinvary Lajos
(zerinvarylajos(AT)yahoo.com), Mar 24 2009]
%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: 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 Sequence in context: A157457 A000950 A000951 this_sequence A159594 A088358
A082161
%Y A000272 Adjacent sequences: A000269 A000270 A000271 this_sequence A000273 A000274
A000275
%K A000272 easy,nonn,core,nice
%O A000272 0,4
%A A000272 N. J. A. Sloane (njas(AT)research.att.com).
|
