9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # A Diagrammatic Approach to the Meander Problem

NBI-HE-98-18 July 1998

A Diagrammatic Approach to the Meander Problem

arXiv:hep-th/9807193v1 27 Jul 1998

M. G. Harris1

The Niels Bohr Institute, Bl

egdamsvej 17, DK-2100 Copenhagen ?, Denmark.

Abstract

The meander problem is a combinatorial problem which provides a toy model of the compact folding of polymer chains. In this paper we study various questions relating to the enumeration of meander diagrams, using diagrammatical methods. By studying the problem of folding tree graphs, we derive a lower bound on the exponential behaviour of the number of connected meander diagrams. A di?erent diagrammatical method, based on a non-commutative algebra, provides an approximate calculation of the behaviour of the generating functions for both meander and semi-meander diagrams. Keywords: meander, folding, combinatorial

1

E-mail: Martin.Harris@nbi.dk

1

1

Introduction

The problem of enumerating meander and semi-meander diagrams has appeared in many diverse areas of mathematics [1, 2] and computer science [3, 4]. In the case of semimeanders it can be reformulated as an enumeration of the foldings of a strip of postage stamps [5, 6], which is equivalent to a model of compact foldings of a polymer. Thus the semi-meanders serve as a toy model of the statistical mechanics of such polymer chains. The generating function for meanders can be written as an Hermitian matrix model or as a supersymmetric matrix model [7, 8]. Alternatively combinatorial methods can be used [5, 6], one can represent the problem in terms of non-commuting variables [8] or using a Temperley-Lieb algebra [9, 10, 11]. Despite all of these di?erent approaches and the initial apparent simplicity of the problem, the task of counting the meander and semi-meander diagrams has remained largely unsolved. In this paper we apply diagrammatical methods to the study of meanders. In section 2 the problem is de?ned and some tables of meander numbers are given. Then in section 3 we calculate bounds on the number of connected meanders, in particular the lower bound is improved by mapping the meanders to folded tree graphs. Section 4 uses a diagrammatic representation of a non-commutative algebra to calculate approximate generating functions for meanders and semi-meanders. The nature of the phase transition for semimeanders is also considered in this section. Finally we give our conclusions in section 5 of the paper.

2

2.1

De?nition of the meander numbers

Meanders

Suppose that we have an in?nite line (or “river”) on a planar surface. Then a connected meander of order n is de?ned to be a non-self-intersecting connected loop (or “road”) which crosses the river 2n times (the crossing points are referred to as “bridges”). Two meanders are considered to be equivalent if it is possible to smoothly deform one meander into the other without changing the number of bridges during the process. The total (1) number of inequivalent connected meanders of order n is denoted Mn , and we can de?ne a generating function, M (x) for connected meanders, M (x) = The ?rst few meander numbers are M1 some simple meander diagrams.

(1) ∞ n=1 (1) Mn xn .

(1)

(1)

= 1, M2

(1)

= 2 and M3

= 8. Figure 1 shows

2

Figure 1: Some simple meander diagrams.

The de?nition can be extended to include cases in which the road consists of k dis(k) connected parts, giving a number of meanders of order n denoted by Mn . This leads us to de?ne a more general generating function, M (x, m) =

(k) ∞ n (k) Mn xn mk .

(2)

n=1 k=1

Table 1 gives Mn for small values of k and n (these numbers are taken from [6]). Some examples of disconnected meanders are shown in ?gure 2.

Figure 2: Some simple disconnected meander diagrams.

k 1 2 3 4 5 6 7

n=1 1

2 2 2

3 8 12 5

4 42 84 56 14

5 262 640 580 240 42

6 1828 5236 5894 3344 990 132

7 13820 45164 60312 42840 17472 4004 429

Table 1: Meander numbers, Mn

(k)

(from ref. [6]).

2.2

Semi-meanders

Suppose that instead of having an in?nite river we have only a semi-in?nite river. The end of the river is often referred to as the “source”. In this case the road can wrap around the 3

source of the river and the corresponding diagrams are called “semi-meanders”. As before two semi-meanders are equivalent if one can be smoothly deformed into the other, without changing the number of bridges. Figure 3 shows some examples of semi-meanders.

Figure 3: Some semi-meander diagrams. The source is marked with a dot.

Let us denote the number of inequivalent semi-meanders with n bridges and a road (k) consisting of k connected parts, as M n . Then the corresponding generating function is S(c, m) =

∞ n

M n cn mk .

(k)

(3)

n=1 k=1

Note that the meanders can only have an even number of bridges, whereas semi-meanders can have both even and odd numbers of bridges. This is the reason for the slightly di?erent de?nitions of the generating functions and one should de?ne x ≡ c2 . Table 2 gives the numbers for the simplest semi-meanders. k 1 2 3 4 5 6 7 n=1 1 2 1 1 3 2 2 1 4 4 6 3 1 5 10 16 11 4 1 6 24 48 37 17 5 1 7 66 140 126 66 24 6 1

Table 2: Semi-meander numbers, M n (from ref. [6]).

(k)

3

3.1

Connected meanders

