A338708 -id:A338708 - cp's OEIS frontend

A130131 Number of n-lobsters.

1, 1, 1, 2, 3, 6, 11, 23, 47, 105, 231, 532, 1224, 2872, 6739, 15955, 37776, 89779, 213381, 507949, 1209184, 2880382, 6861351, 16348887, 38955354, 92831577, 221219963, 527197861, 1256385522, 2994200524, 7135736613, 17005929485, 40528629737, 96588403995, 230190847410

Offset: 1

Eric W. Weisstein, May 11 2007

nonn

A lobster graph is a tree having the property that the removal of all leaf nodes leaves a caterpillar graph (see A005418). - N. J. A. Sloane, Nov 05 2020

			a(10) = 105 = A000055(10) - 1 because all trees with 10 vertices are lobsters except this one:
    o-o-o
   /
  o-o-o-o
   \
    o-o-o
Also, all trees with 10 vertices are linear (all vertices of degree >2 belong to a single path) except this one:
     o   o
      \ /
       o
       |
       o
     /   \
    o     o
   / \   / \
  o   o o   o

Andrew Howroyd, Table of n, a(n) for n = 1..200
Andrew Howroyd, Formula for number of lobsters
G. Li and F. Ruskey, C program [dead link]
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. See Tables 1 and 2 (but beware errors).
Eric Weisstein's World of Mathematics, Lobster Graph

Row sums of A380363.
Cf. A000055, A005418, A058984, A130132, A331693, A363251.
Cf. k-linear trees for k = 1..4: A004250, A338706, A338707, A338708.

eta = QPochhammer;
s[n_] := With[{ox = O[x]^n}, x^2 ((1/eta[x + ox] - 1/(1 - x))^2/(1 - x/eta[x + ox]) + (1/eta[x^2 + ox] - 1/(1 - x^2))(1 + x/eta[x + ox])/(1 - x^2/eta[x^2 + ox]))/2 + x/eta[x + ox] - x^3/((1 - x)^2*(1 + x))];
CoefficientList[s[32], x] // Rest (* Jean-François Alcover, Nov 17 2020, after Andrew Howroyd *)

s(n)={my(ox=O(x^n)); x^2*((1/eta(x+ox)-1/(1-x))^2/(1-x/eta(x+ox)) + (1/eta(x^2+ox)-1/(1-x^2))*(1+x/eta(x+ox))/(1-x^2/eta(x^2+ox)))/2 + x/eta(x+ox) - x^3/((1-x)^2*(1+x))}
Vec(s(30)) \\ Andrew Howroyd, Nov 02 2017

a(15)-a(32) from Washington Bomfim, Feb 23 2011

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

A338707 Number of 3-linear trees on n nodes.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 5, 22, 74, 219, 576, 1394, 3150, 6733, 13744, 26969, 51185, 94323, 169453, 297533, 512006, 865050, 1437739, 2353756, 3801041, 6060918, 9552826, 14894428, 22991659, 35159606, 53299703, 80137271, 119563216, 177091225, 260504790, 380720841

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

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=3 of A380363 and A238415.

Cf. A000041, A130131, A338706, A338708.

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

G.f.: x^3*(P(x)-1)*((P(x) - 1/(1-x))^2/(1-x)^2 + (P(x^2) - 1/(1-x^2))/(1-x^2))/2 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

A380363 Triangle read by rows: T(n,k) is the number of linear trees with n vertices and k vertices of degree >= 3, 0 <= k <= max(0, floor(n/2)-1).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 7, 3, 1, 11, 10, 1, 1, 17, 24, 5, 1, 25, 56, 22, 1, 1, 36, 114, 74, 6, 1, 50, 224, 219, 37, 1, 1, 70, 411, 576, 158, 8, 1, 94, 733, 1394, 591, 58, 1, 1, 127, 1252, 3150, 1896, 304, 9, 1, 168, 2091, 6733, 5537, 1342, 82, 1

Offset: 0

Andrew Howroyd, Jan 26 2025

A linear tree is a tree with all vertices of degree > 2 belonging to a single path. These are equinumerous with lobster graphs. All trees having at most 3 vertices of degree > 2 are linear trees.

			Triangle begins:
  1;
  1;
  1;
  1;
  1,   1;
  1,   2;
  1,   4,    1;
  1,   7,    3;
  1,  11,   10,    1;
  1,  17,   24,    5;
  1,  25,   56,   22,    1;
  1,  36,  114,   74,    6;
  1,  50,  224,  219,   37,   1;
  1,  70,  411,  576,  158,   8;
  1,  94,  733, 1394,  591,  58, 1;
  1, 127, 1252, 3150, 1896, 304, 9;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..2501 (rows 0..100)
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. See Table 1.
Eric Weisstein's World of Mathematics, Lobster Graph.

Columns 0..4 are A000012, A004250(n-1), A338706, A338707, A338708.
Row sums are A130131.
Cf. A238415 (initial columns same up to k=3).

G(n,y)={my(p=1/eta(x + O(x^n)), p2=1/eta(x^2 + O(x^n)),
  g1=(p - 1/(1-x))^2/((1 - x)*(1 - x*y*(p-1)/(1-x))),
  g2=(p2 - 1/(1-x^2))*(1 + x + x*y*(p-1))/((1 - x^2)*(1 - x^2*y^2*(p2-1)/(1-x^2))) );
  x^2*y^2*(g1 + g2)/2 + x*y*(p - 1/((1 + x)*(1 - x)^2)) + 1/(1-x)
}
T(n)=[Vecrev(p) | p<-Vec(G(n,y))]
{my(A=T(15)); for(i=1, #A, print(A[i]))}

cp's OEIS Frontend

A130131 Number of n-lobsters.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A338706 Number of 2-linear trees on n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A338707 Number of 3-linear trees on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A380363 Triangle read by rows: T(n,k) is the number of linear trees with n vertices and k vertices of degree >= 3, 0 <= k <= max(0, floor(n/2)-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI