A130131 -id:A130131 - cp's OEIS frontend

A277796 Erroneous version of A130131.

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 105, 231, 537

Offset: 0

dead

A338355 Erroneous version of A130131.

1, 1, 1, 2, 3, 6, 11, 23, 47, 105, 231, 532, 1254, 2872, 6739, 15955, 37776, 89779, 213381, 507949, 1209184, 2880382, 6861351, 16348887, 38955354

Offset: 1

R. J. Mathar, Aug 05 2024

dead

Included in accordance with OEIS policy of including published but erroneous sequences to serve as pointers to the correct values.

Wakhare, Tanay, Eric Wityk, and Charles R. Johnson. "The proportion of trees that are linear." Discrete Mathematics 343.10 (2020): 112008. Also arXiv:1901.08502v2. See Tables 1 and 2 (but beware errors).

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

Dmitry Kamenetsky, Mar 09 2018

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

			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.

Christian Perfect, Solving the princess on a graph puzzle.
Puzzling Stack Exchange, Why does this solution guarantee that the prince knocks on the right door to find the princess?.
standupmaths, Youtube, The Castle and the Princess Puzzle.
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Essentially the same as A005843, A004277 and A004275.

Cf. A130131, A130132, A331693, A386462.

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

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

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

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

Eric W. Weisstein, May 11 2007

nonn

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

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

Cf. A000055, A130131, A331693.

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

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

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

A338708 Number of 4-linear trees on n nodes.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6, 37, 158, 591, 1896, 5537, 14812, 37133, 87841, 198267, 429199, 896731, 1814978, 3572810, 6858774, 12874977, 23679669, 42752787, 75887244, 132618635, 228443753, 388297169, 651868064, 1081771385, 1775876764, 2885944062, 4645393253, 7410678577, 11722238660, 18394159344

Offset: 1

N. J. A. Sloane, Nov 05 2020

nonn

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=4 of A380363.

Cf. A000041, A130131, A338706, A338707.

seq(n)={my(A=O(x^(n-5)), p=1/eta(x + A), p2=1/eta(x^2 + A)); Vec(((p - 1/(1-x))^2*(p - 1)^2/(1 - x)^3 + (p2 - 1/(1 - x^2))*(p2 - 1)/((1 - x^2)*(1 - x)))/2, -n)} \\ Andrew Howroyd, Jan 26 2025

G.f.: x^4*((P(x) - 1/(1 - x))^2*(P(x) - 1)^2/(1 - x)^3 + (P(x^2) - 1/(1 - x^2))*(P(x^2) - 1)/((1 - x^2)*(1 - x)))/2 where P(x) is the g.f. of A000041. - Andrew Howroyd, Jan 26 2025

a(26) onwards from Andrew Howroyd, Jan 26 2025

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]))}

A331693 Number of Tom graphs with n vertices.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 328, 705, 1576, 3551, 8179, 18980, 44559, 105111, 249426, 593484, 1416269, 3384581, 8099819, 19398194, 46487665, 111447044, 267260387, 641022947, 1537706522, 3688974818, 8850411933, 21234093757, 50946316856, 122234742311

Offset: 0

Bobby Jacobs, Jan 24 2020

nonn

This sequence is from a Project Euler problem called "Tom and Jerry". A cat named Tom and a mouse named Jerry play a game on a graph G. Each vertex of G is a mousehole. Jerry starts in one of the vertices. Every day, Tom tries to catch Jerry in one of the holes. If there is a vertex adjacent to Jerry's hole, then Jerry moves to one of the adjacent holes. A Tom graph is a graph on which Tom can always catch Jerry by following a sequence of holes.
All Tom graphs are loop-free graphs, but not all loop-free graphs are Tom graphs. The smallest loop-free graph that is not a Tom graph has 10 vertices:
        1
        |
        2
        |
        3
        |
        4
       / \
      5   8
     /     \
    6       9
   /         \
  7           10