Bounds on the number of meanders

In this section we will derive some bounds on the number of inequivalent connected meanders (from now on it should be understood that we are referring always to inequivalent meanders). The standard way of doing this is to consider a meander as being formed from 4

two arch diagrams (see ?gure 4 for some examples of arch diagrams). That is, if we take a meander diagram and cut it in two along the river, then this gives one arch diagram above the river and one below it (see ?gure 5).

Figure 4: Two example arch diagrams.

Figure 5: A meander cut into two sets of arches. An arch diagram of order n consists of 2n points arranged in a line, which are connected up in pairs by drawing n arches above the points. The arches are not allowed to intersect each other and each point has exactly one arch joined to it. The number of inequivalent order n arch con?gurations is denoted An , and the generating function for arches is de?ned as A(c) =

∞

An cn ,

n=0

A0 ≡ 1.

(4)

The empty arch diagram A0 has the value 1. A non-empty arch diagram can be decomposed into two arch diagrams separated by the arch connected to the rightmost point. This is illustrated diagrammatically as A = 1 + A A . That is, A(c) satis?es the equation A = 1 + cA2 . Hence A(c) = and An = √ 1 1 ? 1 ? 4c 2c (5) (6) (7)

(2n)! 4n ? . n!(n + 1)! n→∞ n3/2 In fact An is equal to cn , the Catalan number of order n.

Since gluing together two arch con?gurations of order n gives a (possibly disconnected) meander of order n we have

n (1) Mn ≤ (k) Mn = An 2 . k=1

(8)

5

In fact, given an arch diagram on top, we can always ?nd an arch con?guration on the bottom that creates a connected meander (using the algorithm given in ?g. 21 of ref. [6]), (1) which means that An ≤ Mn . Consider the asymptotics of Mn

(1)

for a large number of bridges, ? const. R2n , nα (9)

(1) Mn

n→∞

where R gives the exponential behaviour and α is a con?guration exponent. Then

(1) An ≤ Mn ≤ An 2

(10)

implies that 2 ≤ R ≤ 4. (11)

3.2

Improved lower bound

The contents of the previous section are all well-known. In this section we would like to improve the lower bound on R. Instead of considering arch diagrams we will rewrite the connected meanders as tree diagrams. The road of a connected meander divides the plane into two parts: an inside and an outside. Smoothly deforming the road in such a way as to reduce the inside area towards zero yields, in the limit, a connected tree graph (see ?g. 6). Given such a folded tree graph we can easily reconstruct the corresponding meander. Note that applying this

Figure 6: Converting a connected meander, with the inside shaded, to a (folded) tree diagram.

procedure to a disconnected meander would yield a graph that is disconnected and/or contains loops. The tree graphs corresponding to connected meanders can have vertices of arbitrary coordination number, and the mapping procedure is de?ned such that adjacent vertices on the tree occur above and below the river in an alternating fashion. There is a one-to-one correspondence between such tree graphs and the set of connected meanders. By putting bounds on the number of such trees we will improve the lower bound on R discussed in the previous section. 6

It is convenient to label the vertices of each tree with either an ’A’ or ’B’, signifying that they are above or below the river respectively. The left-most link in the tree will be marked by drawing it thicker. Each tree can then be unfolded as shown in ?gure 7.

B A B A B B

A B A

A

Figure 7: An unfolded tree diagram corresponding to the folded tree in ?g. 6.

In general an unfolded tree has many di?erent ways of folding it, subject to the constraints that when folded the ’A’ vertices are above the line and the ’B’ vertices are below it, and that the marked link is leftmost. For example, ?gure 7 can be refolded as in ?gure 8. Each unfolded tree has at least one possible folding and usually has many more. Thus each unfolded tree represents a whole class of connected meander diagrams. By counting the number of unfolded trees we will generate a lower bound on the number

A

B

Figure 8: Another more regular folding of the tree diagram.

of connected meanders. A rooted tree with arbitrary coordination numbers can be generated using the relation illustrated in ?g. 9. That is, if each link in the tree is weighted with x, then the generating function for trees, T (x), satis?es T (x) = x(1 + T + T 2 + T 3 + · · ·) = x/(1 ? T ) and hence T (x) = √ 1 1 ? 1 ? 4x . 2 (12)

(13)

7

T T T T

T T T

Figure 9: Relation which determines T (x), the generating function for rooted trees with arbitrary coordination numbers.

T

U(x)

n1,n2=0

B

A

T T T

n2

n1

T

Figure 10: Relation which determines U (x), the generating function for unfolded trees.

Unfolded trees have a generating function U (x), which from ?g. 10 is given by U (x) = Hence x . (1 ? T )2 (14)

√ T2 1 = 1 ? 1 ? 4x ? 1 = A(x) ? 1, x 2x with A(x) de?ned through equation (6). So we have U (x) = U (x) =

∞ n=1

(15)

An xn .

(16)

