Swapping parentheses P37366


Statement
 

pdf   zip

html

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

1
5
 ⎛
⎜
⎜
⎝
4
9
 + 
3
9
 + 
3
9
 + 
3
9
 + 
3
9
 ⎞
⎟
⎟
⎠		 = 
16
45
 ≃ 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.

Public test cases

  • Input

    1
2
3
10
30

    Output

    0.000000
0.250000
0.355556
0.585699
0.731991
    • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++ Python