OFFSET
4,1
COMMENTS
b(n) = ((n-4)*2^floor((n-1)/2)+2)*floor(n/2) is the number of exterior top arches for all semi-meander solutions with n top arches and floor(n/2) exterior top arches. Conjecture: for n>=5, lim_{n->oo} a(n)/b(n) = 3.
LINKS
Paolo Xausa, Table of n, a(n) for n = 4..1000
Michael LaCroix, Approaches to the Enumerative Theory of Meanders, 2003, pg. 31-31, Demonstrates arch splitting with semi-meander models.
Index entries for linear recurrences with constant coefficients, signature (1,7,-7,-18,18,20,-20,-8,8).
FORMULA
For n>2:
a(2*n) = (3*n-1)*((2*n-4)*2^(n-1) + 2) - (3*n-3)*((2*n-5)*2^(n-1) + 2) + a(2*n-1);
a(2*n+1) = 3*n*((2*n-3)*2^n + 2) - 3*n*((2*n-4)*2^(n-1) + 2) + a(2*n).
G.f.: 2*x^4*(5 + 12*x - 13*x^2 - 12*x^3 + 6*x^4)/((1 - x)^2*(1 + x)*(1 - 2*x^2)^3). - Stefano Spezia, Nov 07 2023
EXAMPLE
For n=5, the number of semi-meanders with 5 top arches and 2 exterior top arches is equal to A259689(5,2) = 6:
__ __
//\\ __ ____ //\\ __ ____
///\\\ __ //\\ / /\\ ///\\\ //\\ __ //\ \
/\////\\\\, //\\///\\\, /\//\//\\\, ////\\\\/\, ///\\\//\\, ///\\/\\/\
There are 12 exterior arches for the 6 solutions.
Solutions for generation n+1 using the exterior arch splitting algorithm:
__
//\\ __ ____
///\\\ __ //\\ __ /____\
////\\\\ __ //\\ ///\\\ //\\ __ // __\\ __ __
/\/////\\\\\,//\\///\\\/\,/\/\////\\\\,///\\\//\\/\,/\///\//\\\\,//\\/\//\\/\
__
//\\ __ ____
///\\\ __ //\\ __ /____\
////\\\\ //\\ __ ///\\\ __ //\\ //__ \\ __ __
/////\\\\\/\,/\///\\\//\\,////\\\\/\/\,/\//\\///\\\,////\\/\\\/\,/\//\\/\//\\
These 12 solutions have 34 exterior arches. Therefore a(5) = 34.
MATHEMATICA
LinearRecurrence[{1, 7, -7, -18, 18, 20, -20, -8, 8}, {10, 34, 78, 222, 362, 938, 1326, 3246, 4242}, 50] (* Paolo Xausa, May 28 2024 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Roger Ford, Oct 10 2023
STATUS
approved