However, as mentioned earlier, the number of unfolded trees (with n links) gives a lower (1) bound on the number of connected meanders (with 2n bridges), that is, An ≤ Mn and R ≥ 2. This reproduces the result in section 3.1. Note that since each link of the tree graph is equivalent to two bridges in the corresponding connected meander (?g. 6), the factor for links in the tree had to be x for consistency with the de?nitions in section 2. The representation in terms of trees allows us to improve on the bound by counting more of the possible foldings for each unfolded tree. Suppose that the generating function for partially folded trees is denoted by Θ(x), Θ(x) ≡

∞ n=1

Θn xn ,

(17)

where by partially folded trees, it is meant that only some of the possible foldings are included for each unfolded tree. That is, we are summing over all the trees in U (x), (1) but only some of the foldings. Thus we will have An ≤ Θn ≤ Mn . Let us now de?ne 8

A

Θ (x)

Config.

V V V V

V

River

B

Figure 11: Relation which determines Θ(x), the generating function for partially folded trees.

T T T T T T T

Figure 12: The relation determining T (x), which has been rewritten.

Θ(x) and hence the subset of the possible foldings that are included in the partial folding. First, the relation in ?g. 10 is rewritten to include more foldings (see ?g. 11). The rooted trees T (x) have been replaced by V (x), which is more folded that T and is de?ned below. The sum is over all possible ways of interleaving the arbitrary number of V -trees. This relation gives x Θ(x) = , (18) 1 ? 2V where the x comes from the marked link. The (1 ? 2V )?1 factor is due to the sum over all possible numbers of V -trees, with each tree being connected to one of 2 vertices (’A’ or ’B’). Now consider redrawing the relation in ?g. 9 as shown in ?g. 12. Then we see that the generating function for T only folds in one direction, but that more foldings can be included if we fold to both left and right. Thus for V (x) the relation in ?g. 13 will be used instead. Figure 14 shows a typical V -tree.

V V V V V V V V V

Figure 13: Relation which determines V (x).

9

Figure 14: A typical V -tree contained in V (x).

Figure 15: Example of a diagram included in Θ(x).

Thus we have V (x) = x 1 + 2V + 3V 2 + 4V 3 + · · · = x . (1 ? V )2 (19)

Diagrams such as that in ?g. 15 are generated when this generating function for V (x) is inserted in to (18). Thus Θ(x) will contain a large number, but my no means all, of the possible folded tree diagrams. As x is increased from zero it reaches some critical value xc at which Θ(x) is non-analytic. This is caused by the critical behaviour of V (x) due to dV dx diverging as x → xc . Now, 1 dV = , dx (1 ? 4V + 3V 2 ) Thus Θn ? and hence R ≥

√ 3 3 2

(20)

so that V (xc ) =

1 3

and xc =

4 27 .

27 4

n

(21)

≈ 2.598. This improves the bound given previously.

3.3

Further improvement to lower bound

The lower bound can be improved further by including more foldings than exist in the generating function for V (x). If V (x) is replaced by W (x), whose generating function is 10

given by the relation in ?g. 16, then an improved generating function is x Θimp. (x) = , 1 ? 2W where x (1 ? W )2 . W (x) = =x W (1 ? 2W )2 (1 ? 1?W )2

(22)

(23)

The generating function for W (x) includes all the trees contained in V (x), but also trees in which there are arbitrary numbers of W -trees (emerging from the root) interleaved with the branches connected to the vertex. Replacing V by W in (19) and then changing W to W/(1 ? W ) on the right hand side gives (23). This last replacement takes into account the fact that each branch in ?g. 13 now has an arbitrary number of trees inserted between it and the previous branch or trunk. Figure 17 shows a typical diagram included in W (x).

W

W W

W W

W W

W

W

W

W

W

Figure 16: Relation which determines W (x), where we are summing over arbitrary numbers of W -trees inserted below each branch.

Figure 17: Typical diagram contained in W (x). The root link of the tree is drawn thicker. The links which occur in a W -tree, but not a V -tree are drawn dotted.

Equation (23) gives (1 ? W )2 dW = . dx (1 ? 8W + 12W 2 ? 2x(W ? 1)) (24)

It is the divergence of this derivative which de?nes the critical value of x, √ 1 xc = 71 ? 17 17 8 11

(25)

and hence the lower bound on R is R ≥ xc ? 2 ≈ 2.970.

1

(26)

This is a signi?cant improvement over the lower bound R ≥ 2 that we had initially. It is worth noting that computer enumerations of the number of semi-meanders yield an estimated value of R ≈ 3.50 (see reference [12]). A power series expansion of Θimp. (x) gives Θimp. (x) = x + 2x2 + 8x3 + 42x4 + 252x5 + 1636x6 + · · · , (27) which should be compared with the correct series for meander diagrams M (x) = x + 2x2 + 8x3 + 42x4 + 262x5 + 1828x6 + · · · . (28)

The two series agree up to and including terms of order x4 , after which we see that Θimp. (x) is, as expected, undercounting the number of meander graphs (the relevant terms in Θimp. are underlined). In principle one could improve the generating functions Θimp. (x) and W (x) in order to raise the lower bound further, however it appears to require increasing amounts of e?ort for diminishing returns.

4

Diagrammatic method

