A262258 a(n) = the number of hills (arch length of 1 with no covering arches) for semi-meander solutions with n arches and floor((n+2)/2) arch group returns to the x axis.

1, 2, 2, 4, 6, 10, 16, 24, 40, 56, 96, 128, 224, 288, 512, 640, 1152, 1408, 2560, 3072, 5632, 6656, 12288, 14336, 26624, 30720, 57344, 65536, 122880, 139264, 262144, 294912, 557056, 622592, 1179648, 1310720, 2490368, 2752512, 5242880, 5767168, 11010048, 12058624

Offset

1,2

Comments

From Roger Ford, May 06 2016: (Start)

2^floor((n-1)/2)= number of semi-meander solutions with semi-length n and floor((n+2)/2) arch groupings. A.Sade, Sur les Chevauchements des Permutations, 1949.

2^floor((n-1)/2)*n= total lengths of all arch groups for semi-meanders with length n and floor((n+2)/2) in each solution.

a(1)-a(n)= number of specific length arch groups, for all semi-meander solutions with length n and floor((n+2/2) arch groups in each solution.

Example: Semi-meander n=6, arch groupings in each solution = 4.

/\ /\

/\ /\ / \ /\ /\ / \

/\-//\\-/\-//\\ /\-/\-/\-//\/\\ //\\-/\-//\\-/\ //\/\\-/\-/\-/\

a(2)=2 arch groups length 3, a(4)=4 arch groups length 2,

a(6)= 10 arch groups length 1.

a(2)*3 + a(4)*2 + a(6)*1= 2*3 + 4*2 + 10*1 = 24 total arch groups.

In general for n an even number:

n*2^(floor((n-1)/2) = a(2)*(floor(n/2))+ a(4)*(floor (n/2)-1)+ a(6)*(floor(n/2)-2)+...+ a(n).

In general for n an odd number:

n*(floor((n-1)/2) = a(2)*(floor((n+1)/2)+a(4)*(floor((n+1)/2)-1)+a(6)*(floor((n+1)/2)-2)+...+ a(n-1)*2+ a(n). (End)

Links

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

Albert Sade, Sur les Chevauchements des Permutations, published by the author, Marseille, 1949. [Annotated scanned copy]

Formula

a(1)=1, a(2)=2, a(n) = (2^floor((n-1)/2)*(floor(n/2)-(1/2)*(floor((n-3)/2)) for n>2.

Conjectures from Colin Barker, May 06 2016: (Start)

a(n) = 2^(n/2-3)*(n+4) for n>2 and even.

a(n) = 2^((n-9)/2)*(4*n+4) for n>2 and odd.

a(n) = 4*a(n-2)-4*a(n-4) for n>6.

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

(End)

Example

For n=5 arches and floor((5+2)/2) = 3 arch group returns,  there are the following semi-meander solutions with /\ denoting a hill and - a return to axis.
        /\                    /\
       /  \                  /  \
/\-/\-//\/\\- = 2 hills     //\/\\-/\-/\- = 2 hills
    /\   /\                  /\   /\
/\-//\\-//\\- = 1 hill      //\\-//\\-/\- = 1 hill
There are 6 hills, so a(5)=6.

Mathematica

f[n_] := Ceiling[2^Floor[(n - 1)/2]*(Floor[n/2] - Floor[(n - 3)/2]/2)]; Array[f, 42] (* Robert G. Wilson v, Sep 16 2015 *)

Prog

(Magma) [1, 2] cat [Ceiling(2^Floor((n-1)/2)*(Floor(n/2)- Floor((n-3)/2)/2)): n in [3..45]]; // Vincenzo Librandi, Sep 17 2015

Crossrefs

Sequence in context: A050194 A288006 A228807 * A293633 A006355 A055389

Adjacent sequences: A262255 A262256 A262257 * A262259 A262260 A262261

Keyword

nonn

Author

Roger Ford, Sep 16 2015

Status

approved