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-7 of 7 results.

A000055 Number of trees with n unlabeled nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, 7741, 19320, 48629, 123867, 317955, 823065, 2144505, 5623756, 14828074, 39299897, 104636890, 279793450, 751065460, 2023443032, 5469566585, 14830871802, 40330829030, 109972410221, 300628862480, 823779631721, 2262366343746, 6226306037178
Offset: 0

Views

Author

Keywords

Comments

Also, number of unlabeled 2-gonal 2-trees with n-1 2-gons, for n>0. [Corrected by Andrei Zabolotskii, Jul 29 2025]
Main diagonal of A054924.
Left border of A157905. - Gary W. Adamson, Mar 08 2009
From Robert Munafo, Jan 24 2010: (Start)
Also counts classifications of n items that require exactly n-1 binary partitions; see Munafo link at A005646, also A171871 and A171872.
The 11 trees for n = 7 are illustrated at the Munafo web link.
Link to A171871/A171872 conjectured by Robert Munafo, then proved by Andrew Weimholt and Franklin T. Adams-Watters on Dec 29 2009. (End)
This is also "Number of tree perfect graphs on n nodes" [see Hougardy]. - N. J. A. Sloane, Dec 04 2015
For n > 0, a(n) is the number of ways to arrange n-1 unlabeled non-intersecting circles on a sphere. - Vladimir Reshetnikov, Aug 25 2016
All trees for n=1 through n=12 are depicted in Chapter 1 of the Steinbach reference. On p. 6 appear encircled two trees (with n=10) which seem inequivalent only when considered as ordered (planar) trees. Earlier instances of such possibly (in)equivalent trees could appear from n=6 on (and from n=9 on without equivalence modulo plane symmetry) but are not drawn separately there. - M. F. Hasler, Aug 29 2017

Examples

			a(1) = 1 [o]; a(2) = 1 [o-o]; a(3) = 1 [o-o-o];
a(4) = 2 [o-o-o and o-o-o-o]
            |
            o
G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + 23*x^8 + ...
		

References

  • F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 279.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 55.
  • N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 49.
  • A. Cayley, On the analytical forms called trees, with application to the theory of chemical combinations, Reports British Assoc. Advance. Sci. 45 (1875), 257-305 = Math. Papers, Vol. 9, 427-460 (see p. 459).
  • S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 295-316.
  • J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 526.
  • F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 232.
  • F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 58 and 244.
  • D. E. Knuth, Fundamental Algorithms, 3d Ed. 1997, pp. 386-88.
  • R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 138.
  • 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).

Crossrefs

Cf. A000676 (centered trees), A000677 (bicentered trees), A027416 (trees with a centroid), A102011 (trees with a bicentroid), A034853 (refined by diameter), A238414 (refined by maximum vertex degree).
Cf. A000081 (rooted trees), A000272 (labeled trees), A000169 (labeled rooted trees), A212809 (radius of convergence).
Cf. A036361 (labeled 2-trees), A036362 (labeled 3-trees), A036506 (labeled 4-trees), A054581 (unlabeled 2-trees).
Cf. A157904, A157905, A005195 (Euler transform = forests), A095133 (multisets).
Column 0 of A335362 and A034799.
Related to A005646; see A171871 and A171872.

