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

Author

Eric W. Weisstein, May 11 2007

Keywords

• nonn

Comments

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

Examples

			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
		

Links

• 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

Crossrefs

Row sums of A380363.

Cf. A000055, A005418, A058984, A130132, A331693, A363251.

Cf. k-linear trees for k = 1..4: A004250, A338706, A338707, A338708.

Programs

Mathematica

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

PARI

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

Extensions

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