{'fraction_non_alphanumeric': 0.058433191599020745, 'fraction_numerical': 0.015590774384744235, 'mean_word_length': 3.983092562867844, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Meanders: A Direct Enumeration Approach

We study the statistics of semi-meanders, i.e. configurations of a set of roads crossing a river through n bridges, and possibly winding around its source, as a toy model for compact folding of polymers. By analyzing the results of a direct enumeration up to n=29, we perform on the one hand a large n extrapolation and on the other hand we reformulate the available data into a large q expansion, where q is a weight attached to each road. We predict a transition at q=2 between a low-q regime with irrelevant winding, and a large-q regime with relevant winding.


Introduction
The meander problem is a simply stated combinatorial question: count the number of configurations of a closed non-self-intersecting road crossing an infinite river through a given number of bridges. Despite its apparent simplicity, this problem still awaits a solution, if only for asymptotics when the number of bridges is large. The problem emerged in various contexts ranging from mathematics to computer science [1]. In particular, Arnold re-actualized it in connection with Hilbert's 16th problem, namely the enumeration of ovals of planar algebraic curves [2], and it also appears in the classification of 3-manifolds [3].
Remarkably, the meander problem can be rephrased in the physical language of critical phenomena, through its equivalence with a particular problem of Self-Avoiding Walks: the counting of the compact foldings of a linear chain.
Several techniques have been applied to this problem: direct combinatorial approaches [4] [5], random matrix model techniques [6] [7] [8], an algebraic approach using the Temperley-Lieb algebra and Restricted Solid-On-Solid models [9]. Several exact results have been obtain on the way for meander-related issues, including exact sum rules for meandric numbers [7], the solution of the somewhat simpler irreducible meander problem [6] [7], and the calculation of a meander-related determinant [9] [3].
The present paper is dedicated to a more direct enumerative approach and a thorough analysis of its results in the spirit of critical phenomena. The meander problem is generalized to include the case of several non-intersecting but possibly interlocking roads with a weight q per road. The corresponding generating functions are analyzed as functions of q. In particular, we derive their large q asymptotic expansion in powers of 1/q. The paper is organized as follows. In sect.2, we give the basic definitions of meanders and semi-meanders (which correspond to the same problem with a semi-infinite river with a source, around which the roads are free to wind), as well as some associated observables such as the winding. We further give exact solutions to the meander and semi-meander problems at two particular values of q: q = 1, where they reduce to a random walk problem, and q = ∞, dominated by simple configurations. In sect.3, we explain how to enumerate the semi-meanders for arbitrary number n of bridges, using a fundamental recursive construction. After implementation on a computer, this procedure allowed us to find the semi-meander numbers with up to n = 29 bridges. These data are presented and then analyzed by a direct large n extrapolation. On the way we also confirm the scaling hypotheses borrowed from the theory of critical phenomena. Evidence is found for a phase transition for semi-meanders at a value of q = q c ≃ 2 between a low-q and a large-q regimes, discriminated by the relevance of winding around the source. In sect.4, we show how to use the above data to generate a large-q expansion for most of the interesting quantities. This expansion provides an accurate description of the whole q > q c phase. In sect.5, we analyze the break-down of this expansion, which gives rise to the q < q c phase.
Sect.6 briefly describes the small-q expansion of the problem. We gather our conclusions in sect.7. The more technical details are left in appendices.

Definitions, observables
A meander of order n is a planar configuration of a non-self-intersecting loop (road) crossing a line (river), through a given number 2n of points (bridges). We consider as equivalent any two configurations which may be continuously deformed into each other, keeping the river fixed (this is therefore a topological equivalence). The number of inequivalent meanders of order n is denoted by M n . For instance, we have M 1 = 1, M 2 = 2, M 3 = 8... More numbers can be found in [6] [7] [10].
We stumbled on the meander problem by trying to enumerate the distinct compact folding configurations of a closed polymer, i.e. the different ways of folding a closed chain of 2n identical constituents onto itself. The best image of such a closed polymer is that   When the strip of stamps is open (see Fig.2), we decide to attach the first stamp to a support, preventing the strip from winding around it, while the last stamp has a free extremal edge. In this case, a slightly generalized transformation maps any compactly folded open configuration of (n − 1) stamps to what we will call a semi-meander configuration of order n, in the following manner. (c) the result is a semi-meander configuration of order 5, namely that of a road, crossing a semi-infinite river through 5 bridges (the source of the river, around which the road is free to wind, is indicated by an asterisk).
As shown in Fig.3, draw a curve (road) though the (n − 1) centers (bridges) of all the piled-up stamps, then close this curve across the support (this last intersection is the n-th bridge), and pull the free edge of the last stamp in order to form a straight half-line (river with a source). The resulting picture is a configuration of a road (the curve) crossing a semi-infinite river (stamps and support) through n bridges: this is called a semi-meander configuration of order n. Note that the road in a semi-meander may wind freely around the source of the river, and that consequently the number of bridges may be indifferently even or odd, as opposed to meanders. The number of distinct semi-meanders of order n is denoted byM n . For instance, we haveM 1 = 1,M 2 = 1,M 3 = 2,M 4 = 4... More numbers can be found in [4] [7] and in appendix A.
Through its compact folding formulation, the semi-meander problem is a particular reduction of the two-dimensional self-avoiding walk problem, in which only topological constraints are retained. It is therefore natural to define, by analogy with self-avoiding walks the connectivityR per stamp and the configuration exponent γ which determine the large n behavior of the semi-meander numbers as follows 1  The "end-to-end distance" of the folded strip of stamps (a) is the number (w = 1 here) of stamps to be added to the strip (the added stamp is represented in dashed line), so that the new free end (empty circle) is in contact with the infinity to the right. This coincides with the "winding" of the corresponding semi-meander (b), namely the number of bridges to be added if we continue the river to the right of its source (dashed line). 1 That the semi-meander numbersM n actually have these leading asymptotics may be proved by deriving upper and lower bounds onR. See [7] for further details.
A natural observable for self-avoiding walks is the end-to-end distance. The corresponding notion for a compactly folded open strip of stamps is the "distance" between the free end of the strip and, say the support. This distance should also indicate how far the end of the strip is buried inside the folded configuration. It is defined as the minimal length w of a strip of stamps to be attached to the free end, such that a resulting folding with n − 1 + w stamps has its free end outside of the folding, namely can be connected to the infinity to the right of the folding by a half-line which does not intersect any stamp.
Indeed, the infinity to the right can be viewed as the nearest topological neighbor of the support, hence w measures a distance from the free end of the strip to the support. This is illustrated in Fig.4(a), with n = 5 and w = 1. In the semi-meander formulation (see Fig.4(b)), this distance w is simply the winding of the road around the source of the river, namely the number of bridges to be added if we continue the river to the right of its source. By analogy with self-avoiding walks, we expect the average winding over all the semi-meanders of order n to have the leading behavior where ν is some positive (end-to-end) exponent 0 ≤ ν ≤ 1, as w is always smaller or equal to n.
In this language, a meander of order n is simply a semi-meander of order 2n with winding w = 0. By analogy with closed (as compared to open) self-avoiding walks, we expect the asymptotics where the connectivity per bridge R is the same as that for semi-meanders (2.1), R =R, and the configuration exponent α = γ is characteristic of the closed boundary condition on the strip of stamps.
In the following, we will mainly focus our study on the semi-meander numbers.

Arches and connected components
Any semi-meander may be viewed as a particular meander by opening the semi-infinite river as indicated by the arrows on Fig.5. In the process, the number of bridges is doubled, hence the order is conserved. The resulting meander however is very peculiar. Note that in general a meander is made of an upper (resp. lower) configuration consisting of nonintersecting arches (arcs of road) connecting the bridges by pairs above (resp. below) the

Fig. 5:
A semi-meander viewed as a particular meander: the semi-infinite river must be opened up as indicated by the arrows. This doubles the number of bridges in the resulting meander, hence the order is conserved (n = 5 here). By construction, the lower arch configuration of the meander is always a rainbow arch configuration of same order.
river. In the present case the lower configuration is fixed: it is called the rainbow arch configuration of order n (the bridge i is connected to the bridge (2n − i + 1), i = 1, 2, ..., n).
On the other hand, the upper arch configuration may take any of theM n values leading to semi-meanders of order n.
There are however distinct arch configurations of order n [7], as is readily proved by recursion (c n+1 = 0≤j≤n c j c n−j , with c 0 = 1, hence c 1 = 1, c 2 = 2, c 3 = 5, c 4 = 14,...: the c n are called the Catalan numbers). Hence not all upper arch configurations, once supplemented by a lower rainbow arch configuration of same order, lead to an opened semi-meander (M n < c n ). This is because, in general, the corresponding object will have k ≥ 1 connected components: we call it a semi-meander of order n with k connected components.
Indeed, if the river is folded back into a semi-infinite one, we are simply left with a collection of k possibly interlocking semi-meanders of respective orders n 1 , n 2 ,..., n k , with n 1 + n 2 + ... + n k = n. We always have 1 ≤ k ≤ n, and k = n only for the superposition of an upper and a lower rainbow configurations, leading to n concentric circles. We denote bȳ M (k) n the number of inequivalent semi-meanders of order n with k connected components.
In particular, we haveM  The direct numerical study of the asymptotics of the numbersM (k) n turns out to be delicate, as the natural scaling variable of the problem is the ratio x = k/n, which depends on n and takes only a discrete set of values. To circumvent this problem, we will study the generating functionm n (q) for these numbers, also referred to as the semi-meander polynomial.m n (q) = whereR(q) is the partition function per bridge, γ(q) is a possibly varying exponent and c(q) a function independent of n. For q → 0 (k = 1), we must recover the connected semi-meanders, namely thatm n (q)/q →M n , i.e.
(c.f. (2.1)). The notion of winding is well-defined for multi-component semi-meanders as well, as the sum of the individual windings of each connected component, namely the total number of times the various roads forming the semi-meander wind around the source of the river. Therefore we define w n (q) = 1 m n (q) multicomp. semi−meanders w q k ∼ n ν(q) (2.8) where ν(q) is the generalized winding exponent for multi-component semi-meanders, satisfying 0 ≤ ν(q) ≤ 1.
Analogously, we define multi-component meanders of order n, as configurations of k non-intersecting roads (1 ≤ k ≤ n) crossing the river through a total of 2n bridges, and denote by M This is nothing but the restriction of (2.5) with n → 2n, to semi-meanders with zero winding w = 0. We therefore expect the asymptotics for large n m n (q) ∼ c(q) R(q) 2n n α(q) (2.10) In this estimate, the partition function per bridge R(q) is expected to be identical to that of semi-meandersR(q) only if the winding is irrelevant, namely if ν(q) is strictly less than Otherwise, the fraction of semi-meanders with zero winding may be exponentially small, and we only expect that R(q) <R(q) if ν(q) = 1.

Exact results for large numbers of connected components (q = ∞)
For very large q, we simply havem as the meander polynomial is dominated by the k = n term, corresponding to the unique semi-meander of order n made of n concentric circular roads, each crossing the semi-infinite river only once. This semi-meander will appear as the rightmost object in the n-th line of the tree of Fig.8. The winding of this semi-meander is clearly w = n, hence we have, for As to meanders, the only way to build a meander of order n with the maximal number n connected components is that each component be a circle, crossing the river exactly twice. This is readily done by taking any upper arch configuration and completing it by reflection symmetry w.r.t. the river. This leads to M (n) n = c n (c.f. (2.4)) meanders with n connected components. By Stirling's formula, we find that when q → ∞ the meander polynomial behaves as m n (q) ∼ c n q n This confirms the abovementioned property (2.11) that R(q) <R(q) when ν(q) = 1, as 2 √ q < q for large q. The function h satisfies h(i) ≥ 0, for all i, and may be interpreted as a "height" variable, defined on the segments of river, whose graph is nothing but a walk of 2n steps as shown in Fig.6. This may be seen as the two-dimensional extent of a brownian motion of 2n steps on a half-line, originating and terminating at the origin of the line. This interpretation makes the leading behavior c n ∼ 2 2n of (2.16) clear: it corresponds to the 2 possible directions (up or down) that the motion may take at each step. The exponent 3/2 in (2.16) is characteristic of the boundary condition, namely that the motion is closed and takes place on a half-line (other boundary conditions would lead to different values of γ, e.g. for a closed walk on a line, we would have a behavior n 2n ∼ 2 2n / √ n).
In this picture, the winding is simply given by the height w = h(n) of the middle point.
Let us evaluate more generally the average height of a point i over the arch configurations of order n. It is given by simple calculation [9] shows that as the A n,i (h) walks are simply obtained by gluing two independent walks of i and 2n − i steps linking the origin to the height h.
In the case of the winding, w = h(i = n), (2.18) leads to a more compact formula, according to the parity of n n = 2p : For large n, this gives the following expansion irrespectively of the parity of n. This implies that This is the well-known result for the Brownian motion, for which the extent of the path scales like n 1/2 for large n. It is instructive to note that, thanks to (2.21), the observable w + 1 is less sensitive than w to the finite size effects at q = 1. This will be useful in the forthcoming numerical estimates for arbitrary q where we observe that the numerical extrapolations are improved by considering w + 1 instead of w. Using (2.19), we may now compute the probability distribution P n (w) for an arch configuration of order n to have winding h(n) = w, which takes for large n the scaling form with a scaling function f independent of n for large n, readily obtained by use of Stirling's formula, upon writing w = 2 n/π ξ for large n. This gives For general position i = n, we find, by a saddle point evaluation of the sum (2.18), that the average profile of arch configurations is a "Wigner" semi-circle The meanders of order n are the semi-meanders of order 2n with winding w = h(2n) = 0. They are therefore built as the juxtaposition of two independent walks of length 2n. Hence or, in other words This is again in agreement with (2.11), as ν(1) = 1/2 < 1, i.e. the winding is irrelevant at q = 1.

Exact enumeration and its analysis
In this section, we present results of an exact enumeration ofM (k) n for small n (n ≤ 29), and analyze their large n extrapolation. The enumeration is performed by implementing on a computer a recursive algorithm which describes all the semi-meanders up to some given order. Clearly, the complexity is proportional to the Catalan numbers (c n ∼ 4 n ) hence the limitation on n.

The main recursion relation
The subsequent numerical study relies on the exploitation of the following recursion relation generating all the semi-meanders of order (n + 1) from those of order n.
The construction of all the semi-meanders of order n + 1 with arbitrary number of connected components from those of order n. Process (I): (i) pick any exterior arch and cut it (ii) pull its edges around the semi-meander and paste them below. The lower part becomes the rainbow configuration R n+1 of order n + 1. This process preserves the number of connected components k → k. Process (II): draw a circle around the semi-meander of order n. This process adds one connected component k → k + 1.
We start from any semi-meander of order n with k connected components, in the open-river picture. We may construct a semi-meander of order (n + 1) in either following way (denoted (I) or (II)), as illustrated in Fig.7 (I) Pick any exterior arch, i.e. any arch with no other arch passing above it. Cut it and pull its ends all the way around the others (in order to add two bridges), and reconnect them below, by creating an extra concentric lower arch for the rainbow. In this process, we have n → n + 1, but the number of connected components has not changed: k → k. Another way of picturing this transformation is the following: one simply has pulled the exterior arch all the way around the semi-meander and brought it below the figure, creating two new bridges along the way. As no cutting nor pasting is involved, the number of connected components is clearly preserved.
(II) Draw a circle around the semi-meander. This adds a lower concentric semi-circle which increases the order of the rainbow to (n+1), and also adds one connected component to the initial semi-meander k → k + 1.
These two possibilities exhaust all the semi-meanders of order (n + 1), as the transformation is clearly invertible, by pulling back up the lower external arch of the rainbow.
Note that by construction, there are as many possibilities for the process (I) as exterior arches, and the transformation is therefore one-to-many. The tree of semi-meanders down to order n = 4. This tree is constructed by repeated applications of the processes (I) and (II) on the semimeander of order 1 (root). We have indicated by small vertical arrows the multiple choices for the process (I), each of which is indexed by its number. The number of connected components of a given semi-meander is equal to the number of processes (II) in the path going from the root to it, plus one (that of the root).
We may now construct a tree of all the semi-meanders, generated recursively from that of order 1 (root), as displayed in Fig.8. Note that we have adopted the open-river formulation to represent them.
Keeping track of the connected components, this translates into the following relation between the semi-meander polynomials where we denoted by ext.arch. n (q) the average number of exterior arches in a semimeander of order n, weighed by q k , k its number of connected components. In (3.1), the first term corresponds to all the processes (I), whereas the second term corresponds to (II).
Taking the large n limit in (3.1), this permits to interpret as the limit when n → ∞ of the average number of exterior arches in semi-meanders of order n, weighed by an activity q per connected component.
In particular, when q → ∞, we havē as the limiting semi-meander, made of concentric circles, has only one exterior arch. This is a refinement of the large q estimate in (2.13). When q = 1, we find an average of exterior arches in arbitrary arch configurations of large order [7]. When q = 0, the con-

Exact enumeration and large n extrapolation
In appendix A, we give an archetypical example of the programs we have implemented to compute the semi-meander numbers and various observables. We have computed the numbersM (k) n for 1 ≤ k ≤ n ≤ 27, the numbersM  2n (0)), and the semi-meander "profile" semi−meanders order n,k c.c.
for all positions 0 ≤ i ≤ 2n. Some of these numbers can be found in appendix A.
After gathering these numbers into generating functions of q, it is possible to perform large n extrapolations at fixed q, for the quantitiesR(q), R(q), γ(q), α(q),c(q), c(q) and ν(q).
The general extrapolation scheme is the following. Suppose an observed quantity X n has the following large n expansion Then we get a best estimate of the large n limit x 0 by iterating p times the difference This gives perfect results for the Catalan numbers (i.e., q = 1) using X n = Log(c n+1 /c n ).
This turns out to extend to a whole range of q's in a neighborhood of 1. For instance, The results forR(q) and R(q) are displayed in Fig.9. The two functions are found to coincide in the range 0 ≤ q ≤ q c with q c ≃ 2, and to split intoR(q) > R(q) for q > q c .
As explained before, the comparison betweenR(q) and R(q) determines directly whether ν(q) is 1 or not. The result of Fig.9 is therefore the signal of a phase transition at q = q c between a low-q regime where the winding is essentially irrelevant (ν(q) < 1) and a large-q phase with relevant winding (ν(q) = 1). This is compatible with the direct extrapolation for ν(q) displayed in Fig.10, which is however less reliable in the region around q = 2, due to its sub-leading (and probably discontinuous) character.
The configuration exponent for semi-meanders γ(q) is represented in Fig.11, for two different orders in the extrapolation scheme (3.8). The extrapolation proves to be stable for 0 < q < 2. For q > 2, it develops oscillations around a mean value, estimated to vanish (γ(q) ∼ 0) for q large enough. For simplicity, we chose not to represent the functions α(q), c(q),c(q). The coefficientc(q) develops a discontinuity at the transition q = 2. On the other hand, the functions pertaining to meanders only (α(q) and c(q)) do not display any transition at q = 2.

