UyHiP November 2013 riddle: Parenthesis Values

Lwins_G

UyHiP (http://www.brand.site.co.il/riddles/) 这个月的谜题似乎和组合数学有一些关系。

题目如下：
考虑$n$对括号的任一种合法嵌套序列，((())()) 就是一个$n=4$时的例子。
在这个序列中，每一对括号都有自己的嵌套层数（若某对括号被恰好$k-1$个括号对完全包含，则它的嵌套层数为$k$）。对于任一个序列，我们定义序列的$V$值为序列中$n$对括号的嵌套层数的乘积，在上面的例子中$V=3 \cdot 2 \cdot 2 \cdot 1 = 12$。
令$f(n)$代表所有可能的包含恰好$n$对括号的序列的$V$值的总和。

任务：求出$f(n)$的闭式表达，并证明。

wayne

貌似跟整数划分有莫大关系

wayne

是这个结果吗？
http://oeis.org/A077365

{1,1}
{2,3}
{3,9}
{4,37}
{5,169}
{6,981}
{7,6429}
{8,49669}
{9,430861}
.....

wayne

恩，我手工算了:
1,1
2,3
3,11,
4,55
5,299

2的划分：{{2}, {1, 1}}
3的划分：{{3}, {2, 1}, {1, 1, 1}}
4的划分：{{4}, {3, 1}, {2, 2}, {2, 1, 1}, {1, 1, 1, 1}}

计算n=4：
{4}：        4!
{3, 1}        C(2,1)*(3!+2*2)
{2, 2}       2!*2!
{2, 1, 1}  C(3,1)*2!
{1, 1, 1, 1}  1
加起来 就是 55

Lwins_G

n=4的情况：
()()()()    V=1
(())()()  ()(())()  ()()(())    V=2  ∑V=6
((()))()  ()((()))    V=6  ∑V=12
(()())()  ()(()())    V=4  ∑V=8
(())(())    V=4
(()()())    V=8
((())())  (()(()))    V=12  ∑V=24
(((())))    V=24
((()()))    V=18

f(4)=1+6+12+8+4+8+24+24+18=105

Lwins_G

写了一个$O(n^2)$的程序来验证$n=100$以内的情况，发现都符合一个简单的公式。不过说出来就没意思了，既然是谜题，还是要充分享受自己探究的乐趣。

mathe

可以按最右边连续右括号数目分类，k个括号情况的和为S(n,k),于是S(n)=S(n,1)+S(n,2)+...+S(n,n)
另外对于n对括号，最右边k个连续右括号的情况，去掉这k个连续右括号最左边的一个和对应的左括号可以得出一个n-1对最右边连续k-1个括号的情况(k=1除外)
反之，对于n对括号，最右边k各连续右括号的情况，这k个连续右括号每个左边添加一对括号，分别可以得出n+1对，最右边连续k+1,k,...,2个右括号的情况。另外在最右边添加一个可以得出n+1对最右边一个右括号的情况。由此得出
$S(n+1,k)=k \sum_{t=k-1}^nS(n,t)$

wayne

我联想到了 树和森林,不过也只是算到了n=5.于是,索性搜了下OEIS,找到了一个匹配项:
(2n-1)!! = 1*3*5*...*(2n-1)  
http://oeis.org/A001147,1, 1, 3, 15, 105, 945, 10395, 135135,
与此相关的一个数列是 1, 1, 2, 10, 74, 706, 8162, 110410,...., 外层仅有一个括号,换言之,只有一个树的情况
http://oeis.org/A000698
a_0 = 1; for n>0, $a_n = (2n-1)!! - \sum_{k=1}^{n-1} (2k-1)!! a_{n-k}$.