Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Discrete math problem college level question

  1. Sep 22, 2004 #1
    Suppose 2n people sit on a round table and are shaking hands in
    pairs. Suppose that etiquette is observed and no 2 shakes cross. Let
    S_n be the number of possible shaking hands arrangements of this sort.

    Determine S_10.
  2. jcsd
  3. Sep 22, 2004 #2


    User Avatar
    Staff Emeritus
    Gold Member

    Welcome to the forums!

    Try with small numbers first, adding one person at a time. How many more handshakes are needed per added person? After the first few, you should be able to see a pattern.
  4. Sep 23, 2004 #3
    I do not know how to procede. The question is unclear to me. For S_4 is the answer 4 ways? Thanks.
  5. Sep 23, 2004 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Draw a circle with 2n numbered points on its circumference...say with n=2,4,6,... etc. Now draw lines connecting these points such that (i) all points are connected - this is not stated, but I'm ammuming it is implicit, and (ii) no two lines intersect. After having drawn the lines, list the end-points of these lines as a set of unordered pairs.

    How many such different sets are there, for a given n, and a given ordering of the people (don't change their positions, only change the lines) ?

    Do you see a pattern across different values of n ?

    (If my interpretation of this problem is correct, S(1) = 1, S(2) = 2, ...you find the rest)
    Last edited: Sep 23, 2004
  6. Sep 23, 2004 #5
    I guess with that patter then the number of possible shaking hand arrangements = n.
    I guess I need to ask my professor to clarify the question if all people are shaking.
  7. Sep 28, 2004 #6
    Hello does anyone have a faster way using probability to solve this problem? Counting it out would be difficult. I know however, that the pattern has been
    S_1 = 1
    S_2 = 2
    S_3 = 4
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook