Discrete math problem college level question

In summary, the conversation discusses a problem where 2n people are sitting at a round table and shaking hands in pairs without any crossed handshakes. The task is to determine the number of possible shaking hand arrangements, denoted as S_n, for a given number of people, starting with S_10. The conversation suggests drawing circles and connecting points to find a pattern, with the given values of S_n being 1, 2, 4, etc. There is also a mention of using probability to solve the problem.
  • #1
afang
5
0
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.
 
Physics news on Phys.org
  • #2
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.
 
  • #3
I do not know how to procede. The question is unclear to me. For S_4 is the answer 4 ways? Thanks.
 
  • #4
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:
  • #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.
 
  • #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
etc...
 

1. What is discrete math?

Discrete math, also known as finite math, is a branch of mathematics that deals with discrete objects and quantities rather than continuous ones. It includes topics such as logic, set theory, combinatorics, graph theory, and algorithms.

2. What makes a math problem "college level"?

A college level math problem typically requires a deeper understanding of mathematical concepts and the ability to apply them in more challenging and complex scenarios. It may also involve multiple steps and require critical thinking and problem-solving skills.

3. How is discrete math used in the real world?

Discrete math has applications in various fields such as computer science, engineering, finance, and cryptography. It is used to solve problems involving discrete structures and processes, such as designing efficient algorithms, analyzing networks, and making decisions based on logical reasoning.

4. What are some strategies for solving discrete math problems?

Some strategies for solving discrete math problems include breaking down the problem into smaller, more manageable parts, using visual representations such as graphs or tables, and applying logical reasoning and critical thinking skills. It is also helpful to practice regularly and seek help from teachers or peers when needed.

5. Are there any specific formulas or techniques that are commonly used in discrete math problems?

Yes, some commonly used formulas and techniques in discrete math include the fundamental counting principle, the binomial theorem, induction, and various graph algorithms such as Dijkstra's algorithm and Kruskal's algorithm. However, it is important to understand the underlying concepts and not just rely on memorizing formulas.

Similar threads

  • Introductory Physics Homework Help
Replies
2
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Replies
4
Views
1K
  • Math Proof Training and Practice
2
Replies
61
Views
6K
  • Precalculus Mathematics Homework Help
Replies
2
Views
2K
Replies
4
Views
3K
  • STEM Educators and Teaching
Replies
3
Views
1K
  • Introductory Physics Homework Help
Replies
14
Views
2K
Back
Top