|
%I M1205 N0464 #189 Jun 16 2023 03:16:13
%S 1,1,2,4,10,24,66,174,504,1406,4210,12198,37378,111278,346846,1053874,
%T 3328188,10274466,32786630,102511418,329903058,1042277722,3377919260,
%U 10765024432,35095839848,112670468128,369192702554,1192724674590,3925446804750
%N Semi-meanders: number of ways a semi-infinite directed curve can cross a straight line n times.
%C For n > 1, the number of permutations of n letters without overlaps [Sade, 1949]. - _N. J. A. Sloane_, Jul 05 2015
%C Number of ways to fold a strip of n labeled stamps with leaf 1 on top. [Clarified by _Stéphane Legendre_, Apr 09 2013]
%C From _Roger Ford_, Jul 04 2014: (Start)
%C 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).
%C 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.
%C 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.
%C 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).
%C Example: semi-meanders a(5)=10.
%C (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]
%C (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].
%C (End)
%C From _Roger Ford_, Feb 23 2018: (Start)
%C For n>1, the number of semi-meanders with n top arches and k concentric starting arcs is a(n,k)= A000682(n-k).
%C /\ /\
%C Examples: a(5,1)=4 //\\ / \ /\
%C A000682(5-1)=4 ///\\\ / /\\ / \ /\ /\
%C /\////\\\\, /\//\//\\\, /\/\//\/\\, /\ //\\//\\
%C a(5,2)=2 /\ a(5,3)=1 /\
%C A000682(5-2)=2 /\ //\\ /\ /\ A000682(5-3)=1 //\\ /\
%C //\\///\\\, //\\//\\/\ ///\\\//\\
%C a(5,4)=1 /\
%C A000682(5-4)=1 //\\
%C ///\\\
%C ////\\\\/\. (End)
%C 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
%C From _Martin Philp_, Mar 25 2021: (Start)
%C 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:
%C 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.
%C Hence, for n >= 2, a(n-1) is the number of stamp foldings having 1 and 2 (in this order) on top.
%C 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).
%C (End)
%C 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
%D A. Sade, Sur les Chevauchements des Permutations, published by the author, Marseille, 1949.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H I. Jensen, <a href="/A000682/b000682.txt">Table of n, a(n) for n = 1..45</a>
%H CombOS - Combinatorial Object Server, <a href="http://combos.org/meander">Generate meanders and stamp foldings</a>
%H P. Di Francesco, O. Golinelli and E. Guitter, <a href="https://arxiv.org/abs/hep-th/9506030">Meander, folding and arch statistics</a>, arXiv:hep-th/9506030, 1995.
%H P. Di Francesco, O. Golinelli and E. Guitter, <a href="http://arXiv.org/abs/hep-th/9607039">Meanders: a direct enumeration approach</a>, arXiv:hep-th/9607039, 1996; Nucl. Phys. B 482 [ FS ] (1996) 497-535.
%H P. Di Francesco, <a href="http://arXiv.org/abs/math-ph/9911002">Matrix model combinatorics: applications to folding and coloring</a>, arXiv:math-ph/9911002, 1999.
%H I. Jensen, <a href="http://www.ms.unimelb.edu.au/~iwan/">Home page</a>
%H I. Jensen, <a href="https://web.archive.org/web/20190419141113/https://researchers.ms.unimelb.edu.au/~ij@unimelb/meanders/series/semi.meanders.ser">Terms a(1)..a(45)</a>
%H I. Jensen, <a href="http://dx.doi.org/10.1088/0305-4470/33/34/301">A transfer matrix approach to the enumeration of plane meanders</a>, J. Phys. A 33, 5953-5963 (2000).
%H I. Jensen and A. J. Guttmann, <a href="http://dx.doi.org/10.1088/0305-4470/33/21/101">Critical exponents of plane meanders</a> J. Phys. A 33, L187-L192 (2000).
%H J. E. Koehler, <a href="http://dx.doi.org/10.1016/S0021-9800(68)80048-1">Folding a strip of stamps</a>, J. Combin. Theory, 5 (1968), 135-152.
%H J. E. Koehler, <a href="/A001011/a001011_4.pdf">Folding a strip of stamps</a>, J. Combin. Theory, 5 (1968), 135-152. [Annotated, corrected, scanned copy]
%H M. La Croix, <a href="http://www.math.uwaterloo.ca/~malacroi/Latex/Meanders.pdf"> Approaches to the Enumerative Theory of Meanders</a>
%H Stéphane Legendre, <a href="http://arxiv.org/abs/1302.2025">Foldings and Meanders</a>, arXiv preprint arXiv:1302.2025 [math.CO], 2013.
%H Stéphane Legendre, <a href="/A000682/a000682.pdf">Illustration of initial terms</a>
%H W. F. Lunnon, <a href="http://dx.doi.org/10.1090/S0025-5718-1968-0221957-8">A map-folding problem</a>, Math. Comp. 22 (1968), 193-199.
%H A. Panayotopoulos, P. Vlamos, <a href="https://doi.org/10.1007/s11786-015-0234-0">Partitioning the Meandering Curves</a>, Mathematics in Computer Science (2015) p 1-10.
%H Albert Sade, <a href="/A000108/a000108_17.pdf">Sur les Chevauchements des Permutations</a>, published by the author, Marseille, 1949. [Annotated scanned copy]
%H J. Sawada and R. Li, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p43">Stamp foldings, semi-meanders, and open meanders: fast generation algorithms</a>, Electronic Journal of Combinatorics, Volume 19 No. 2 (2012), P#43 (16 pages).
%H J. Touchard, <a href="http://dx.doi.org/10.4153/CJM-1950-035-6">Contributions à l'étude du problème des timbres poste</a>, Canad. J. Math., 2 (1950), 385-398.
%H <a href="/index/Fo#fold">Index entries for sequences obtained by enumerating foldings</a>
%F For n >= 2, a(n) = 2^(n-2) + Sum_{x=3..n-2} (2^(n-x-2)*A301620(x)). - _Roger Ford_, Apr 23 2018
%F 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
%F a(n) = A000136(n)/n. - _Jean-François Alcover_, Sep 06 2019, from formula in A000136.
%e 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.
%t A000136 = Import["https://oeis.org/A000136/b000136.txt", "Table"][[All, 2]];
%t a[n_] := A000136[[n]]/n;
%t Array[a, 45] (* _Jean-François Alcover_, Sep 06 2019 *)
%Y A000560(n) = a(n+1)/2 (for n >= 2) gives number of nonisomorphic solutions (see also A086441).
%Y Cf. A000136, A001011, A001997.
%Y Row sums of A259689.
%K nonn,nice
%O 1,3
%A _N. J. A. Sloane_
%E Sade gives the first 11 terms. Computed to n = 45 by Iwan Jensen.
%E Offset changed by _Roger Ford_, Feb 09 2018
|
