|
|
A000682
|
|
Semi-meanders: number of ways a semi-infinite directed curve can cross a straight line n times.
(Formerly M1205 N0464)
|
|
34
|
|
|
1, 1, 2, 4, 10, 24, 66, 174, 504, 1406, 4210, 12198, 37378, 111278, 346846, 1053874, 3328188, 10274466, 32786630, 102511418, 329903058, 1042277722, 3377919260, 10765024432, 35095839848, 112670468128, 369192702554, 1192724674590, 3925446804750
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
For n > 1, the number of permutations of n letters without overlaps [Sade, 1949]. - N. J. A. Sloane, Jul 05 2015
Number of ways to fold a strip of n labeled stamps with leaf 1 on top. [Clarified by Stéphane Legendre, Apr 09 2013]
The number of semi-meander solutions for n (a(n)) is equal to the number of n top arch solutions in the intersection of A001263 (with no intersecting top arches) and A244312 (arches forming a complete loop).
The top and bottom arches for semi-meanders pass through vertices 1-2n on a straight line with the arches below the line forming a rainbow pattern.
The number of total arches going from an odd vertex to a higher even vertex must be exactly 2 greater than the number of arches going from an even vertex to a higher odd vertex to form a single complete loop with no intersections.
The arch solutions in the intersection of A001263 (T(n,k)) and A244312 (F(n,k)) occur when the number of top arches going from an odd vertex to a higher even vertex (k) meets the condition that k = ceiling((n+1)/2).
Example: semi-meanders a(5)=10.
(A244312) F(5,3)=16 { 10 common solutions: [12,34,5 10,67,89] [16,23,45,78,9 10] [12,36,45,7 10,89] [14,23,58,67,9 10] [12,3 10,49,58,67] [18,27,36,45,9 10] [12,3 10,45,69,78] [18,25,34,67,9 10] [14,23,5 10,69,78] [16,25,34,7 10,89] } + [18,27,34,5 10,69] [16,25,3 10,49,78] [18,25,36,49,7 10] [14,27,3 10,58,69] [14,27,36,5 10,89] [16,23,49,58,7 10]
(A001263) T(5,3)=20 { 10 common solutions } + [12,38,45,67,9 10] [1 10,29,38,47,56] [1 10,25,34,69,78] [14,23,56,7 10,89] [12,3 10,47,56,89] [18,23,47,56,9 10] [1 10,29,36,45,78] [1 10,29,34,58,67] [1 10,27,34,56,89] [1 10,23,49,56,78].
(End)
For n>1, the number of semi-meanders with n top arches and k concentric starting arcs is a(n,k)= A000682(n-k).
/\ /\
Examples: a(5,1)=4 //\\ / \ /\
A000682(5-1)=4 ///\\\ / /\\ / \ /\ /\
/\////\\\\, /\//\//\\\, /\/\//\/\\, /\ //\\//\\
a(5,2)=2 /\ a(5,3)=1 /\
//\\///\\\, //\\//\\/\ ///\\\//\\
a(5,4)=1 /\
///\\\
////\\\\/\. (End)
For n >= 4, 4*a(n-2) is the number of stamp foldings with leaf 1 on top, with leaf 2 in the second or n-th position, and with leaf n and leaf n-1 adjacent. Example for n = 5, 4*a(5-2) = 8: 12345, 12354, 12453, 12543, 13452, 13542, 14532, 15432. - Roger Ford, Aug 05 2019
The condition of having leaf n and leaf n-1 adjacent is the same as having one fewer leaf, and then counting each element twice. So the above comment is equivalent to saying:
For n >= 3, 2*a(n-1) is the number of stamp foldings with leaf 1 on top and leaf 2 in the second or n-th position. Example for n = 4, 2*a(4-1) = 4: 1234, 1243, 1342, 1432. Furthermore the number of stamp foldings with leaf 1 on top and leaf 2 in the n-th position is the same as the number of stamp foldings with leaf 1 on top and leaf 2 in the second position, as a cyclic rotation of 1 and mirroring the sequence maps one to the other. 1234, 1243 <-rot-> 2341, 2431 <-mirror-> 1432, 1342.
Hence, for n >= 2, a(n-1) is the number of stamp foldings having 1 and 2 (in this order) on top.
Not only is a(n) the number of stamp foldings with 1 on top, it is the number of stamp foldings with any particular leaf on top. This explains why A000136(n)= n*a(n).
(End)
The number of semi-meanders that in the first exterior top arch has exactly one arch of length one = Sum_{k=1..n-1} a(k). Example: for n = 5, Sum_{k=1..4} A000682(k) = 8, 10 = arch of length one, *start and end of first exterior top arch*; *10*11001100, *10*11110000, *10*11011000, *10*10110100, *1100*111000, *1100*110010, *111000*1100, *11110000*10. - Roger Ford, Jul 12 2020
|
|
REFERENCES
|
A. Sade, Sur les Chevauchements des Permutations, published by the author, Marseille, 1949.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
For n >= 2, a(n) = 2^(n-2) + Sum_{x=3..n-2} (2^(n-x-2)*A301620(x)). - Roger Ford, Apr 23 2018
a(n) = 2^(n-2) + Sum_{j=4..n-1} (Sum_{k=3..floor((j+2)/2)} (A259689(j,k)*(k-2)*2^(n-1-j))). - Roger Ford, Dec 12 2018
|
|
EXAMPLE
|
a(4) = 4: the four solutions with three crossings are the two solutions shown in A086441(3) together with their reflections about a North-South axis.
|
|
MATHEMATICA
|
A000136 = Import["https://oeis.org/A000136/b000136.txt", "Table"][[All, 2]];
|
|
CROSSREFS
|
A000560(n) = a(n+1)/2 (for n >= 2) gives number of nonisomorphic solutions (see also A086441).
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Sade gives the first 11 terms. Computed to n = 45 by Iwan Jensen.
|
|
STATUS
|
approved
|
|
|
|