| login |
Demonstration of the On-Line Encyclopedia of Integer Sequences® (OEIS®) (Page 10)
From sequences-reply@oeis.org Wed Sep 28 12:49:39 2011
Date: Wed, 28 Sep 2011 12:49:22 -0400
From: sequences-reply@oeis.org
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 D. Zvonkine, Home Page
%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
# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE
If any of your sequences were not found in the OEIS (and
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
per hour please.
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.
Please donate!
Click the single right arrow to go to the next demonstration page, or the single left arrow to return to the previous page.
|