Programs

  • Haskell
    import Data.List (generic_index)
    import Math.OEIS (getSequenceByID)
    triangle x = (x * x + x) `div` 2
    a000055 n = let {r = genericIndex (fromJust (getSequenceByID "A000081")); (m, nEO) = divMod n 2}
                in  r n - sum (zipWith (*) (map r [0..m]) (map r [n, n-1..]))
                    + (1-nEO) * (triangle (r m + 1))
    -- Walt Rorie-Baety, Jun 12 2021
    
  • Magma
    N := 30; P := PowerSeriesRing(Rationals(),N+1); f := func< A | x*&*[Exp(Evaluate(A,x^k)/k) : k in [1..N]]>; G := x; for i in [1..N] do G := f(G); end for; G000081 := G; G000055 := 1 + G - G^2/2 + Evaluate(G,x^2)/2; A000055 := Eltseq(G000055); // Geoff Baileu (geoff(AT)maths.usyd.edu.au), Nov 30 2009
    
  • Maple
    G000055 := series(1+G000081-G000081^2/2+subs(x=x^2,G000081)/2,x,31); A000055 := n->coeff(G000055,x,n); # where G000081 is g.f. for A000081 starting with n=1 term
    with(numtheory): b:= proc(n) option remember; `if`(n<=1, n, (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/ (n-1)) end: a:= n-> `if`(n=0, 1, b(n) -(add(b(k) *b(n-k), k=0..n) -`if`(irem(n, 2)=0, b(n/2), 0))/2):
    seq(a(n), n=0..50);
    # Alois P. Heinz, Aug 21 2008
    # Program to create b-file b000055.txt:
    A000081 := proc(n) option remember; local d, j;
    if n <= 1 then n else
        add(add(d*procname(d),d=numtheory[divisors](j))*procname(n-j),j=1..n-1)/(n-1);
    fi end:
    A000055 := proc(nmax) local a81, n, t, a, j, i ;
    a81 := [seq(A000081(i), i=0..nmax)] ; a := [] ;
    for n from 0 to nmax do
        if n = 0 then
            t := 1+op(n+1, a81) ;
        else
            t := op(n+1, a81) ;
        fi;
        if type(n, even) then
            t := t-op(1+n/2, a81)^2/2 ;
            t := t+op(1+n/2, a81)/2 ;
        fi;
        for j from 0 to (n-1)/2 do
            t := t-op(j+1, a81)*op(n-j+1, a81) ;
        od:
        a := [op(a), t] ;
    od:
    a end:
    L := A000055(1000) ;
    #  R. J. Mathar, Mar 06 2009
  • Mathematica
    s[n_, k_] := s[n, k] = a[n + 1 - k] + If[n < 2k, 0, s[n - k, k]]; a[1] = 1; a[n_] := a[n] = Sum[a[i] s[n-1, i] i, {i, 1, n-1}] / (n-1); Table[a[i] - Sum[a[j] a[i-j], {j, 1, i/2}] + If[OddQ[i], 0, a[i/2] (a[i/2] + 1)/2], {i, 1, 50}] (* Robert A. Russell *)
    b[0] = 0; b[1] = 1; b[n_] := b[n] = Sum[d*b[d]*b[n-j], {j, 1, n-1}, {d, Divisors[j]}]/(n-1); a[0] = 1; a[n_] := b[n] - (Sum[b[k]*b[n-k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Apr 09 2014, after Alois P. Heinz *)
  • PARI
    {a(n) = local(A, A1, an, i, t); if( n<2, n>=0, an = Vec(A = A1 = 1 + O('x^n)); for(m=2, n, i=m\2; an[m] = sum(k=1, i, an[k] * an[m-k]) + (t = polcoeff( if( m%2, A *= (A1 - 'x^i)^-an[i], A), m-1))); t + if( n%2==0, binomial( -polcoeff(A, i-1), 2)))}; /* Michael Somos */
    
  • PARI
    N=66;  A=vector(N+1, j, 1);
    for (n=1, N, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d * A[d]) * A[n-k+1] ) );
    A000081=concat([0], A);
    H(t)=subst(Ser(A000081, 't), 't, t);
    x='x+O('x^N);
    Vec( 1 + H(x) - 1/2*( H(x)^2 - H(x^2) ) )
    \\ Joerg Arndt, Jul 10 2014
    
  • Python
    # uses function from A000081
    def A000055(n): return 1 if n == 0 else A000081(n)-sum(A000081(i)*A000081(n-i) for i in range(1,n//2+1)) + (0 if n % 2 else (A000081(n//2)+1)*A000081(n//2)//2) # Chai Wah Wu, Feb 03 2022
  • SageMath
    [len(list(graphs.trees(n))) for n in range(16)] # Peter Luschny, Mar 01 2020
    

Formula

G.f.: A(x) = 1 + T(x) - T^2(x)/2 + T(x^2)/2, where T(x) = x + x^2 + 2*x^3 + ... is the g.f. for A000081.
a(n) ~ A086308 * A051491^n * n^(-5/2). - Vaclav Kotesovec, Jan 04 2013
a(n) = A000081(n) - A217420(n+1), n > 0. - R. J. Mathar, Sep 19 2016
a(n) = A000676(n) + A000677(n). - R. J. Mathar, Aug 13 2018
a(n) = A000081(n) - (Sum_{1<=i<=j, i+j=n} A000081(i)*A000081(j)) + (1-(-1)^(n-1)) * binomial(A000081(n/2)+1,2) / 2 [Li, equation 4.2]. - Walt Rorie-Baety, Jul 05 2021

A000094 Number of trees of diameter 4.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 5, 8, 14, 21, 32, 45, 65, 88, 121, 161, 215, 280, 367, 471, 607, 771, 980, 1232, 1551, 1933, 2410, 2983, 3690, 4536, 5574, 6811, 8317, 10110, 12276, 14848, 17941, 21600, 25977, 31146, 37298, 44542, 53132, 63218, 75131, 89089
Offset: 1

Views

Author

Keywords

Comments

Number of partitions of n-1 with at least two parts of size 2 or larger. - Franklin T. Adams-Watters, Jan 13 2006
Also equal to the number of partitions p of n-1 such that max(p)-min(p) > 1. Example: a(7)=5 because we have [5,1],[4,2],[4,1,1],[3,2,1] and [3,1,1,1]. - Giovanni Resta, Feb 06 2006
Also number of partitions of n-1 with at least two parts that are smaller than the largest part. Example: a(7)=5 because we have [4,1,1],[3,2,1],[3,1,1,1],[2,2,1,1,1] and [2,1,1,1,1]. - Emeric Deutsch, May 01 2006
Also number of regions of n-1 that do not contain 1 as a part, n >= 2 (cf. A186114, A206437). - Omar E. Pol, Dec 01 2011
Also rank of the last region of n-1 multiplied by -1, n >= 2 (cf. A194447). - Omar E. Pol, Feb 11 2012
Also sum of ranks of the regions of n-1 that contain emergent parts, n >= 2 (cf. A182699). For the definition of "regions of n" see A206437. - Omar E. Pol, Feb 21 2012

Examples

			From _Gus Wiseman_, Apr 12 2019: (Start)
The a(5) = 1 through a(9) = 14 partitions of n-1 with at least two parts of size 2 or larger, or non-hooks, are the following. The Heinz numbers of these partitions are given by A105441.
  (22)  (32)   (33)    (43)     (44)
        (221)  (42)    (52)     (53)
               (222)   (322)    (62)
               (321)   (331)    (332)
               (2211)  (421)    (422)
                       (2221)   (431)
                       (3211)   (521)
                       (22111)  (2222)
                                (3221)
                                (3311)
                                (4211)
                                (22211)
                                (32111)
                                (221111)
The a(5) = 1 through a(9) = 14 partitions of n-1 whose maximum part minus minimum part is at least 2 are the following. The Heinz numbers of these partitions are given by A307516.
  (31)  (41)   (42)    (52)     (53)
        (311)  (51)    (61)     (62)
               (321)   (331)    (71)
               (411)   (421)    (422)
               (3111)  (511)    (431)
                       (3211)   (521)
                       (4111)   (611)
                       (31111)  (3221)
                                (3311)
                                (4211)
                                (5111)
                                (32111)
                                (41111)
                                (311111)
The a(5) = 1 through a(9) = 14 partitions of n-1 with at least two parts that are smaller than the largest part are the following. The Heinz numbers of these partitions are given by A307517.
  (211)  (311)   (321)    (322)     (422)
         (2111)  (411)    (421)     (431)
                 (2211)   (511)     (521)
                 (3111)   (3211)    (611)
                 (21111)  (4111)    (3221)
                          (22111)   (3311)
                          (31111)   (4211)
                          (211111)  (5111)
                                    (22211)
                                    (32111)
                                    (41111)
                                    (221111)
                                    (311111)
                                    (2111111)
(End)
		

References

  • 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).

Crossrefs

Programs

  • Maple
    g:=x/product(1-x^j,j=1..70)-x-x^2/(1-x)^2: gser:=series(g,x=0,48): seq(coeff(gser,x,n),n=1..46); # Emeric Deutsch, May 01 2006
    A000094 := proc(n)
        combinat[numbpart](n-1)-n+1 ;
    end proc: # R. J. Mathar, May 17 2016
  • Mathematica
    t=Table[PartitionsP[n]-n,{n,0,45}];
    ReplacePart[t,0,1]
    (* Clark Kimberling, Mar 05 2012 *)
    CoefficientList[1/QPochhammer[x]-x/(1-x)^2-1+O[x]^50, x] (* Jean-François Alcover, Feb 04 2016 *)

Formula

a(n+1) = A000041(n)-n for n>0. - John W. Layman
G.f.: x/product(1-x^j,j=1..infinity)-x-x^2/(1-x)^2. - Emeric Deutsch, May 01 2006
G.f.: sum(sum(x^(i+j+1)/product(1-x^k, k=i..j), i=1..j-2), j=3..infinity). - Emeric Deutsch, May 01 2006
a(n+1) = Sum_{m=1..n} A083751(m). - Gregory Gerard Wojnar, Oct 13 2020

Extensions

More terms from Franklin T. Adams-Watters, Jan 13 2006

A000147 Number of trees of diameter 5.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 2, 7, 14, 32, 58, 110, 187, 322, 519, 839, 1302, 2015, 3032, 4542, 6668, 9738, 14006, 20036, 28324, 39830, 55473, 76875, 105692, 144629, 196585, 266038, 357952, 479664, 639519, 849425, 1123191, 1479972, 1942284, 2540674, 3311415
Offset: 1

Views

Author

Keywords

Comments

A tree of diameter 5 is formed from two rooted trees of height 2, with their roots joined. - Franklin T. Adams-Watters, Jan 13 2006

References

  • 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).

