A253062 Largest order of a rooted tree that does not contain a rooted caterpillar subtree of order n.

0, 1, 2, 3, 5, 7, 11, 16, 23, 34, 49, 70, 103, 148, 211, 310, 445, 634, 931, 1336, 1903, 2794, 4009, 5710, 8383, 12028, 17131, 25150, 36085, 51394, 75451, 108256, 154183, 226354, 324769, 462550, 679063, 974308, 1387651, 2037190, 2922925, 4162954, 6111571

Offset

1,3

Links

Table of n, a(n) for n=1..43.

Stephan Brandt, Janina Müttel, Dieter Rautenbach, The circumference of the square of a connected graph, Combinatorica 34 (2014), no. 5, 547--559. MR3276436.

Formula

See Maple code.

Conjectures from Colin Barker, Feb 21 2015: (Start)

a(n) = a(n-1)+3*a(n-3)-3*a(n-4) for n>10.

G.f.: -x^2*(x^8-x^7+x^6-x^5+x^4+x^3-x^2-x-1) / ((x-1)*(3*x^3-1)).

(End)

Maple

f:=proc(k, i)
if i=1 then (23*3^k-1)/2
elif i=2 then (33*3^k-1)/2
else (47*3^k-1)/2; fi;
end;
g:=proc(n) local r, s;
s := (n mod 3); if s=0 then s:=s+3; fi; r:=(n-s)/3;
f(r-2, s);
end;
a:=[0, 1, 2, 3, 5, 7, 11, 16, 23];
for n from 10 to 50 do a:=[op(a), g(n)]; od;

Crossrefs

Cf. A253063.

Sequence in context: A232481 A232482 A332062 * A117590 A308991 A326467

Adjacent sequences: A253059 A253060 A253061 * A253063 A253064 A253065

Keyword

nonn

Author

N. J. A. Sloane, Jan 21 2015

Status

approved