Scaling functions
By analogy with critical phenomena, in addition to the scaling behaviors (2.6), (2.10) and (2.8) involving the critical exponents γ(q), α(q) and ν(q), we expect to find more refined scaling laws involving scaling functions. A particular example of such scaling functions has been derived for q = 1 (2.23), for the probability distribution P n (w) of the winding w among arch configurations of order n. It involves the scaling function (2.24).
For q = 0 we expect the same behavior for the corresponding probability distribution of winding w among connected semi-meanders of order n. We expect the scaling behavior This is precisely what we observe in Fig.12, where we plot w + 1 n (0) P (0) n (w) as a function of the reduced variable ξ = (w + 1)/ w + 1 n (0) for different values of n. Indeed, as already explained in the q = 1 case, we have taken the variable (w + 1) instead of w to improve the convergence. All the data accumulate on a smooth curve, which represents the scaling function f (0) (ξ). The shape of this function is reminiscent of that of the end-to-end distribution for polymers. By analogy, we expect a certain power law behavior for small ξ where θ satisfies the relation obtained by identifying  For large ξ, we expect a behavior f (0) (ξ) ∼ exp(−const. ξ δ ) with a possible Fisher-law behavior δ = 1/(1 − ν). The observed function of Fig.12 is compatible with these limiting behaviors, although we cannot extract reliable estimates of the exponents θ and δ.
As we already did in the case of q = 1 (2.25), we can study the average profile of involving a scaling function ρ(x; q) of the variable x, with 0 ≤ x ≤ 2 for each value of q (with the appropriate normalization such that ρ = 1). For instance, we have seen in eq.(2.25) that ρ(x; 1) = (2/π) x(2 − x).  Fig. 13: Semi-meander average profiles for q = 0, 1, 2, 4, and 1 ≤ n ≤ 24, as functions of the reduced variable x = i/n. For q = 1, we also represented the exact large n Wigner semi-circular limit ρ(x; 1). For q = 4, we also represented the large n and q piecewise-linear limit ρ(x; ∞).
We have represented in Fig.13 these profiles for several values of q. Again, the points accumulate on smooth limiting curves ρ(x; q). We observe a first change of behavior at q = 1 between a q < 1 regime with a negative cusp at x = 1 and a q > 1 regime with a positive cusp, separated by the Wigner semi-circle, with no cusp at q = 1. For large q, ρ(x; q) tends to the limit ρ(x; ∞) = 1 − |1 − x| corresponding to the unique semi-meander made of n concentric circles, which satisfies h(i) = i for 0 ≤ i ≤ n and h(i) = 2n − i for n ≤ i ≤ 2n. For small x, we expect a power law behavior of the form where we identify the exponent ϕ(q) = ν(q) from h(1) = 1 and the fact that j h(j) ∼ n 1+ν(q) .

