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

Author

Didrik Fosse, May 31 2023

Keywords

• nonn
• easy

Comments

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

Examples

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

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

Crossrefs

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

Cf. A130131 (any maximum degree).

Programs

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

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