In this section, we will develop a diagrammatic method for generating meander and semimeander diagrams. By truncating some of the equations, we will derive approximate solutions for the critical behaviour of M (x, m) and S(c, m), which can be compared with results from computer enumerations carried out by other authors.

4.1

u-diagrams

Following reference [8], let us introduce a set of non-commuting variables {ua , u? } with a a = 1, · · · , m, which obey the relation ua u? = δab . b (29)

We will consider ua , u? as annihilation and creation operators in some Hilbert space, with a a vacuum |? , such that ua |? = 0, Now de?ne G and G? by G = 1 + c Gua Gua G? = 1 + c u? G? u? G? , a a 12 (31) ?|u? = 0, b ?|? = 1. (30)

can write the ?rst equation as G = 1 + Ga G a, where a line emerging from an ’a’, that is written below the equation, represents ua . The fact that the two lines are joined into an arch indicates that we are summing over the repeated index ’a’. Since ’a’ is just a dummy index it can be omitted. It is to be understood that each arch has a factor of c associated with it. Expanding this equation gives G =1+

§¤ ¨ §¤ §¤ §¤? ?¨ ¨ §¤ § ?¤ §¤ §¤ ?? ? ? §¤ ? ? ? ? ?

where we are summing over the repeated index a (a = 1, · · · , m). Diagrammatically we

+

+

+

+

+

+

+

+ ···,

(32)

that is, G = 1 + ua ua + ua ua ub ub + ua ub ub ua + · · ·. Thus G generates arch con?gurations, however unlike A in equation (5) G keeps track of where the ends of the arches are positioned. The generating function G? generates arch con?gurations in terms of u? , a diagrammatically one can consider these as inverted arch diagrams. So

? ? + ?? ? + ?? + + ? ?? ? ? + ? ??+ G? = 1 + ?? ?? + ?? ?? ?? ??? ?? ?? + ?· · · . ? §¤? ?¨

(33)

The dagger operator acting on a diagram can be thought of as re?ecting the diagram, for example, = ??? ?? . (34)

Now consider the expression GG? , this contains terms of the form ua1 ua2· · · uan u?n u?n?1 · u?1 . b b b ·· When this term is drawn as a diagram the inverted arches can be drawn under the upright arches to make the connection with meander diagrams clear. One can apply equation (29) repeatedly to eliminate u and u? variables. In terms of diagrams this corresponds to gluing together a leg on the upright arch diagram to one on the inverted diagram (see ?g. 18). If the number of u variables is equal to the number of u? variables then we will end up with a (possibly disconnected) meander diagram. However, if the numbers are not equal then there will be spare u or u? left over. Taking the vacuum expectation value will kill these extra terms and hence GG? generates all the meander diagrams, since any meander can be made by gluing together two arch diagrams. Each closed loop in the meander diagram will give a factor of δaa = m. Thus the correct weightings are generated and hence GG? = 1 + M (x, m). (35)

4.2

X-diagrams

? It is convenient now to introduce a new set of variables, {Xa , Xa }, de?ned by

Gua Xa = √ , m 13

u? G? a ? Xa = √ . m

(36)

(a) a1 a2 b1 b2 an-1 an bn-1 bn a1 a2 b1 b2 an-1 bn-1 δa ,b n n

(b)

Figure 18: (a) Applying equation (29) to ua1 · · · uan u?n · · u?1 . b b· ?. (29) twice to a term in GG

(b) Applying equation

So that |X| ≡

2

m ? Xa Xa = GG? , a=1

(37) (38)

|X|2 = 1 + M (x, m). The equations for Xa equivalent to (29) and (30) are

? Xa Xb =

1 δab |X|2 , m ?|? = 1.

(39) (40)

Xa |? = 0, From (31) we have

? ?|Xb = 0,

? ? |X|2 = (1 + cmXa Xa ) 1 + cmXb Xb ? ? ? = 1 + cm Xa Xa + Xa Xa + c2 mXa |X|2 Xa ,

(41) (42)

where repeated indices are summed over. In a similar fashion to the u, u? diagrams, this can be written diagrammatically, in this case as

§¤

= 1 + cm

§¤

+

§¤

+ c2 m

¨ ??

,

(43)

where the ends corresponding to non-daggered operators are on the left of the vertical line and those for the daggered operators are on the right. Two ends are joined into an arch whenever the corresponding operators share a summed over index. The vertical line is only present in order to indicate the boundary between non-daggered and daggered operators. Equation (39) implies that

? ? Xa Xa Xb Xb =

1 ? ? Xa Xc Xc Xa , m 1 ? Xa Xa Xc Xc , m 1 ?¨ ? m

(44)

which was used above, and

? Xb Xa Xa Xb =

(45)

which can be drawn respectively as

§¤ §¤

=

(46)

14

and

. (47) m In principle one could repeatedly substitute equation (42) into itself in order to expand ? |X|2 in terms of Xa and Xa . However this rapidly becomes tedious and it is necessary to ?nd a simpler way of calculating |X|2 . Let us de?ne {An } by A0 = 1, and {Yn } by Y1 = cm A1 =

