A000147 -id:A000147 - cp's OEIS frontend

A000094 Number of trees of diameter 4.

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

N. J. A. Sloane

nonn

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

			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)

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

Christian G. Bower, Table of n, a(n) for n = 1..500
J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.
J. Riordan, The enumeration of trees by height and diameter, IBM Journal 4 (1960), 473-478. (Annotated scanned copy)
Miloslav Znojil, Perturbation theory near degenerate exceptional points, arXiv:2008.00479 [math-ph], 2020.
Index entries for sequences related to trees

Cf. A000041, A206437, A034853, A000147 (diameter 5).

Cf. A006918, A083751, A084835, A105441, A115720, A257990, A307516, A307517, A325164.

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

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 *)

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

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

A034853 Triangle giving number of trees with n >= 3 nodes and diameter d >= 2.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 5, 2, 1, 1, 3, 8, 7, 3, 1, 1, 3, 14, 14, 11, 3, 1, 1, 4, 21, 32, 29, 14, 4, 1, 1, 4, 32, 58, 74, 42, 19, 4, 1, 1, 5, 45, 110, 167, 128, 66, 23, 5, 1

Offset: 3

N. J. A. Sloane

			   1
   1    1
   1    1    1
   1    2    2    1
   1    2    5    2    1
   1    3    8    7    3    1
   1    3   14   14   11    3    1
   1    4   21   32   29   14    4    1
   1    4   32   58   74   42   19    4    1
   1    5   45  110  167  128   66   23    5    1
   1    5   65  187  367  334  219   88   29    5    1
   1    6   88  322  755  850  645  328  123   34    6    1

R. J. Mathar, Table of n, a(n) for n = 3..212 (a(192) corrected by _Sean A. Irvine_, Apr 28 2022)
B. D. McKay, Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes.
B. D. McKay, Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes. [Cached copy of top page only, pdf file, no active links, with permission]
J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.
J. Riordan, The enumeration of trees by height and diameter, IBM Journal 4 (1960), 473-478. (Annotated scanned copy)
Index entries for sequences related to trees

Cf. A000055 (row sums), A283826, A000094 (diameter 4), A000147 (diameter 5), A000251 (diameter 6), A000550 (diameter 7), A000306 (diameter 8).

Reference gives recurrence.

A338706 Number of 2-linear trees on n nodes.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 3, 10, 24, 56, 114, 224, 411, 733, 1252, 2091, 3393, 5408, 8440, 12982, 19650, 29388, 43394, 63430, 91754, 131584, 187057, 263932, 369624, 514253, 710838, 976876, 1334828, 1814492, 2454011, 3303436, 4426627, 5906599, 7848883, 10389557

Offset: 1

N. J. A. Sloane, Nov 05 2020, using data supplied by Eric Wityk

nonn

A k-linear tree is a tree with exactly k vertices of degree 3 or higher all of which lie on a path. - Andrew Howroyd, Dec 17 2020

Empirically the partial sums of A000147. - Sean A. Irvine, Jul 11 2022

			The a(6) = 1 tree is:
         o   o
         |   |
     o---o---o---o

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Tanay Wakhare, Eric Wityk, and Charles R. Johnson, The proportion of trees that are linear, Discrete Mathematics 343.10 (2020): 112008. Also Corrigendum and preprint arXiv:1901.08502 [math.CO], 2019-2020. See Tables 1 and 2 (but beware errors).

Column k=2 of A380363 and A238415.

Cf. A000041, A000147, A130131, A338707, A338708.

seq(n)=my(p=1/(eta(x + O(x^(n-3))))); Vec(((x*(p - 1/(1-x)))^2 + x^2*(subst(p,x,x^2) - 1/(1-x^2)))/(2*(1-x)), -n) \\ Andrew Howroyd, Dec 17 2020

G.f.: ((x*(P(x) - 1/(1-x)))^2 + x^2*(P(x^2) - 1/(1-x^2)))/(2*(1-x)) where P(x) is the g.f. of A000041. - Andrew Howroyd, Dec 17 2020

Terms a(31) and beyond from Andrew Howroyd, Dec 17 2020

cp's OEIS Frontend

A000094 Number of trees of diameter 4.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A034853 Triangle giving number of trees with n >= 3 nodes and diameter d >= 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A338706 Number of 2-linear trees on n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions