1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A permutation and combination problem

  1. Jul 31, 2013 #1
    1. The problem statement, all variables and given/known data
    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?


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


    3. 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.
     
  2. jcsd
  3. Jul 31, 2013 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Please be more specific in what the definition of a "pattern of connection" is.
     
  4. Jul 31, 2013 #3
    It means that the only important thing is which two points is connected, the shape of the line of connection doesn't matter.
     
  5. Jul 31, 2013 #4
    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.
     
  6. Jul 31, 2013 #5

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  7. Jul 31, 2013 #6
    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.
     
  8. Jul 31, 2013 #7
    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.
     
  9. Jul 31, 2013 #8
    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.
     
  10. Jul 31, 2013 #9

    Avodyne

    User Avatar
    Science Advisor

    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).
     
    Last edited: Jul 31, 2013
  11. Jul 31, 2013 #10
    Yes, I actually already have the recursion relation before I post this question, but what I need is the formal algebraic expression.
     
    Last edited: Jul 31, 2013
  12. Jul 31, 2013 #11

    Avodyne

    User Avatar
    Science Advisor

    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
    [tex]G(x)\equiv\sum_{n=0}^\infty N_{2n}x^n[/tex]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.
     
    Last edited: Jul 31, 2013
  13. Aug 1, 2013 #12
    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.
     
  14. Aug 1, 2013 #13
    You are correct, I got it, but how do you know we need to define a function like that to solve it?
     
  15. Aug 1, 2013 #14

    Avodyne

    User Avatar
    Science Advisor

    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.
     
  16. Aug 1, 2013 #15
    Thank you for your explanation, then what kind of lecture, subject or book would teach such techniques?
     
  17. Aug 1, 2013 #16
    This book is written with generating functions as its main topic: http://www.math.upenn.edu/~wilf/DownldGF.html .
     
  18. Aug 2, 2013 #17

    Avodyne

    User Avatar
    Science Advisor

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: A permutation and combination problem
Loading...