Lesson 5

Second Proof: Cyclic Shifts.

Consider a path of \(n+1\) up-steps and \(n\) down-steps. The number of such paths is \(\binom{2n+1}{n}\). Let us call such a path good if it starts with an up-step and never descends to the level of the starting point. Good paths are in one-to-one correspondence with Dyck paths: if we cut off the first up-step from a good path, we get a Dyck path, and vice versa.

Now consider a table of width \(2n+1\). Rows will be indexed by all paths. For a row \(p\) and a column \(0 \le i < 2n+1\), the corresponding cell will contain the path \(p\), cyclically shifted by \(i\) positions. It is easy to see that each column will list all paths (each column is simply a permutation of the first column). Therefore, the fraction of good paths in a column equals the fraction of good paths in the entire table. Below, we will show that each row contains exactly one good path. In other words, each path has exactly one cyclic shift that is a good path. Thus, \[C(n)=\frac{1}{2n+1}\cdot \binom{2n+1}{n}\ .\]

The code below outputs all sequences of four opening and three closing brackets and all their cyclic shifts. Each valid cyclic shift is marked with an asterisk. As seen, there is exactly one good cyclic shift in each row, and there are exactly five in each column.

from itertools import combinations


def table(n):
    for open_brace_indices in combinations(range(2 * n + 1), n):
        perm = ['(' for _ in range(2 * n + 1)]
        for position in open_brace_indices:
            perm[position] = ')'

        for start_index in range(len(perm)):
            cyclic_shift = perm[start_index:] + perm[:start_index]
            print("".join(cyclic_shift), end="")
            if all(cyclic_shift[:i].count("(") >
                   cyclic_shift[:i].count(")")
                   for i in range(1, len(perm))
                   ):
                print('* ', end='')
            else:
                print('  ', end='')
        print('')


table(3)

)))((((  ))(((()  )(((())  (((()))* ((()))(  (()))((  ()))(((  
))()(((  )()((()  ()((())  )((())(  ((())()* (())()(  ())()((  
))(()((  )(()(()  (()(())* ()(())(  )(())((  (())(()  ())(()(  
))((()(  )((()()  ((()())* (()())(  ()())((  )())(((  ())((()  
))(((()  )(((())  (((()))* ((()))(  (()))((  ()))(((  )))((((  
)())(((  ())((()  ))((()(  )((()()  ((()())* (()())(  ()())((  
)()()((  ()()(()  )()(()(  ()(()()  )(()()(  (()()()* ()()()(  
)()(()(  ()(()()  )(()()(  (()()()* ()()()(  )()()((  ()()(()  
)()((()  ()((())  )((())(  ((())()* (())()(  ())()((  ))()(((  
)(())((  (())(()  ())(()(  ))(()((  )(()(()  (()(())* ()(())(  
)(()()(  (()()()* ()()()(  )()()((  ()()(()  )()(()(  ()(()()  
)(()(()  (()(())* ()(())(  )(())((  (())(()  ())(()(  ))(()((  
)((())(  ((())()* (())()(  ())()((  ))()(((  )()((()  ()((())  
)((()()  ((()())* (()())(  ()())((  )())(((  ())((()  ))((()(  
)(((())  (((()))* ((()))(  (()))((  ()))(((  )))((((  ))(((()  
()))(((  )))((((  ))(((()  )(((())  (((()))* ((()))(  (()))((  
())()((  ))()(((  )()((()  ()((())  )((())(  ((())()* (())()(  
())(()(  ))(()((  )(()(()  (()(())* ()(())(  )(())((  (())(()  
())((()  ))((()(  )((()()  ((()())* (()())(  ()())((  )())(((  
()())((  )())(((  ())((()  ))((()(  )((()()  ((()())* (()())(  
()()()(  )()()((  ()()(()  )()(()(  ()(()()  )(()()(  (()()()* 
()()(()  )()(()(  ()(()()  )(()()(  (()()()* ()()()(  )()()((  
()(())(  )(())((  (())(()  ())(()(  ))(()((  )(()(()  (()(())* 
()(()()  )(()()(  (()()()* ()()()(  )()()((  ()()(()  )()(()(  
()((())  )((())(  ((())()* (())()(  ())()((  ))()(((  )()((()  
(()))((  ()))(((  )))((((  ))(((()  )(((())  (((()))* ((()))(  
(())()(  ())()((  ))()(((  )()((()  ()((())  )((())(  ((())()* 
(())(()  ())(()(  ))(()((  )(()(()  (()(())* ()(())(  )(())((  
(()())(  ()())((  )())(((  ())((()  ))((()(  )((()()  ((()())* 
(()()()* ()()()(  )()()((  ()()(()  )()(()(  ()(()()  )(()()(  
(()(())* ()(())(  )(())((  (())(()  ())(()(  ))(()((  )(()(()  
((()))(  (()))((  ()))(((  )))((((  ))(((()  )(((())  (((()))* 
((())()* (())()(  ())()((  ))()(((  )()((()  ()((())  )((())(  
((()())* (()())(  ()())((  )())(((  ())((()  ))((()(  )((()()  
(((()))* ((()))(  (()))((  ()))(((  )))((((  ))(((()  )(((())

Now, it remains to prove that each path of \(n+1\) up-steps and \(n\) down-steps has exactly one good cyclic shift. Consider such a path and focus on the rightmost among its lowest points.

This proven fact is an interpretation of the following result.

Theorem (Renyi, 1959). A sequence of integers whose sum of elements equals one has exactly one cyclic shift where the sum of all prefixes is positive.