§¤

1 §¤ §¤ ??

=

,

A2 =

¨ ??

,

A3 =

¤ §? ?

, ···

(48)

§¤

+

§¤

,

Yn = Yn?1 .

' $

(49)

→ §¤ For later use we will de?ne the following notation, that is an operator, which multi← §¤ §¤ plies the expression following it by Xa Xa (that is, ) on the left-hand side, whereas ? ? multiplies the expressing following it by Xa Xa on the right-hand side. Thus, Y1 = cm and Y2 = c

§¤

+

§¤

= cm

→ §¤ §¤ ← +

(50)

§¤ §¤ §¤ §¤

+

=c

→ §¤ ← §¤ §¤ . +

(51)

Now equation (43) can also be written as A1 = 1 + Y1 + αA2 , where α ≡ c2 m = xm. This equation generalizes to An = An?1 + Yn + αAn+1 . Note that we wish to evaluate A1 since A1 =

§¤

(52)

(53)

= |X|2 = GG? = 1 + M (x, m).

(54)

The next step is to rewrite A1 in terms of {Yn } and α. We rewrite (53) as 0 = α (An+1 ? f An ) ? where f (α) is given by αf + and de?ne An by An = An ? f An?1 . 15 (57) 1 = 1, f f (α) = √ 1 1 ? 1 ? 4α 2α (56) 1 (An ? f An?1 ) + Yn , f (55)

Then from (55) An = f Yn + αf An+1 . This yields immediately A1 = f + A1 = f. 1 + Y1 + (αf )Y2 + (αf )2 Y3 + · · · . (59) (58)

The ?rst term in A1 is f (α), which generates the Catalan numbers (see equation (6)). (n) These correspond to the set of numbers Mn in M (x, m), that is, the leading diagonal of table 1.

4.3

Calculation of Yn

In order to calculate A1 , or at least an approximation to it, we need to consider how to calculate Yn . It is worth noting that Y1 = 0 from (40). Now consider Y2 , Y2 = c so that Y2 = 1 ? cαf 2 → ← → ← §¤ §¤ §¤ §¤ + + A1 = cf 1 + Y1 + (αf )Y2 + (αf )2 Y3 + · · · , → ← §¤ §¤ +

?1

(60)

cf

→ ← §¤ §¤ + (1 + Y1 ) + O(Y3 ) .

(61)

So far all the equations have been exact, but from now on in this expression we shall ignore the terms Yn for which n ≥ 3. This will make the calculation more tractable, but will cause us to miss out some of the meander diagrams in our generating functions. That is, the equation for A1 will contain only a subset of the meanders. Now, Y2 = cf

∞ n=0

cαf 2

n

→ ← n+1 → ← §¤ §¤ §¤ §¤ + + 1 + cm . + O(Y3 )

(62)

and rearranging this gives Y2 = f Y1 + xmf 1 + xf 2 m

∞ n=1

cαf 2

n?1

→ ← n+1 §¤ §¤ + . + O(Y3 ).

(63)

This summation will be truncated so as to keep terms up to and including n = 2, again this will cause us to lose some diagrams, Y2 = f Y1 m + xmf 1 + xf 2 + O(Y3 ) + O → ← 2 §¤ §¤ + + cαf 2 → ← 3 §¤ §¤ + . (64)

→ ← 4 §¤ §¤ + .

From now on the omitted terms will just be indicated by three dots, however it should be understood that this means terms of the form indicated in the second line of the above 16

equation. To simplify this equation, consider that, → ← 2 §¤ §¤ + . = = and similarly → ← 3 → →→ ←← ← 3 → ← ?¨ §¤ §¤ §¤ §¤ §¤ §¤ §¤ §¤ §¤ §¤ ? . + . = + . + + m

A2

→→ ←← →← §¤ §¤ §¤ §¤ §¤§¤ + . +2 . →→ ←← 2 ?¨ ? §¤ §¤ §¤ §¤ + . + m (65)

(66)

Now from (59), A2 = f (A1 + Y2 ) + O(Y3 ) so that → ← 3 §¤ §¤ + . = = → →→ ←← ← 3f → ← §¤ §¤ §¤ §¤ §¤ §¤ §¤ §¤ + + . + (A1 + Y2 ) + · · · m → →→ ←← ← 3f c → ← 2 3f §¤ §¤ §¤ §¤ §¤ §¤ §¤ §¤ Y2 + + + A1 + · · · , . + mc m

(67)

where we can use (59) to eliminate A1 . Basically one can repeat this process of substituting equations into (67) to gradually increase the coe?cient in front of Y2 , which has the e?ect of improving the accuracy of the ?nal result. The actual equation that is ?nally used is somewhat arbitrary, but eventually one gains an expression such as → ← 3 §¤ §¤ + . = + 1 ? 3xf 2 ? 3x2 f 4

?1

→→ → ←← ← §¤ §¤ §¤ §¤ §¤ §¤ + . + ···. (68)

3f 2 c → ← 2 3f §¤ §¤ Y2 + + . mc m