Crossrefs

Cf. A034853, A000251 (diameter 6).

Programs

  • Maple
    b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1 or k<1, 0,
         add(binomial(b((i-1)$2, k-1)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
        end:
    g:= n-> b((n-1)$2, 2) -b((n-1)$2, 1):
    a:= n-> (add(g(i)*g(n-i), i=0..n)+`if`(n::even, g(n/2), 0))/2:
    seq(a(n), n=1..45);  # Alois P. Heinz, Feb 09 2016
  • Mathematica
    b[n_, i_, k_] := b[n, i, k] = If[n==0, 1, If[i<1 || k<1, 0, Sum[Binomial[ b[i-1, i-1, k-1]+j-1, j]*b[n-i*j, i-1, k], {j, 0, n/i}]]]; g[n_] := b[n-1, n-1, 2] - b[n-1, n-1, 1]; a[n_] := (Sum[g[i]*g[n-i], {i, 0, n}] + If[EvenQ[n], g[n/2], 0])/2; Table[a[n], {n, 1, 45}] (* Jean-François Alcover, Feb 17 2016, after Alois P. Heinz *)

Formula

If n odd, a(n) = Sum_{k=1..(n-1)/2} b(k)*b(n-k); if n even, a(n) = (Sum_{k=1..n/2-1} b(k)*b(n-k)) + C(b(n/2)+1, 2), where b(n) = P(n-1)-1 = A000065(n-1). - Franklin T. Adams-Watters, Jan 13 2006

Extensions

More terms from Franklin T. Adams-Watters, Jan 13 2006

A000251 Number of trees of diameter 6.

Original entry on oeis.org

1, 3, 11, 29, 74, 167, 367, 755, 1515, 2931, 5551, 10263, 18677, 33409, 59024, 102984, 177915, 304458, 516939, 871180, 1458882, 2428548, 4021670, 6627515, 10874462, 17770474, 28932739, 46943967, 75925797, 122433291, 196879385, 315759282, 505168033, 806290796, 1284034606, 2040485004, 3235965074, 5121801962, 8091411114, 12759606939, 20085832527, 31565046053, 49523414558, 77575278933, 121329065354, 189475663960, 295465391518, 460087656595, 715436020515, 1110994054004
Offset: 7

Views

Author

Keywords

References

  • 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).

Crossrefs

Cf. A034853, A000550 (diameter 7).

Programs

  • PARI
    \\ sh_euler is shifted Euler transform.
    sh_euler(p)={my(m=serprec(p,x)-1); x*exp(sum(i=1, m, subst(p+O(x^(1+m\i)), x, x^i)/i))}
    lista(n)={my(s0=x + O(x*x^n), s1=sh_euler(s0), s2=sh_euler(s1), s3=sh_euler(s2), r2=s2-s1, r3=s3-s2, t6=r3-r2*s2); Vec(t6)} \\ Christian Sievers, May 18 2023

Extensions

More terms from Sean A. Irvine, Nov 21 2010

A000306 Number of trees of diameter 8.

Original entry on oeis.org

1, 4, 19, 66, 219, 645, 1813, 4802, 12265, 30198, 72396, 169231, 387707, 871989, 1930868, 4215615, 9091410, 19389327, 40944999, 85691893, 177898521, 366614456, 750494796, 1526979694, 3089556090, 6219191608, 12460307373, 24856533408, 49387348955, 97765283686, 192870793594, 379287172272
Offset: 9

Views

Author

Keywords

References

  • 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).

