Average number of Dyck words in a Dyck word Given a integer $n$, how many Dyck words are a substring of a Dyck word of size $n$, on average?
For example, if $n=2$, then Dyck words of size $2$ are : 


*

*[ ] [ ]  

*[ [ ] ]


(1) contains two strict "sub-Dyck words" : [ ] (with the first two parentheses) and [ ] (with the last two parentheses). And the original [ ] [ ]. The total is 3
(2) contains only one strict "sub-Dyck word": [ ]. And the original [ [ ] ]. The total is 2
So for $n=2$ the answer is 2.5, of course it is harder to compute when $n$ gets bigger.
Has anyone an idea on how to find a general formula for this problem?

Every Dyck word can be written uniquely as $(w_1)w_2$, where $w_1$,$ w_2$ are (possibly empty) Dyck words. This should allow you to find a recursive solution to your problem. Every Dyck subword will either be a subword of $w_1$, a subword of $w_2$, ($w_1$), or ($w_1$) followed by a nonempty initial subword of $w_2$. So you need to find subwords, and initial subwords starting at the beginning.
So if we call the function counting the number of subwords $f(w)$ and the number of possibly empty initial subwords g(w), then if $w = (w_1)w_2$ we have $f(w) = f(w_1) + f(w_2) + g(w_2) + 1$. Similarly, we have the recursion $g(w) = 1 + g(w_2)$ as every initial subword of $(w_1)w_2$ is empty, or $(w_1)$ followed by a possibly empty initial word of $w_2$.
This gives you a recursion rule that is usable to get a similar recursion rule to that for the Catalan numbers C(n). First define G(n) as the sum of g(w) over all Dyck words of length 2n. Recursing on the length of $w_2$, this gives us a recursion rule for G:
$G(n) = \sum_{j = 0}^{n-1} C(i)(C(j) + G(j)) = C(n) + \sum_{j = 0}^{n-1} C(i)G(j) $, with G(1) = 2. However, if you look closely, plugging in $G(n) = C(n+1)$ solves the equation, so this is still just the Catalan numbers.
Similarly, we can define F(n) as the sum of f(w) over all Dyck words of length 2n. This has a similar recursion rule:
$F(n) = \sum_{i + j + 1 = n} F(i)C(j) + C(i)F(j) + C(i)G(j) + C(i)C(j) = C(n+1) + \sum_{i + j + 1 = n} F(i)C(j) + C(i)F(j) $
C and F can then be computed efficiently in quadratic time and linear space as a function of n from the above recursion rules with basic memoization techniques, and dividing by the nth Catalan number gives you the correct average. You can also try deriving a closed form formula for F if you would like, though it will take slightly more work.
