cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-6 of 6 results.

A000272 Number of trees on n labeled nodes: n^(n-2) with a(0)=1.

Original entry on oeis.org

1, 1, 1, 3, 16, 125, 1296, 16807, 262144, 4782969, 100000000, 2357947691, 61917364224, 1792160394037, 56693912375296, 1946195068359375, 72057594037927936, 2862423051509815793, 121439531096594251776, 5480386857784802185939, 262144000000000000000000, 13248496640331026125580781
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of spanning trees in complete graph K_n on n labeled nodes.
Robert Castelo, Jan 06 2001, observes that n^(n-2) is also the number of transitive subtree acyclic digraphs on n-1 vertices.
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
Also counts parking functions, critical configurations of the chip firing game, allowable pairs sorted by a priority queue [Hamel].
The parking functions of length n can be described as all permutations of all words [d(1),d(2), ..., d(n)] where 1 <= d(k) <= k; see example. There are (n+1)^(n-1) = a(n+1) parking functions of length n. - Joerg Arndt, Jul 15 2014
a(n+1) is the number of endofunctions with no cycles of length > 1; number of forests of rooted labeled trees on n vertices. - Mitch Harris, Jul 06 2006
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. - Abdullahi Umar, Aug 25 2008
a(n) is also the number of edge-labeled rooted trees on n nodes. - Nikos Apostolakis, Nov 30 2008
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 sequentially) 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}. - Geoffrey Critzer, Jul 20 2009
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)). - Dennis P. Walsh, Mar 02 2011
a(n) is the absolute value of the discriminant of the polynomial x^{n-1}+...+x+1. More precisely, a(n) = (-1)^{(n-1)(n-2)/2} times the discriminant. - Zach Teitler, Jan 28 2014
For n > 2, a(n+2) is the number of nodes in the canonical automaton for the affine Weyl group of type A_n. - Tom Edgar, May 12 2016
The tree formula a(n) = n^(n-2) is due to Cayley (see the first comment). - Jonathan Sondow, Jan 11 2018
a(n) is the number of topologically distinct lines of play for the game Planted Brussels Sprouts on n vertices. See Ji and Propp link. - Caleb Ji, May 11 2018
a(n+1) is also the number of bases of R^n, that can be made from the n(n+1)/2 vectors of the form [0 ... 0 1 ... 1 0 ... 0]^T, where the initial or final zeros are optional, but at least one 1 has to be included. - Nicolas Nagel, Jul 31 2018
Cooper et al. show that every connected k-chromatic graph contains at least k^(k-2) spanning trees. - Michel Marcus, May 14 2020

Examples

			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
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)}.
From _Joerg Arndt_ and Greg Stevenson, Jul 11 2011: (Start)
The following products of 3 transpositions lead to a 4-cycle in S_4:
  (1,2)*(1,3)*(1,4);
  (1,2)*(1,4)*(3,4);
  (1,2)*(3,4)*(1,3);
  (1,3)*(1,4)*(2,3);
  (1,3)*(2,3)*(1,4);
  (1,4)*(2,3)*(2,4);
  (1,4)*(2,4)*(3,4);
  (1,4)*(3,4)*(2,3);
  (2,3)*(1,2)*(1,4);
  (2,3)*(1,4)*(2,4);
  (2,3)*(2,4)*(1,2);
  (2,4)*(1,2)*(3,4);
  (2,4)*(3,4)*(1,2);
  (3,4)*(1,2)*(1,3);
  (3,4)*(1,3)*(2,3);
  (3,4)*(2,3)*(1,2).  (End)
The 16 parking functions of length 3 are 111, 112, 121, 211, 113, 131, 311, 221, 212, 122, 123, 132, 213, 231, 312, 321. - _Joerg Arndt_, Jul 15 2014
G.f. = 1 + x + x^2 + 3*x^3 + 16*x^4 + 125*x^5 + 1296*x^6 + 16807*x^7 + ...

References

  • M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 1999; see p. 142.
  • Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups. Graduate Texts in Mathematics, 231. Springer, New York, 2005.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 311.
  • J. Dénes, The representation of a permutation as the product of a minimal number of transpositions and its connection with the theory of graphs, Pub. Math. Inst. Hung. Acad. Sci., 4 (1959), 63-70.
  • I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, ex. 3.3.33.
  • J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 524.
  • F. Harary, J. A. Kabell, and F. R. McMorris (1992), Subtree acyclic digraphs, Ars Comb., vol. 34:93-95.
  • 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)
  • H. Prüfer, Neuer Beweis eines Satzes über Permutationen, Archiv der Mathematik und Physik, (3) 27 (1918), 142-144.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 128.
  • 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).
  • R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see page 25, Prop. 5.3.2.
  • J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge Univ. Press, 1992.