Crossrefs

Cf. A034853.

Programs

  • PARI
    sh_euler(p)={my(m=serprec(p,x)-1); x*exp(sum(i=1, m, subst(p+O(x^(1+m\i)), x, x^i)/i))}
    lista(n)={my(s2=sh_euler(sh_euler(x+O(x*x^n))), s3=sh_euler(s2), s4=sh_euler(s3), r3=s3-s2, r4=s4-s3, t8=r4-r3*s3); Vec(t8)} \\ Christian Sievers, May 18 2023

Extensions

More terms from Christian Sievers, May 18 2023

A000550 Number of trees of diameter 7.

Original entry on oeis.org

1, 3, 14, 42, 128, 334, 850, 2010, 4625, 10201, 21990, 46108, 94912, 191562, 380933, 746338, 1444676, 2763931, 5235309, 9822686, 18275648, 33734658, 61826344, 112550305, 203627610, 366267931, 655261559, 1166312530, 2066048261, 3643352362, 6397485909, 11188129665, 19491131627, 33831897511, 58519577756, 100885389220, 173368983090, 297021470421, 507378371670, 864277569606, 1468245046383, 2487774321958, 4204663810414, 7089200255686, 11924621337321, 20012746962064, 33513139512868, 56001473574091, 93387290773141, 155419866337746
Offset: 8

