A363251 Number of nonisomorphic open quipus with n nodes.

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,5

Comments

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

Links

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

Formula

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

Example

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:
     .   .
     |   |
   ._._._._.
       |
     ._._.

Mathematica

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

Crossrefs

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

Cf. A130131 (any maximum degree).

Sequence in context: A033961 A298163 A201542 * A000672 A129860 A115868

Adjacent sequences: A363248 A363249 A363250 * A363252 A363253 A363254

Keyword

nonn,easy

Author

Didrik Fosse, May 31 2023

Status

approved