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++
    Event
    Cinquè Concurs de Programació de la UPC - Final
    Date
    2007-10-03