Large q asymptotic expansions
In the previous section, we have observed two regimes for the semi-meander polynomials, namely a low-q regime in which the winding is irrelevant and a large-q regime where the winding is relevant, separated by a transition at a value of q = q c ≃ 2. On the other hand, we have already exhibited an exact solution of the problem at q = ∞ (2.13), and a first correction thereof for large q in (3.3). It is therefore tempting to analyze the large q phase by a systematic expansion in 1/q. This is performed in the following section, wherē R(q) is expanded up to order 19 in 1/q, and γ(q) is found to vanish identically throughout the large q regime. In the subsequent section, we compute the large q expansion of the average winding in semi-meanders, and we find ν(q) = 1 identically in this regime.

Large q asymptotic expansion of the semi-meander polynomial
In this section we derive the large q expansion of the semi-meander polynomialm n (q) of eq.(2.5) asm involving the semi-meander numbers in the formM (n−k) n , k = 0, 1, 2,... Remarkably, these numbers, for arbitrary n ≥ 2k − 1, are polynomials of n, which furthermore exhibit some special structure allowing for an explicit large q expansion ofR(q).
The section is organized as follows. We first derive the polynomial form of theM For starters, let us first compute the numbersM (n−k) n for k = 0, 1, 2.
As we already mentioned, the leading termM only, and which we refer to as the leading semi-meander (c.f. Fig.14 (a)). This yields the first polynomial for all n ≥ 0.
The sub-leading term is made of the "kidney"-type perturbations of the leading semi-meander, displayed in Fig.14 (b).
The next-to-leading term consists of the semi-meanders of order n with (n − 2) connected components, which may be obtained as follows.
(i2) (Fig.14 (c) 2 ) included in one another, hence a total of (n − 3) choices for the position of the double kidney, or 0 choice if n = 2.
(ii) The second possibility is a larger "spiral"-type perturbation of the leading semimeander, with a total of (n We see here the first appearance of a correction for small n, in that an extra boundary term (δ n,2 ) has to be added at n = 2, to recover the fact thatM Recall that the process (I) may be applied to any exterior arch of the semi-meander.
In the situation where k << n, the semi-meander will most probably have only one exterior arch (generated by the last process, most probably of the type (II)), and there will be only one choice for (I), creating a kidney. If two or more processes (I) are applied consecutively, the number of exterior arches may grow, and yield more semi-meanders (e.g. the appli-  have therefore needed to specify that their number (generically equal to (n − 3)) vanishes for n = 3 (granted) and n = 2, the latter resulting in a boundary correction δ n,2 . More generally, expressing that the combinatorial expressions found are only valid for large enough n's will translate into boundary terms, studied in detail in appendix B. We simply quote the result here, valid for all n ≥ k where theμ Instead we can guess the coefficients of p k (n) by matching our data forM (n−k) n with the form (4.6). This can be pushed further by exploiting the re-exponentiation property of m n (q), which implies relations between the coefficients of the p k (n), as discussed now.
The property (4.6) must be reconciled with the large n behavior ofm n (q) (2.6), namely that for n sufficiently large Logm n (q) = n LogR(q) − γ(q)Log n + Logc(q) + o(1) (4.7) Such an expansion is valid for all q, and we can in particular study it for large q. On the other hand, up to any order k in the 1/q expansion, and by choosing n ≥ 2k − 1, we may also write In this expansion, the coefficient of 1/q m is a polynomial of n, as a sum of products of polynomials of n. Comparing this with an expansion of (4.7) in 1/q, we see that its degree is at most 1. Therefore, there exist two sequences of coefficients (α k , β k ), such that with the correspondence Moreover, there can be no Log n term in the expansion of (4.7), hence the remarkable result γ(q) = 0 (4.11) This result is expected to hold as long as the corrections to the polynomial behavior of thē M (n−k) n are negligible. As we will see, this condition defines precisely the large q phase q > q c . Therefore the exponent γ(q) vanishes identically over the whole phase q > q c . In view of, say, the exact value γ(q = 1) = 3/2, this property cannot persist in the small q < q c phase. This is not surprising since the first correction µ (k) 0 = c k−1 (for k = n/2 + 1) implies an additional power law correction of the form 1/n 3/2 .
For n ≥ 2k − 1, (4.9) is a quasi-recursion relation for the polynomials p k , hence for the semi-meander numbersM (n−k) n . This relation is exploited in appendix C to generate from our numerical data the polynomials p k (x) for 0 ≤ k ≤ 18, together with their corrections.
Using these polynomials, it is now straightforward to read the functionsR(q) andc(q) using (4.10), with the result It is interesting to compare the result of these large q expansions to the previous direct large n extrapolations of sect.3. As far asR(q) is concerned, we find a perfect agreement for the values q ≥ 2, down to q = 2, where we findR(2) ≃ 4.442(1) using (4.12), in perfect agreement with the previous estimate. The precision of (4.12) increases with q, leading to far better estimates than before:R(3) ≃ 4.92908(1),R(4) ≃ 5.6495213(1)...
As to γ(q), our prediction that γ(q) = 0 for all q > 2 is compatible with the previous extrapolation of Fig.11, where this value is represented in dashed line. We therefore expect γ(q) to have a discontinuity at q = 2, where it goes from a non-zero γ(q = 2 − ) value to zero. This will be confirmed by the forthcoming analysis of the low-q phase in sect.5.

Large q asymptotic expansion of the semi-meander winding
In this section, we first examine the contribution of the circles to the winding of semimeanders in the large q phase. It turns out to be of the order n throughout this phase, implying that the winding exponent ν(q) = 1 for all q > q c . In a second step, we compute the large q expansion of the average winding by techniques similar to those of the previous section, showing that the circles contribute only for a finite fraction of the winding in the large q phase. This study will single out the value q c = 2 with a very good precision.
To enumerate the total number of circles in order n semi-meanders, we simply have to count the semi-meanders with a marked circle, in one-to-one correspondence with pairs of semi-meanders of total order (n − 1) (since the marked circle separates the original meander into two disconnected pieces, its inside and outside). Hence, the average number of circles in semi-meanders is given by circ. n (q) = q n−1 j=0m j (q)m n−1−j (q) m n (q) (4.13) valid for all q and n, with the convention thatm 0 (q) = 1. Using the large n asymptotics m n (q) ∼c(q)R(q) n , with γ(q) = 0 throughout the large q regime, we find circ. n (q) ∼ n qc (q) R(q) (4.14) The average number of circles therefore grows like n which in turn implies that throughout the large q regime, since each circle contributes 1 to the winding and clearly w ≥ circ. . Note that the above argument relies crucially on the fact that γ(q) = 0, and thus cannot be applied to the small q regime. Indeed, for q = 1, (4.13) simply gives circ. n (q = 1) = 1 for all n, hence a very different behavior.
The quantity σ(q) = lim n→∞ circ. n (q)/n is simply given by the Taylor expansion of Let us now turn to the large q expansion of the average winding of semi-meanders (2.2). This requires a refined study of the semi-meander numbersM where the coefficients λ(q) and µ(q) have the following large q expansions up to order 14 It can be checked directly that λ(q) > σ(q) hence the circles only contribute for a finite fraction of the total winding. The plots of the functions λ(q) and σ(q) are displayed in Fig.15. Remarkably, both coefficients seem to vanish at the same point q = 2 with an excellent precision. Since these coefficients must be positive, we deduce that our large q formulas break down for q < 2. We interpret this as yet another evidence of the drastic change of behavior of the average winding w , which is no longer linear in n below q c , and we find q c = 2 with an excellent precision.
The actual break-down of the large q phase is studied more systematically in next section. The numbersμ 2k−2−n are listed for n/2 < k < n = 2, 3, ..., 9 in appendix C. With the only difference that we are now dealing with rational fractions of n instead of polynomials, we can carry the same large n expansion as in sect.4.1, to extract the large n asymptotics of μ n (q), with the result, according to the parity of n µ 2n (q) ∼c + (q)R 1 (q) 2n (2n) γ 1 (q) Using the results of appendix C, we get the following large q expansions (incorporating the large n asymptotics of c n ∼ 4 n /( √ πn 3/2 )) Due to the rational fractions of n we have dealt with, we cannot conclude that γ 1 (q) = 3/2 (the 3/2 comes from the Catalan number asymptotics) identically for large q. We expect this to hold only in the q → ∞ limit, whereas for finite q, γ 1 (q) is some function of q.
We can now writem n (q) ≃c 0 (q)R 0 (q) n +c ± (q)R 1 (q) n n γ 1 (q) + · · · (5.4) where ± is chosen according to the parity of n and we have indexed by 0 the functions R(q) andc(q) corresponding to the polynomial contributions to theM (n−k) n , with the asymptotic expansions (4.12). When q is large, the first term dominates asR 0 (q) ∼ q, This justifies a posteriori the identificationR(q) =R 0 (q) in the large q regime of sect.4. The properties derived in sect.4. for the large q regime will however break down ifR 1 (q) ≥R 0 (q), i.e. when the corrections become dominant. We expect such a crossing of phases to take place at the transition point q = q c , at which R 1 (q c ) =R 0 (q c ). In this scenario,R(q) =R 1 (q) for all q < q c , and the exponent γ(q) jumps abruptly from its large q > q c value γ 0 (q) = 0, to a non-zero value γ 1 (q c ) = 0. This mechanism explains the jump in the value of γ(q) at the vicinity of q = q c , as observed in Fig.11. In this figure, we have represented in dashed line the purported value γ(q) = 0 for q > 2, which must be substituted to the (bad) large n estimate in this regime, whereas we still rely on the (good) q < 2 estimate.
To reconcile this scenario with the picture described in sect.3, in which for q < q c the winding of semi-meanders becomes irrelevant (i.e.R(q) = R(q)), we should havē R 1 (q) = R(q) below the transition point q c , where the semi-meanders enter their meanderlike phase. Since the meanders themselves do not display any transition at q = q c , it is tempting to infer thatR 1 (q) = R(q) for all values q. As we will see now, this is corroborated by the large q expansion (5.3) forR 1 (q), which turns out to coincide with that of R(q) for meanders (2.10). The latter is easily carried out for the meander numbers, whose structure, given in appendix E, is very similar to that of the semi-meander corrections.
More precisely, the meander numbers M (n−k) n take the general form where r k (x) is a rational fraction of x, with total degree k. With the values listed in appendix E, we find the following large q expansion for the functions R(q) and c(q) of (2.10), up to order 6 in 1/q The exponent α(q) is also found to tend to the Catalan value 3/2 when q tends to infinity, but appears to be a non-constant function of q for all finite q. Remarkably, the first terms of the large q series expansions of R(q) and those of the correction to semi-meandersR 1 (q) coincide!
In conclusion, all our results conspire to suggest that the semi-meanders undergo at q = q c a transition from a "meander"-like regime q < q c , governed by the meander partition function per bridge R(q) ≡R 1 (q), to another regime q > q c , governed byR 0 (q). The order parameter for this transition is clearly which vanishes for q < q c (irrelevant winding, i.e. ν(q) < 1) and is nonzero for q > q c (relevant winding, i.e. ν(q) = 1). With the order parameter (5.7), the transition is found to be continuous, as the leading coefficient λ(q) (4.18) vanishes at q = q c . The smooth character of the transition is also visible from the fact thatR(q) and R(q) approach each other tangentially at q = q c , and that the coefficientc 0 (q) =R(q)σ(q)/q of the large-q dominant contribution tom n (q) vanishes at q = q c (see Fig.15).

Small q behavior of the semi-meander polynomial
The very existence of asymptotics of the form (2.6) for the semi-meander numbers, with a smooth enough functionR(q) has highly non-trivial consequences on the numbers M (k) n . We have already seen how the numbersM (n−k) n , for large n and finite k, are linked to each other (4.8) in order for (2.6) to hold for large q. Let us now examine its consequences on the small q and large n behavior ofm n (q). Let us expandm n (q) around q = 0 up to order k, and take the large n asymptotics of each term in the expansion: where we have only retained the leading n asymptotics in each q j term, and used the q → 0 limits (2.7) (actually, we have assumed that q ∼ 1/n). Comparing with theM n asymptotics (2.1), we finally get valid for large n and finite k. This is actually very similar to the behavior of theM (n−k) n ∼ n k /k! for large n and finite k, and may be deduced from the main recursion relation for semi-meanders as well. Indeed, the numberM n connected semi-meanders are obtained through the process (I) only. Apart from the relative combinatorial factor k−1 n−1 ∼ n k−1 /(k − 1)! accounting for the (k − 1) choices of process (II) among the total of (n − 1) steps, we must consider that whenever a step (II) is chosen instead of a step (I), some freedom in the overall choice is lost. Eq.(6.2) tells us that this corresponds to an average factor ofR ′ (0)/R(0) per step (II) taken instead of a step (I). We checked (6.2) numerically, by performing a large n extrapolation of the appropriate ratio for a few values of k. We find a very good agreement with the estimatē

Conclusion
In this paper, we have analyzed the meander problem in the language of critical phenomena, by analogy with Self-Avoiding Walks. In particular, we have displayed various scaling behaviors, involving both scaling exponents and scaling functions. We have presented strong evidence for the existence of a phase transition for semi-meanders weighed by a factor q per connected component (road). In a large-q regime (q > q c ), the winding is found to be relevant, with a winding exponent ν(q) = 1, while the configuration exponent γ(q) = 0. Throughout this phase, a finite fraction σ(q)/λ(q) of the winding is due to circles, i.e. circular roads with only one bridge, winding around the source of the river. In this regime, the partition function per bridge for semi-meandersR(q) is strictly larger than that of meanders R(q). The particular form of its large q series expansion in 1/q (4.12) with slowly alternating integer coefficients, which furthermore grow very slowly with the order, and its purported re-summation (D.14), suggest a possible re-expressionion in terms of modular forms of q, yet to be found. In a low-q regime q < q c ,R(q) and R(q) coincide, in agreement with an irrelevant winding ν(q) < 1. The exponent γ(q) is no longer 0, but a strictly positive function of q.
We have estimated the value of the transition point q c ≃ 2 with an excellent precision, and we conjecture that q c = 2 exactly. This special value of q has already been singled out in the algebraic study of the meander problem, in connection with the Temperley-Lieb algebra [9]. There, we have been able to re-express the meander and semi-meander partition functions as that of some Restricted Solid-On-Solid model, whose Boltzmann weights are positive precisely iff q ≥ 2, indicating very different behaviors for q < 2 and q > 2.
In the large-q phase, in addition to the exact values ν(q) = 1 and γ(q) = 0, we can use the asymptotic expansion (4.12) to getR(q) with a very good precision. The somewhat sub-leading meander quantities R(q) and α(q) are more difficult to evaluate in this regime.
A number of questions remain unsettled. There still remains to find the varying exponents γ(q) and ν(q) in the q < 2 regime, as well as the precise value of R(q) =R(q).

Acknowledgments
We thank M. Bauer for a critical reading of the manuscript.

Appendix A. Algorithm for the enumeration of semi-meanders
The following is a simple computer algorithm directly inspired by the recursion relation of Sect.3.1.
There, it has been shown that one can construct a tree of all the semi-meanders generated recursively with processes (I) and (II), as displayed in Fig.8. Each node at depth n represents a semi-meander of order n. To have a finite cost of computation, the order is limited to nmax and the nodes of depth nmax appear to be leaves. The algorithm we used consists in visiting all the leaves from left to right, following the branches, as a (clever) squirrel.
To do that, the rules are : In the open-river formulation, each semi-meander is made of a lower rainbow arch configuration (which we need not code) and an upper arch configuration of order n. For convenience, we label the 2n bridges of river from i = −n + 1 to i = n, and the system of arches is described by a sequence of integers {A(i); i = −n + 1, ..., n}, where A(i) ∈ {−n + 1, ..., n} is the label of the bridge connected with the bridge i. The following Fortran program enumerates the connected semi-meanders. For simplicity, only the process (I) is coded and the number of connected components is always k = 1. The arch to be broken (j, A(j)) begins at the bridge j and ends at the bridge A(j). The process (I) splits this arch into two arches (−n, j) and (A(j), n + 1). When the squirrel climbs back up one level, the two extremal arches (−n + 1, A(−n + 1)) and (A(n), n) are re-sealed to give one arch (A(−n + 1), A(n)).
A(A(j)) = n+1 ! go down with process (I) A(n+1) = A(j) A(j) = -n A(-n) = j GOTO 2 3 A(A(-n+1)) = A(n) ! going up A(A(n)) = A(-n+1) j = A(n)+1 ! next arch to break n = n -1 IF (n .GT. 1) GOTO 1 PRINT '(i3, i15)', (n, Sm(n), n = 1, nmax) END It is possible to use the left-right symmetry to divide the work by two. It is also possible to adapt the program for a parallel computer. For that, an intermediate size where the c n are the Catalan numbers (2.4).
As explained in Sect.4, the polynomial part ofM (n−k) n is generically obtained as a sum of combinatorial factors, counting all the possible occurrences of perturbations of the leading semi-meander (order n, n components) which have the same order n, but have only n − k connected components. A perturbation, by definition, is made of a core, which does not contain any circle, supplemented by circles. The core is generically made of p irreducible semi-meanders with a total order n 0 , and a total of (n 0 − k) connected components. By irreducible, we mean that no circle can separate the semi-meander in two disconnected pieces. This core is completed by (n − n 0 ) circles, to form a semi-meander of order n. Enumerating all perturbations of the leading meander with n − k components amounts to enumerating all the ways of completing cores by circles. There are exactly possible decorations of the above core by circles. The polynomial form (B.2) of the combinatorial factor is however only valid for n ≥ n 0 − p. When n ≤ n 0 − p − 1, we have to add a correction to the polynomial form to get a vanishing result, equal to (−1) p+1 for the largest n = n 0 − p − 1. The largest n at which such corrections occur is obtained by maximizing n 0 − p. As the core does not contain any circle, each of its n 0 − k connected components is at least of order 2, hence This inequality is saturated for a core made of k kidneys. Minimizing p consists in taking (k − 1) arbitrary kidneys included in one, for which p = 1. We therefore find that the first correction to the polynomial behavior (4.6) occurs at n = 2k − 2. Fig. 16: Arbitrarily disjoint or included kidneys are equivalent to symmetric meanders upon folding back the river, as indicated by the arrows. The latter are in one-to-one correspondence with arch configurations of the same order.

* *
p 14 (x) = (x 14 + 259x 13 + 23751x 12 + 899171x 11 + 8661653x 10 − 285047763x 9 − 7202313547x 8 − 30034731727x 7 + 538444152246x 6  interpreted as the partition function for semi-meanders weighed by q per connected component and 1/ √ t per winding unit (up to a global normalization factor). In the large q limit we now repeat the analysis performed in sect.4.1, by Taylor-expanding Log(m n (q, t)/q n ) order by order in 1/q, in the same way as we did previously for Log(m n (q)/q n ). This also relies on the identification of the numbersM The correction is ad hoc to yield a zero answer when n = 2.