A permutation and combination problem

[basichan]

Homework Statement

There are 2n points on a circle, we want to connect each two of them to make a pattern of connection in the way that there is no cross between the lines of connection, and all the lines have to be inside the circle and on the plane of the circle.
Question: How many different patterns of connection there are?

Homework Equations

This is a relevant question to count the number of planar Feynman Diagrams that without interaction insider a loop.

The Attempt at a Solution

we can check that in the case of n=1, there is 1 pattern, n=2, there are 2 different patterns, n=3, there are 5 different patterns.

 

[LCKurtz]

Homework Statement

There are 2n points on a circle, we want to connect each two of them to make a pattern of connection in the way that there is no cross between the lines of connection, and all the lines have to be inside the circle and on the plane of the circle.
Question: How many different patterns of connection there are?



we can check that in the case of n=1, there is 1 pattern, n=2, there are 2 different patterns, n=3, there are 5 different patterns.

Please be more specific in what the definition of a "pattern of connection" is.

 

[basichan]

Please be more specific in what the definition of a "pattern of connection" is.

It means that the only important thing is which two points is connected, the shape of the line of connection doesn't matter.

 

[basichan]

Please be more specific in what the definition of a "pattern of connection" is.

For example, if there are two points on the circle, there is trivially one way to connect the two points. No matter the line is a straight line or a curve.

 

[LCKurtz]

That doesn't tell me enough. What are the rules? If I have 4 points on a circle and some lines between some of them, how do I tell if I have a "legal" pattern of connection? Please give the definition since this topic is unfamiliar to me.

 

[basichan]

That doesn't tell me enough. What are the rules? If I have 4 points on a circle and some lines between some of them, how do I tell if I have a "legal" pattern of connection? Please give the definition since this topic is unfamiliar to me.

I am not sure what your mean. I mean any line or curve you can draw is legal, the rules are the lines cannot cross each other, and cannot go beyond the plane of the circle and have to be inside the circle. That's all.

 

[basichan]

That doesn't tell me enough. What are the rules? If I have 4 points on a circle and some lines between some of them, how do I tell if I have a "legal" pattern of connection? Please give the definition since this topic is unfamiliar to me.

I would like to say it again, the legal curve or lines are these doesn't go across any of other lines or curves, any any point can only be connected to another unique point.

 

[basichan]

That doesn't tell me enough. What are the rules? If I have 4 points on a circle and some lines between some of them, how do I tell if I have a "legal" pattern of connection? Please give the definition since this topic is unfamiliar to me.

If there are 4 points on the circle, a, b, c, d in turn for example, we can only connect a with b, and c with d, or a with d, b with c. These is all the possible way we can do.

 

[Avodyne]

Interesting problem. I think I can express it a little more simply: A circle has 2n equally spaced points on it. The points are to be connected in pairs by straight line segments. The line segments are not allowed to intersect each other. How many ways are there to draw these line segments? Call this number N(2n).

Let's number the points consecutively around the circle from 1 to 2n. You can convince yourself that each segment must connect an odd-numbered point with an even-numbered point. (Otherwise, an odd number of points will be isolated on each side of the segment, and we will not be able to pair them all up with other segments that do not cross the first segment.) Suppose point #1 is connected to point #2k. This cuts the circle into two pieces, one with 2k-2 unconnected points and one with 2n-2k unconnected points. Points in one piece cannot be connected to points in the other piece without crossing the first segment. Each piece by itself is then equivalent to the original circle problem, so that the number of ways to connect the points in the piece with 2k-2 points is N(2k-2). From this you can construct a recursion relation that you could solve numerically (and possibly analytically).

 

[basichan]

Interesting problem. I think I can express it a little more simply: A circle has 2n equally spaced points on it. The points are to be connected in pairs by straight line segments. The line segments are not allowed to intersect each other. How many ways are there to draw these line segments? Call this number N(2n).

Let's number the points consecutively around the circle from 1 to 2n. You can convince yourself that each segment must connect an odd-numbered point with an even-numbered point. (Otherwise, an odd number of points will be isolated on each side of the segment, and we will not be able to pair them all up with other segments that do not cross the first segment.) Suppose point #1 is connected to point #2k. This cuts the circle into two pieces, one with 2k-2 unconnected points and one with 2n-2k unconnected points. Points in one piece cannot be connected to points in the other piece without crossing the first segment. Each piece by itself is then equivalent to the original circle problem, so that the number of ways to connect the points in the piece with 2k-2 points is N(2k-2). From this you can construct a recursion relation that you could solve numerically (and possibly analytically).

Yes, I actually already have the recursion relation before I post this question, but what I need is the formal algebraic expression.

 

[Avodyne]

You should have said that you found a recursion relation in your original post!

To get a closed form expression, try this: formally define the function
$$G(x)\equiv\sum_{n=0}^\infty N_{2n}x^n$$Now write the square of this function as a double series. By manipulating this double series and using the recursion relation, you should be able to convert it into a single series. This will give you a closed-form equation for G.

 

[basichan]

You should have said that you found a recursion relation in your original post!

To get a closed form expression, try this: formally define the function
$$G(x)\equiv\sum_{n=0}^\infty N_{2n}x^n$$Now write the square of this function as a double series. By manipulating this double series and using the recursion relation, you should be able to convert it into a single series. This will give you a closed-form equation for G.

I just won't to lead others to my way of solution, maybe there could be another way. So that I haven't post it.

 

[basichan]

You should have said that you found a recursion relation in your original post!

To get a closed form expression, try this: formally define the function
$$G(x)\equiv\sum_{n=0}^\infty N_{2n}x^n$$Now write the square of this function as a double series. By manipulating this double series and using the recursion relation, you should be able to convert it into a single series. This will give you a closed-form equation for G.

You are correct, I got it, but how do you know we need to define a function like that to solve it?

 

[Avodyne]

G(x) is called the "generating function" of the infinite sequence. The generating function is often easier to work with than the sequence itself. For example, a linear recursion relations for a sequence can often be translated into a linear differential equation for G(x). In this case, the recursion relation looked like what you get when you multiply two series together and reorganize them into a single series, so using a generating function was worth a try. That said, I am a little surprised that it all works out so straightforwardly in this case.

 

[basichan]

G(x) is called the "generating function" of the infinite sequence. The generating function is often easier to work with than the sequence itself. For example, a linear recursion relations for a sequence can often be translated into a linear differential equation for G(x). In this case, the recursion relation looked like what you get when you multiply two series together and reorganize them into a single series, so using a generating function was worth a try. That said, I am a little surprised that it all works out so straightforwardly in this case.

Thank you for your explanation, then what kind of lecture, subject or book would teach such techniques?

 

[slider142]

Thank you for your explanation, then what kind of lecture, subject or book would teach such techniques?

This book is written with generating functions as its main topic: http://www.math.upenn.edu/~wilf/DownldGF.html .

 

[Avodyne]

Another freely available book is Richard Stanley's Enumerative Combinatorics: http://math.mit.edu/~rstan/ec/

By the way, I realized that the solution to this problem is the Catalan number C_n, which is the solution to many seemingly different combinatoric problems: http://en.wikipedia.org/wiki/Catalan_number