Substituting this into (64) gives, after a bit of manipulation, Y2 = where D ≡ 1 ? 3xf 2 ? 3x2 f 4 1 + m 1 + xf 2 E ≡ F J This gives us Y2 = F A2 + · · · = a′ A2 + · · · , D 17 (71) f 1 ? 3xf 2 ? 3x2 f 4 , m ≡ 2xf 1 + xf 2 1 ? 3xf 2 , , 1 D E.Y1 + F.A2 + →→ → ←← ← F m →→ ←← §¤ §¤ §¤ §¤ §¤ §¤ §¤ §¤ §¤ §¤ + + . +J . 2 + · · · , (69)

≡ x2 m2 f 3 c 1 + xf 2 .

(70)

where we de?ne a′ = F/D. To calculate the critical behaviour it is necessary to have a formula for Y3 . This can be derived from (69) using (49), that is, 1 Y3 = D Now, Fm E.Y2 + F.A3 + 2

' $ ' $ §¤ §¤ §¤ §¤

+

+J

$ $ ' ' §¤ §¤ §¤ §¤ §¤ §¤

+

+ ···. (72)

' $ ¨ ' $ ¨ §¤ §¤ §¤ §¤ 1 ? ? §¤ §¤ ? ?

+

=

m

+

,

(73)

where using (59) to substitute for +

§¤

, and keeping only the relevant terms, we have

¨§¤ §¤ ¨ ?? ??

' $ ' $ §¤ §¤ §¤ §¤

= cf =

+

# §¤ ? ? ?§¤ ? cf # + m

+ ··· Y3 f + ···. m (74)

+ ··· =

In a similar fashion, we can extract a term proportional to Y3 by the following manipulation,

' ' $ $ §¤ §¤ §¤ §¤ §¤ §¤ 1

+

=

m

§¤ ? ? ? §¤ ? ?? ? ?

+

= cf

? ? ? §¤ §¤ ? ? ? ? ?

+

+ ···

cf = m cf 2 = m

' $ ' $ §¤ §¤ §¤ §¤ §¤ §¤

+

+ ··· cf 3 Y3 + · · · . m2 (75)

' $ ' $ §¤ §¤ §¤ §¤

+

+ ··· =

Substituting this into equation (72) gives Y3 = 1 D Jcf 3 1 Y3 + · · · . E.Y2 + F.A3 + F f Y3 + 2 m2 (76)

Rearranging this gives us, Y3 = where we have de?ned 1 Jcf 3 H ≡ D ? Ff ? , 2 m2 This relation generalizes to Yn = aAn + bAn?1 + · · · , 18 for n ≥ 3. (79) a≡ F , H b≡a E . D (78) E F A3 + Y2 + · · · = aA3 + bA2 + · · · , H H (77)

4.4

Now

Meander generating function

An = An?1 + αAn+1 + Yn , so that for n ≥ 3, 0 = αAn+1 + (a ? 1)An + (b + 1)An?1 + · · · .

(80)

(81)

? Let us de?ne an operator O, which adds an outer arch to the diagram that it is operating ? . Then since OA = A ? ? n on, that is, OY = Xa Y Xa n+1 , ? ? 0 = αO2 A2 + (a ? 1)OA2 + (b + 1)A2 + · · · ? and hence multiplying by exp(y O) gives 0= α ? ?y

2

(82)

+ (a ? 1)

? + (b + 1) ?y

? exp(y O)A2 + · · · .

(83)

Keeping only the explicitly written term, the solution is ? exp(y O)A2 = Ceky , where k= 1 1?a? 2α (84)

(1 ? a)2 ? 4α(b + 1) .

(85)

So that An = Ckn?2 for n ≥ 2. Using the relation (80) for n = 1, 2 gives us the approximate result A1 = 1 + αC, C= 1? a′ 1 . ? α ? αk (86)

Expanding this using equations (70), (78) and (85) gives A1 = 1 + mx + (2m + 2m2 )x2 + (8m + 12m2 + 5m3 )x3 +(38m + 84m2 + 56m3 + 14m4 )x4 + O(x5 ) + missing diagrams. (87)

Comparing with table 1, we ?nd that the approximate formula generates the correct coe?cients up to x4 , except for the coe?cient of mx4 , which is lower than it should be. Expanding the series further one sees that more and more of the coe?cients are below the correct value, that is, as expected we are undercounting the number of diagrams as a result of the terms that were dropped during the calculation. Now the singular behaviour of A1 is given by the singularity in k caused by the vanishing of the square root. This gives a relation that determines approximately xc , the critical value of x, as a function of m. The quantity xc (m) has been calculated numerically using the equations given and the results are plotted in ?gure 20. 19

4.5

Semi-meanders

So far we have only discussed how to apply the X-diagrams to the problem of enumerating meanders, but in fact they can also be used to calculate semi-meanders. Suppose we consider a semi-meander with winding number equal to one (?g. 19). Note that the winding number (denoted by w) is the minimum number of bridges that would need to be added if we were to extend the river to in?nity on the righthand side. Meanders are just semi-meanders with winding number zero and are generated by GG? . Semi-meanders with w = 1 are generated by the expression c Gua GG? u? G? . That is, a the upper part of the diagram consists of two arch con?gurations separated by a ua , which is linked to a u? below, that separates two inverted arch con?gurations. More generally a a

