Problem Statement
Consider a meeting of n businessmen sitting around a circular table. To start the meeting, they must shake hands. Each businessman shakes the hand of exactly one other businessman. All handshakes happen simultaneously. We say that the shake is perfect if no arms cross each other. Given an int n, return the number of perfect shakes that exist for n businessmen. See examples for further clarification.
Definition
- Class:
- HandsShaking
- Method:
- countPerfect
- Parameters:
- int
- Returns:
- long
- Method signature:
- long countPerfect(int n)
- (be sure your method is public)
Notes
- Businessmen are distinguishable. Rotating a perfect shake can yield a different perfect shake (see example 1).
Constraints
- n will be between 2 and 50, inclusive.
- n will be even.
Examples
2
Returns: 1
Two businessmen have only one possibility - just to shake each other's hand.
4
Returns: 2
Two out of three possible shakes are perfect.
6
Returns: 5
8
Returns: 14
10
Returns: 42
12
Returns: 132
14
Returns: 429
16
Returns: 1430
18
Returns: 4862
20
Returns: 16796
22
Returns: 58786
24
Returns: 208012
26
Returns: 742900
28
Returns: 2674440
30
Returns: 9694845
32
Returns: 35357670
34
Returns: 129644790
36
Returns: 477638700
38
Returns: 1767263190
40
Returns: 6564120420
42
Returns: 24466267020
44
Returns: 91482563640
46
Returns: 343059613650
48
Returns: 1289904147324
50
Returns: 4861946401452