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

A130131 Number of n-lobsters.

Original entry on oeis.org

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

Views

Author

Eric W. Weisstein, May 11 2007

Keywords

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

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

A300576 Number of nights required in the worst case to find the princess in a castle with n rooms arranged in a line (Castle and princess puzzle).

Original entry on oeis.org

1, 2, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122
Offset: 1

Views

Author

Dmitry Kamenetsky, Mar 09 2018

Keywords

Comments

This is a logic puzzle. There is a castle with n rooms arranged in a line. The princess living in the castle sleeps in a different room each night, but always one adjacent to the one in which she slept on the previous night. She is free to choose any room in which to sleep on the first night. A prince would like to find the princess, but she will not tell him where she is going to sleep each night. Each night the prince can look in a single room. What strategy should he follow in order to guarantee that he finds the princess in a minimum number of nights?
The strategy to find the princess guaranteed within a(n) nights takes on average k(n) nights until the princess is found with lim_{n->oo} k(n) = n-1.5. For n>4, strategies with lower average numbers of trials exist; A386462 provides this strategy for n=8. See there for more information. - Ruediger Jehn, Aug 05 2025
Christian Perfect (see link) considered the case when the rooms are arranged as a general graph. He showed that the set of solvable graphs is exactly the set of trees not containing the "threesy" subgraph, which is A130131. He also showed that for d-level binary trees with 1 <= d <= 4 the number of required nights is 1, 2, 6, 18. Binary trees with d >= 5 are unsolvable as they contain "threesy".

Examples

			For n = 1, there is only one room to search, so a(1) = 1.
For n = 2, the prince searches room 1 on the first night. If the princess is not there that means she was in room 2. If the prince searches room 1 again then he is guaranteed to see the princess as she has to move from room 2 to room 1 (she cannot stay in the same room). So a(2) = 2.
For n = 3, the prince searches room 2 on the first night. If the princess is not there that means she was either in room 1 or 3. On the second night she must go to room 2 and this is where the prince will find her. So a(3) = 2.
For n = 4, a solution that guarantees to find the princess in a(4)=4 nights is to search rooms (2,3,3,2).
For n = 5, a solution that guarantees to find the princess in a(5)=6 nights is to search rooms (2,3,4,4,3,2).
In the general case for n >= 3, a solution guaranteeing success in the minimum number of nights is to search rooms (2,3,...,n-1,n-1,...,3,2), so a(n) = 2*n - 4.

Links

Crossrefs

Essentially the same as A005843, A004277 and A004275.
Cf. A130131, A130132, A331693, A386462.

Programs

  • Mathematica
    CoefficientList[ Series[(2x^3 - x^2 + 1)/(x - 1)^2, {x, 0, 62}], x] (* Robert G. Wilson v, Mar 12 2018 *)
Join[{1,2},Range[2,200,2]] (* Harvey P. Dale, Jan 25 2019 *)

Formula

For n >= 3, a(n) = 2*n - 4.
From Chai Wah Wu, Apr 14 2024: (Start)
a(n) = 2*a(n-1) - a(n-2) for n > 4.
G.f.: x*(2*x^3 - x^2 + 1)/(x - 1)^2. (End)
E.g.f.: 4 + 2*exp(x)*(x - 2) + 3*x + x^2. - Stefano Spezia, Aug 15 2025

A130132 Number of trees on n vertices which are not lobsters.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 4, 19, 77, 287, 1002, 3365, 10853, 34088, 104574, 315116, 935321, 2743374, 7966723, 22951010, 65681536, 186961873, 529845497, 1496245171, 4213181063, 11836671278, 33195092417, 92966480736
Offset: 1

Views

Author

Eric W. Weisstein, May 11 2007

Keywords

Comments

Also the number of nonlinear trees on n nodes. - Andrew Howroyd, Dec 17 2020

Links

Crossrefs

Cf. A000055, A130131, A331693.

Formula

a(n) = A000055(n) - A130131(n). - Andrew Howroyd, Nov 02 2017

Extensions

a(15)-a(32) from Washington Bomfim, Feb 23 2011
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.