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!

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