cp's OEIS Frontend

A130131 Number of n-lobsters.

%I A130131 #49 Jan 26 2025 21:47:51
%S A130131 1,1,1,2,3,6,11,23,47,105,231,532,1224,2872,6739,15955,37776,89779,
%T A130131 213381,507949,1209184,2880382,6861351,16348887,38955354,92831577,
%U A130131 221219963,527197861,1256385522,2994200524,7135736613,17005929485,40528629737,96588403995,230190847410
%N A130131 Number of n-lobsters.
%C A130131 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
%H A130131 Andrew Howroyd, <a href="/A130131/b130131.txt">Table of n, a(n) for n = 1..200</a>
%H A130131 Andrew Howroyd, <a href="/A130131/a130131.txt">Formula for number of lobsters</a>
%H A130131 G. Li and F. Ruskey, <a href="http://theory.cs.uvic.ca/dis/distribute.pl.cgi?package=FreeTree.c">C program</a> [dead link]
%H A130131 Tanay Wakhare, Eric Wityk, and Charles R. Johnson, <a href="https://doi.org/10.1016/j.disc.2020.112008">The proportion of trees that are linear</a>, Discrete Mathematics 343.10 (2020): 112008. Also <a href="https://doi.org/10.1016/j.disc.2020.112284">Corrigendum</a> and preprint <a href="https://arxiv.org/abs/1901.08502">arXiv:1901.08502</a>. See Tables 1 and 2 (but beware errors).
%H A130131 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LobsterGraph.html">Lobster Graph</a>
%e A130131 a(10) = 105 = A000055(10) - 1 because all trees with 10 vertices are lobsters except this one:
%e A130131     o-o-o
%e A130131    /
%e A130131   o-o-o-o
%e A130131    \
%e A130131     o-o-o
%e A130131 Also, all trees with 10 vertices are linear (all vertices of degree >2 belong to a single path) except this one:
%e A130131      o   o
%e A130131       \ /
%e A130131        o
%e A130131        |
%e A130131        o
%e A130131      /   \
%e A130131     o     o
%e A130131    / \   / \
%e A130131   o   o o   o
%t A130131 eta = QPochhammer;
%t A130131 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))];
%t A130131 CoefficientList[s[32], x] // Rest (* _Jean-François Alcover_, Nov 17 2020, after _Andrew Howroyd_ *)
%o A130131 (PARI)
%o A130131 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))}
%o A130131 Vec(s(30)) \\ _Andrew Howroyd_, Nov 02 2017
%Y A130131 Row sums of A380363.
%Y A130131 Cf. A000055, A005418, A058984, A130132, A331693, A363251.
%Y A130131 Cf. k-linear trees for k = 1..4: A004250, A338706, A338707, A338708.
%K A130131 nonn
%O A130131 1,4
%A A130131 _Eric W. Weisstein_, May 11 2007
%E A130131 a(15)-a(32) from _Washington Bomfim_, Feb 23 2011