A366415 a(n) is the number of exterior top arches (no covering arch) for semi-meanders in generation n+1 that are generated by semi-meanders with n top arches and floor(n/2) exterior top arches using the exterior arch splitting algorithm.
10, 34, 78, 222, 362, 938, 1326, 3246, 4242, 10002, 12438, 28566, 34330, 77338, 90654, 201246, 231458, 507938, 575526, 1251366, 1400874, 3022890, 3350574, 7184430, 7897138, 16842802, 18382902, 39026742, 42336314, 89522234, 96600126, 203554878
Offset: 4
Examples
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.
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).
Programs
-
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 *)
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
Comments