Swapping parentheses P37366
Let Pn be the set of words with exactly n opening parentheses and n closing parentheses, such that every ‘)’ matches a ‘(’. For instance,
| P3 = { “((()))” , “(()())” , “(())()” , “()(())” , “()()()” } . |
Consider the following experiment: Choose one word w from Pn 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 Pn?
For example, let n = 3. If we choose w = “((()))”, then there are exactly four swaps that produce a word in P3, 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 P3 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 Pn produces a word also in Pn.
Input
1 2 3 10 30
Output
0.000000 0.250000 0.355556 0.585699 0.731991
- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++ Python