Let P_{n} be the set of words with exactly n opening parentheses and n closing parentheses, such that every ‘)’ matches a ‘(’. For instance,
P_{3} = { “((()))” , “(()())” , “(())()” , “()(())” , “()()()” } . |
Consider the following experiment: Choose one word w from P_{n} at random. Then, pick one ‘(’ and one ‘)’ of w, independently at random, and swap them. What is the probability that the result is also a word in P_{n}?
For example, let n = 3. If we choose w = “((()))”, then there are exactly four swaps that produce a word in P_{3}, namely 2-4, 2-5, 3-4, 3-5. The rest of swaps (1-4, 1-5, 1-6, 2-6, 3-6) are incorrect. Each of the other words in P_{3} has three correct swaps. Therefore, the probability for n = 3 is
| ⎛ ⎜ ⎜ ⎝ |
| + |
| + |
| + |
| + |
| ⎞ ⎟ ⎟ ⎠ | = |
| ≃ 0.355556 . |
Input
Input consists of several integer numbers n between 1 and 30.
Output
For every given n, print with six digits after the decimal point the probability that swapping a random ‘(’ with a random ‘)’ of a random word in P_{n} produces a word also in P_{n}.
Input
1 2 3 10 30
Output
0.000000 0.250000 0.355556 0.585699 0.731991