ua ua

Figure 19: A typical semi-meander with winding number of one.

semi-meander with winding number w is generated by cw Gua1 G · · · uaw GG? u? w · · · G? u? 1 G? . a a So that the generating function for semi-meanders is

? ? ? ? ? ? S(c, m) = Xa Xa + cm Xa Xb Xb Xa + c2 m2 Xa Xb Xc Xc Xb Xa + · · · ,

(88)

which can be rewritten as S(c, m) =

∞ w=0

(cm)w Aw+1 .

(89)

Using our approximate formula for An this gives S(c, m) = 1 + Cm x + A power series expansion of this expression gives S(c, m) = 1 + mc + (m + m2 )c2 + (2m + 2m2 + m3 )c3 + (4m + 6m2 + 3m3 + m4 )c4 +(8m + 16m2 + 11m3 + 4m4 + m5 )c5 + O(c6 ) + missing diagrams, (91) c . 1 ? mck (90)

which is correct up to O(c5 ) except for the coe?cient of mc5 . As expected this formula undercounts the number of diagrams. 20

The critical behaviour for semi-meanders is caused by the vanishing of the quantity (1 ? mck) for large m, and by the vanishing of the square root in the formula for k at < small m (that is, m ? 0.6). The function xc (m) for semi-meanders has been calculated numerically and is displayed in ?gure 20.

90 Meander Semi-meander 80

70

60

50 1/xc 40 30 20 10 0 0 1 2 3 4 m 5 6 7 8

Figure 20: Plot of 1/xc as a function of m for meanders and semi-meanders using the approximate formulae.

4.6

Discussion

The graph (?g. 20), which plots the approximate value of 1/xc as a function of m for both meanders and semi-meanders, shows a number of interesting features. First of all it should be noted that the missing diagrams in the power series expansions for M (x, m) and S(c, m) tend to be those with lower powers of m, whereas the coe?cients of the highest powers of m, (mn xn for meanders and mn cn for semi-meanders,) are exact. Thus one would expect our approximation to be exact in the m → ∞ limit and least accurate in the m → 0 limit. Unfortunately, the most interesting behaviour occurs for small values of m. In reference [12] the authors perform a computer enumeration of the semi-meander diagrams. They conclude that in the function S(c, m), there is a phase transition at m ≈ 2, between a meander-like phase (with irrelevant winding number) and a phase 21

10 Meander Semi-meander 9

8

7 1/Sqrt[xc]

6

5

4

3

2 0 1 2 3 4 m 5 6 7 8

√ √ Figure 21: Plot of R(m) = 1/ xc for meanders and R(m) = 1/ xc for semi-meanders, using the approximate formulae.

in which winding is relevant. Figure 20 shows indications of such a phase transition developing at around m ≈ 0.6. Below this value of m, xc for semi-meanders is equal to that for meanders. Above m ≈ 0.6 the two curves split apart. This is caused by a change in the form of the critical behaviour for the semi-meanders, as indicated in the previous section. In the next section we will examine the behaviour of the winding number for semi-meanders as a function of m, and this also gives evidence of a phase transition at m ≈ 0.6. One would expect that, as our approximation is improved by including more of the missing diagrams, the location of the phase transition would become clearer and be in closer agreement with ref. [12]. √ Figure 21 shows our approximation to 1/ xc as a function of m. This can be directly compared with ?g. 9 of ref. [12], which calculates the same quantities, but using a di?erent method. The two graphs are very similar, although it is immediately apparent that the undercounting of diagrams has pushed the curves on our graph lower than they should be. √ In particular, that paper derived an exact value for R(m) = 1/ xc (for meanders) and R(m) similarly de?ned for semi-meanders. The result they gave was R(1) = R(1) = 4, showing that our approximate value of R(1) = R(1) = 3.3 is too low. Even so the general form of our graphs is the same as that derived in ref. [12], lending support to the results in that paper. 22

In the limit m → 0 our approximation gives R(0) = R(0) = 2.6. Again this is too low as we have already proved in section 3.3 that R(0) ≥ 2.970. Reference [12] on the other hand has R(0) = R(0) = 3.5, which is comfortably within the known bounds. It should perhaps be noted that the paper [12] also showed that for m → ∞ one has √ R ? m and R ? m. This behaviour can clearly be seen in the linearity of the lines for meanders (in ?g. 20) and semi-meanders (in ?g. 21) at large m.

4.7

Winding number

The phase transition for the semi-meander diagrams is believed to be a winding transition with an average winding per bridge equal to zero in one phase and non-zero in the other. This suggests that we should examine more closely the winding numbers of diagrams in the semi-meander generating function S(c, m). From (89) we see that w =

∞ Cmc 1 (cm)w w Aw+1 = . S(c, m) w=0 S(1 ? mck)2 Ck w?1

(92)

Now from (3) the average number of bridges n is given by n = So that c ?S . S ?c ?S ?c