Views

Author

Keywords

References

  • 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).

Crossrefs

Cf. A034853, A000306 (diameter 8)

Programs

  • Maple
    b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1 or k<1, 0,
         add(binomial(b((i-1)$2, k-1)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
        end:
    g:= n-> b((n-1)$2, 3) -b((n-1)$2, 2):
    a:= n-> (add(g(i)*g(n-i), i=0..n)+`if`(n::even, g(n/2), 0))/2:
    seq(a(n), n=8..40);  # Alois P. Heinz, Feb 09 2016
  • Mathematica
    m = 50; r[x_] = (Rest @ CoefficientList[ Series[ x*Product[ (1 - x^k)^(- PartitionsP[k-1]), {k, 1, m+3}], {x, 0, m+3}], x] - PartitionsP[ Range[0, m+2]]).(x^Range[m+3]); A000550 = CoefficientList[(r[x]^2 + r[x^2])/2, x][[9 ;; m+8]] (* Jean-François Alcover, Feb 09 2016 *)

Formula

G.f.: a(x)=(r(x)^2+r(x^2))/2, where r(x) is the generating function of A000235. - Sean A. Irvine, Nov 21 2010

Extensions

More terms from Sean A. Irvine, Nov 21 2010

A283826 Irregular triangle read by rows: T(n,k) = number of trees on n nodes with radius k, n>=1, 1 <= k <= floor(n/2).

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 7, 3, 1, 11, 10, 1, 1, 17, 25, 4, 1, 25, 61, 18, 1, 1, 36, 132, 61, 5, 1, 50, 277, 194, 28, 1, 1, 70, 554, 553, 117, 6, 1, 94, 1077, 1495, 451, 40, 1, 1, 127, 2034, 3823, 1552, 197, 7, 1, 168, 3770, 9427, 5020, 879, 54, 1, 1, 222, 6853, 22466, 15289, 3485, 305, 8, 1
Offset: 1

Views

Author

N. J. A. Sloane, Mar 19 2017

Keywords

Comments

The radius of a tree is the maximal distance of a node from the center.

Examples

			Triangle begins:
  0,
  1,
  1,
  1,  1,
  1,  2,
  1,  4,   1,
  1,  7,   3,
  1, 11,  10,   1,
  1, 17,  25,   4,
  1, 25,  61,  18,  1,
  1, 36, 132,  61,  5,
  1, 50, 277, 194, 28, 1,
  ...
		

Crossrefs

Cf. A283827.
See also A000676, A000677, A027416, A102911, A004250 (column 2?), A000055 (row sums).

Formula

T(n,k) = A034853(n,2k-1) + A034853(n,2k). - R. J. Mathar, Apr 03 2017
Showing 1-7 of 7 results.