From Hugo Pfoertner, Feb 20 2020 (Start):
The sequence is an equivalent of A005195 (number of forests with n unlabeled nodes), but made from trees that don't have the unlabeled 10-node graph shown above as a subgraph. This is described in the comment of A300576 and there is also a link to Christian Perfect's website.
In order to find a term of the current sequence, the number of trees containing the shown subgraph must be subtracted from the total number A000055. For n = 10 this is exactly one, for n = 11 it is trivially 4 and for n = 12 it is 19 (A130132).
The marked illustrations from the Steinbach graph catalog show these manually counted tree graphs.
The formulas of A005195 (Euler transform) can then be used to calculate the number of forests if the reduced number of trees A130131 is used instead of A000055. (End)
a(0) = 1: the empty graph is a Tom graph, since Jerry cannot hide from Tom. - Rainer Rosenthal, Mar 01 2020

			The graph
  1---2---3
is a Tom graph: Tom can follow the sequence 2, 2 to guarantee that he catches Jerry.
The graph
    1
   / \
  2---3
is not a Tom graph: Jerry always has 2 vertices to go to, and whatever vertex Tom picks, Jerry can choose another to evade Tom.

Seiichi Manyama, Table of n, a(n) for n = 0..2000
Project Euler, Problem 690: Tom and Jerry
Peter Steinbach, Simple Graphs - Trees, illustrations of the graphs, including an added marking of the relevant 4 cases for 11 nodes.
Peter Steinbach, Simple Graphs - Trees, illustrations of the graphs, including an added marking of the relevant 19 cases for 12 nodes.

Cf. A000055, A005195, A130131, A130132, A300576.

a(n) <= A005195(n) with equality only for n in {1, ..., 9}.

a(11)-a(12) from Hugo Pfoertner, Feb 20 2020

a(0), a(13)-a(33) from Rainer Rosenthal, Feb 29 2020

A363251 Number of nonisomorphic open quipus with n nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 6, 11, 18, 36, 64, 127, 241, 480, 935, 1868, 3688, 7373, 14655, 29305, 58432, 116859, 233367, 466727, 932761, 1865513, 3729648, 7459286, 14915826, 29831640, 59657802, 119315589, 238620236, 477240456, 954459044, 1908918069, 3817792423

Offset: 0

Didrik Fosse, May 31 2023

An open quipu is a tree of maximal valency 3 such that all nodes of degree 3 lie on a path.

			The 4 open quipus with 6 nodes are:
  ._._._._._.   ._._._._.   ._._._._.   ._._._.
                  |             |         | |
The smallest interesting nonexample, a 3-valent tree where the nodes of degree 3 do not lie on a path, is:
     .   .
     |   |
   ._._._._.
       |
     ._._.

Paolo Xausa, Table of n, a(n) for n = 0..1000
Renee Woo and Arnold Neumaier, On Graphs Whose Spectral Radius is Bounded by 3/2*sqrt(2), Graphs and Combinatorics 23 (2007), 713-726. Also preprint and slides.
Index entries for linear recurrences with constant coefficients, signature (2,3,-5,-3,-1,3,7,0,-1,-6,-2,4).

A000672 minus the trees where the nodes of degree 3 do not lie on a path.

Cf. A130131 (any maximum degree).

LinearRecurrence[{2,3,-5,-3,-1,3,7,0,-1,-6,-2,4},{1,1,1,1,2,2,4,6,11,18,36,64,127},50] (* Paolo Xausa, Aug 13 2023 *)

G.f.: (1 - x - 4*x^2 + x^3 + 5*x^4 + 4*x^5 - 4*x^7 - 6*x^8 - 3*x^9 + 5*x^10 + 4*x^11 - x^12)/((1 - x)^3*(1 + x)^2*(1 - 2*x)*(1 + x^2)*(1 + x + x^2)*(1 - 2*x^2)). - Andrew Howroyd, May 31 2023

cp's OEIS Frontend

A277796 Erroneous version of A130131.

Views

Author

Keywords

A338355 Erroneous version of A130131.

Views

Author

Keywords

Comments

Links

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A338706 Number of 2-linear trees on n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A338707 Number of 3-linear trees on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A338708 Number of 4-linear trees on n nodes.

Views

Author

Keywords

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

A331693 Number of Tom graphs with n vertices.

Views

Author

Keywords

Comments

Examples