?1

(93)

which gives a measure of the average number of windings per bridge; we expect that 0 ≤ w / n ≤ 1. Using a symbolic algebra program to calculate (94) and evaluating for di?erent values of m (using our previously calculated values of xc (m)) gives us the graph shown in ?g. 22. This graph shows clear evidence of a phase transition occurring at about m ≈ 0.6. As discussed in the previous section we are using an approximate generating function, which is known to be inaccurate for small values of m, so this result should be treated cautiously. However it is at least encouraging to see such clear signs of a phase transition, and one could hope that further e?ort to improve the m → 0 behaviour of the generating functions would increase the accuracy of this estimate.

Cm w = n (1 ? mck)2

,

(94)

5

Conclusion

In this paper we have shown how one can tackle the meander problem using diagrammatical techniques. In section 3 the problem of counting connected meanders was converted to one of enumerating folded trees. Using this connection it was shown that 2.970 ≤ R ≤ 4, 23 (95)

0.8

0.7

0.6

0.5 <w>/<n>

0.4

0.3

0.2

0.1

0 0 1 2 3 4 m 5 6 7 8

Figure 22: Graph of w / n plotted as a function of m, showing evidence of a phase transition.

where R ≡ R(0) is de?ned by (9) and gives a measure of the exponential growth of connected meanders as the number of bridges is increased. This is an improvement over the usual bounds of 2 ≤ R ≤ 4, and is consistent with the numerical estimate [12] of R ≈ 3.5. It may be possible to improve this lower bound, by modifying the method to increase the number of folded con?gurations that are included. Signi?cant improvements seemed to be quite di?cult to achieve, but the idea may be worth further study. In section 4 we used a non-commutative representation of the meander problem to calculate approximate formulae for the generating functions of both meanders and semimeanders. The approximations were necessary in order to make the equations tractable and resulted in the loss of some diagrams, which should have been present in the generating functions. Nevertheless we have managed to extract graphs showing the behaviour of xc for the two models, which were qualitatively the same as those generated using a di?erent method [12]. In particular we have shown that there is a region over which R(m), for the semi-meanders, is equal to R(m), for the meanders, giving an indication of the existence of a phase transition. Examination of the average winding number per bridge shows much clearer evidence of the phase transition and yields an estimated critical value of mc ≈ 0.6. Comparison with ref. [12], which has mc ≈ 2, suggests that our estimate is too low. It would seem to be worthwhile to attempt to improve the approximations used, 24

in order to narrow down the exact location of this phase transition. Many questions remain unanswered concerning the meander problem and the critical behaviour of the semi-meander generating function, and these must be left for future investigation.

Acknowledgements

MGH would like to acknowledge the support of the European Union through their TMR Programme, and to thank Charlotte Kristjansen and Yuri Makeenko for interesting discussions.

References

[1] V. Arnold, Siberian Math. Journal 29 (1988) 717. [2] K. H. Ko and L. Smolinsky, Paci?c J. Math. 149 (1991) 319. [3] K. Ho?man, K. Mehlhorn, P. Rosenstiehl and R. Tarjan, Information and Control 68 (1986) 170. [4] S. Lando and A. Zvonkin, Theor. Comp. Science 117 (1993) 227; Selecta Math. Sov. 11 (1992) 117. [5] J. Touchard, Canad. J. Math. 2 (1950) 385. [6] P. Di Francesco, O. Golinelli and E. Guitter, SACLAY-SPhT/95-059, hepth/9506030. [7] Y. Makeenko, Nucl. Phys. Proc. Suppl. 49 (1996) 226, hep-th/9512211. [8] Y. Makeenko and I. Chepelev, ITEP-TH-13/95, hep-th/9601139. [9] P. Di Francesco, O. Golinelli and E. Guitter, Commun. Math. Phys. 186 (1997) 1, hep-th/9602025. [10] P. Di Francesco, Commun. Math. Phys. 191 (1998) 543, hep-th/9612026. [11] P. Di Francesco, J. Math. Phys. 38 (1997) 5905, hep-th/9702181. [12] P. Di Francesco, O. Golinelli and E. Guitter, Nucl. Phys. B482 (1996) 497, hepth/9607039.

25

- A Mathematical Approach to the Plato's Problem
- A Heuristic Approach to Solving the Software Clustering Problem
- A New Closed Form Approach to the Absolute Orientation Problem
- Ant colony system A cooperative learning approach to the traveling salesman problem
- A collaborative filtering approach to mitigate the new user cold start problem
- A probabilistic approach to the dychotomy problem
- TCP Connections for P2P Apps A Software Approach to Solving the NAT Problem
- Order statistics a new approach to the problem of blind source separation
- A new approach to the minimum cut problem
- A set theoretic approach to the simultaneous localization and map building problem
- A Novel Approach Applied to the Largest Clique Problem
- A new approach to the giant component problem
- A Multilevel Approach to the Travelling Salesman Problem
- A Deterministic Approach to the Protein Design Problem
- A Lagrangian relaxation approach to the edgeweighted clique problem

更多相关文章：
更多相关标签：