Links

Crossrefs

Cf. A000169, A000254, A000312, A007778, A007830, A008785-A008791, A052750, A081048, A083483, A097170, A239910.
a(n) = A033842(n-1, 0) (first column of triangle).
a(n) = A058127(n-1, n) (right edge of triangle).
Cf. A000272 (labeled trees), A036361 (labeled 2-trees), A036362 (labeled 3-trees), A036506 (labeled 4-trees), A000055 (unlabeled trees), A054581 (unlabeled 2-trees).
Column m=1 of A105599. - Alois P. Heinz, Apr 10 2014

Programs

  • Haskell
    a000272 0 = 1; a000272 1 = 1
a000272 n = n ^ (n - 2)  -- Reinhard Zumkeller, Jul 07 2013
  • Magma
    [ n^(n-2) : n in [1..10]]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006
  • Maple
    A000272 := n -> ifelse(n=0, 1, n^(n-2)): seq(A000272(n), n = 0..20); # Peter Luschny, Jun 12 2022
  • Mathematica
    << DiscreteMath`Combinatorica` Table[NumberOfSpanningTrees[CompleteGraph[n]], {n, 1, 20}] (* Artur Jasinski, Dec 06 2007 *)
Join[{1},Table[n^(n-2),{n,20}]] (* Harvey P. Dale, Nov 28 2012 *)
a[ n_] := If[ n < 1, Boole[n == 0], n^(n - 2)]; (* Michael Somos, May 25 2014 *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ 1 - LambertW[-x] - LambertW[-x]^2 / 2, {x, 0, n}]]; (* Michael Somos, May 25 2014 *)
a[ n_] := If[ n < 1, Boole[n == 0], With[ {m = n - 1}, m! SeriesCoefficient[ Exp[ -LambertW[-x]], {x, 0, m}]]]; (* Michael Somos, May 25 2014 *)
a[ n_] := If[ n < 2, Boole[n >= 0], With[ {m = n - 1}, m! SeriesCoefficient[ InverseSeries[ Series[ Log[1 + x] / (1 + x), {x, 0, m}]], m]]]; (* Michael Somos, May 25 2014 *)
a[ n_] := If[ n < 1, Boole[n == 0], With[ {m = n - 1}, m! SeriesCoefficient[ Nest[ 1 + Integrate[ #^2 / (1 - x #), x] &, 1 + O[x], m], {x, 0, m}]]]; (* Michael Somos, May 25 2014 *)
  • Maxima
    A000272[n]:=if n=0 then 1 else n^(n-2)$
makelist(A000272[n],n,0,30); /* Martin Ettl, Oct 29 2012 */
  • PARI
    {a(n) = if( n<1, n==0, n^(n-2))}; /* Michael Somos, Feb 16 2002 */
  • PARI
    {a(n) = my(A); if( n<1, n==0, n--; A = 1 + O(x); for(k=1, n, A = 1 + intformal( A^2 / (1 - x * A))); n! * polcoeff( A, n))}; /* Michael Somos, May 25 2014 */
  • PARI
    /* GP Function for Determinant of Hermitian (square symmetric) matrix for univariate polynomial of degree n by Gerry 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, May 04 2007 */
  • Python
    def A000272(n): return 1 if n <= 1 else n**(n-2) # Chai Wah Wu, Feb 03 2022

Formula

E.g.f.: 1 + T - (1/2)*T^2; where T=T(x) is Euler's tree function (see A000169, also A001858). - Len Smiley, Nov 19 2001
Number of labeled k-trees on n nodes is binomial(n, k) * (k*(n-k)+1)^(n-k-2).
E.g.f. for b(n)=a(n+2): ((W(-x)/x)^2)/(1+W(-x)), where W is Lambert's function (principal branch). [Equals d/dx (W(-x)/(-x)). - Wolfdieter Lang, Oct 25 2022]
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, May 04 2007
a(n+1) = Sum_{i=1..n} i * n^(n-1-i) * binomial(n, i). - Yong Kong (ykong(AT)curagen.com), Dec 28 2000
For n >= 1, a(n+1) = Sum_{i=1..n} n^(n-i)*binomial(n-1,i-1). - Geoffrey Critzer, Jul 20 2009
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..." - Dennis P. Walsh, Mar 02 2011
From Sergei N. Gladkovskii, Sep 18 2012: (Start)
E.g.f.: 1 + x + x^2/(U(0) - x) where U(k) = x*(k+1)*(k+2)^k + (k+1)^k*(k+2) - x*(k+2)^2*(k+3)*((k+1)*(k+3))^k/U(k+1); (continued fraction).
G.f.: 1 + x + x^2/(U(0)-x) where U(k) = x*(k+1)*(k+2)^k + (k+1)^k - x*(k+2)*(k+3)*((k+1)*(k+3))^k/E(k+1); (continued fraction). (End)
Related to A000254 by Sum_{n >= 1} a(n+1)*x^n/n! = series reversion( 1/(1 + x)*log(1 + x) ) = series reversion(x - 3*x^2/2! + 11*x^3/3! - 50*x^4/4! + ...). Cf. A052750. - Peter Bala, Jun 15 2016
For n >= 3 and 2 <= k <= n-1, the number of trees on n vertices with exactly k leaves is binomial(n,k)*S(n-2,n-k)(n-k)! where S(a,b) is the Stirling number of the second kind. Therefore a(n) = Sum_{k=2..n-1} binomial(n,k)*S(n-2,n-k)(n-k)! for n >= 3. - Jonathan Noel, May 05 2017

A097174 Total number of red nodes among tricolored labeled trees on n nodes.

Original entry on oeis.org

1, 0, 6, 12, 320, 2190, 51492, 685496, 17286768, 348213690, 9956411300, 266065478052, 8737396913544, 287741445880070, 10816320294520860, 420123621828718320, 17913098835916877792, 798053882730994171890, 38192029991097097185108, 1914946396460982552420380
Offset: 1

Views

Author

Ralf Stephan, Jul 30 2004

Keywords

Links

Crossrefs

Cf. A097170, A097171, A097172, A097173, A000272, A000169.

Programs

  • Mathematica
    Rest[CoefficientList[Series[LambertW[-LambertW[-x]], {x, 0, 20}], x] * Range[0, 20]!] (* Vaclav Kotesovec, Aug 26 2016 *)
  • PARI
    x='x+O('x^50); Vec(serlaplace(lambertw(-lambertw(-x)))) \\ G. C. Greubel, Nov 15 2017

Formula

E.g.f.: A(x) = -T(-T(x)), with T(x) = Sum_{k>=1} A000169(k)/k!*x^k.
a(n) = -n^(n-1) * Sum_{j=1..n} (-j/n)^j*C(n, j).
a(n) ~ LambertW(1)*n^(n-1)/(1+LambertW(1)). - Vaclav Kotesovec, Aug 26 2016

A097172 Total number of brown nodes among tricolored labeled trees on n nodes.

Original entry on oeis.org

3, 4, 185, 1026, 30457, 362664, 10245825, 195060070, 5907674201, 153676400076, 5199628119985, 169205814335754, 6462995557999905, 249877775352089296, 10749867848389013249, 478345428286978038606, 23013713995857481324969
Offset: 3

Views

Author

Ralf Stephan, Jul 30 2004

Keywords

Links

Crossrefs

Equals A000169(n)-A097174(n)-A097173(n).
Cf. A097170, A097171, A097173, A097174, A000272.

Programs

  • Mathematica
    Drop[CoefficientList[Series[-LambertW[-x] - LambertW[-LambertW[-x]]- LambertW[-LambertW[-x]]^2, {x, 0, 20}], x] * Range[0, 20]!, 3] (* Vaclav Kotesovec, Aug 26 2016 *)

Formula

E.g.f.: A(x) = T(x)+T(-T(x))-T(-T(x))^2, with T(x)=Sum[k=1..inf, A000169(k)/k!*x^k].
a(n) = -n^(n-1) * {1 + Sum[l=1..n, (-l/n)^l*(2/l-1)*C(n, l)]}.
a(n) ~ (1-2*LambertW(1)^2)*n^(n-1)/(1+LambertW(1)). - Vaclav Kotesovec, Aug 26 2016

A097173 Total number of green nodes among tricolored labeled trees on n nodes.

Original entry on oeis.org

0, 2, 0, 48, 120, 4560, 35700, 1048992, 15514128, 456726240, 10073339100, 323266492560, 9361060088952, 336767513038320, 11913610172869860, 482920107426039360, 19998225191360977440, 909512248720724321472
Offset: 1

Views

Author

Ralf Stephan, Jul 30 2004

Keywords

Links

Crossrefs

Cf. A097170, A097171, A097172, A097174, A000272.

Programs

  • Mathematica
    Rest[CoefficientList[Series[LambertW[-LambertW[-x]]^2, {x, 0, 20}], x] * Range[0, 20]!] (* Vaclav Kotesovec, Aug 26 2016 *)

Formula

E.g.f.: A(x) = T(-T(x))^2, with T(x)=Sum[k=1..inf, A000169(k)/k!*x^k].
a(n) = -2 * n^(n-1) * Sum[l=1..n, (-l/n)^l*(1/l-1)*C(n, l)].
a(n) ~ 2*LambertW(1)^2*n^(n-1)/(1+LambertW(1)). - Vaclav Kotesovec, Aug 26 2016

A097171 Number of maximal matchings among labeled trees on n nodes.

Original entry on oeis.org

1, 1, 6, 24, 320, 3270, 55482, 999656, 21718440, 544829130, 15130478990, 475440344412, 16294653237876, 613546243029902, 25016884214147490, 1100408748640263120, 51948228453097163312, 2617775548597611727506, 140364712844785892810646, 7975414423897012183673540
Offset: 1

Views

Author

Ralf Stephan, Jul 30 2004

Keywords

Links

Crossrefs

Cf. A097170, A097172, A097173, A097174, A000169, A000272.

Programs

  • Maple
    umax := 20 ; u := array(0..umax) ; U := proc() global umax,u ; local resul,n ; resul :=0 ; for n from 0 to umax do resul := resul+u[n]*x^n ; od: end: expU := proc() global umax,u ; taylor(exp(U()),x=0,umax+1) ; end: xexpU := proc() global umax,u ; taylor(x*expU(),x=0,umax+1) ; end: exexpU := proc() global umax,u ; local t ; t := xexpU() ; taylor(exp(-t^2+t+3*U()),x=0,umax+1) ; end: A := expand(taylor(U()-x^2*exexpU(), x=0,umax+1)) ; for n from 0 to umax do u[n] := solve(coeff(A,x,n),u[n]) ; od : F := proc() t := xexpU() ; taylor(-(t+U())^2/2+(1+U()*t)*t+U()-U()^2,x=0,umax+1) ; end: egf := F() ; for n from 1 to umax do n!*coeff(egf,x,n) ; od; # R. J. Mathar, Sep 14 2006
  • Mathematica
    nmax = 20; egf := -U^2 - (1/2)*(E^U*x + U)^2 + E^U*x*(E^U*U*x + 1) + U;
U = 1;
Do[U = Normal[x^2*E^(E^(2U)*(-x^2) + E^U*x + 3U) + O[x]^n], {n, 1, nmax}];
Rest[Range[0, nmax - 1]!*CoefficientList[egf + O[x]^nmax, x]] (* Jean-François Alcover, Dec 14 2017 *)

Formula

Coulomb and Bauer give a g.f.

Extensions

More terms from R. J. Mathar, Sep 14 2006

A173249 Partial sums of A000272.

Original entry on oeis.org

1, 2, 3, 6, 22, 147, 1443, 18250, 280394, 5063363, 105063363, 2463011054, 64380375278, 1856540769315, 58550453144611, 2004745521503986, 74062339559431922, 2936485391069247715, 124376016487663499491
Offset: 0

Views

Author

Jonathan Vos Post, Feb 13 2010

Keywords

Comments

Partial sums of number of trees on n labeled nodes. The subsequence of primes in this sequence begin: 2, 58550453144611, no more through a(30).

Examples

			a(19) = 1 + 1 + 1 + 3 + 16 + 125 + 1296 + 16807 + 262144 + 4782969 + 100000000 + 2357947691 + 61917364224 + 1792160394037 + 56693912375296 + 1946195068359375 + 72057594037927936 + 2862423051509815793 + 121439531096594251776 + 5480386857784802185939.

Crossrefs

Cf. A000055, A000169, A000312, A007778, A007830, A008785-A008791, A033842, A000272, A036361, A036362, A036506, A000055, A054581, A097170

Formula

a(n) = SUM[i=0..n] A000272(i) = SUM[i=0..n] i^(i-2).
Showing 1-6 of 6 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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