UyHiP November 2013 riddle: Parenthesis Values
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)$的闭式表达，并证明。
貌似跟整数划分有莫大关系 是这个结果吗？
http://oeis.org/A077365
{1,1}
{2,3}
{3,9}
{4,37}
{5,169}
{6,981}
{7,6429}
{8,49669}
{9,430861}
..... 恩，我手工算了:
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 于 2013-11-5 17:37 编辑
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 写了一个$O(n^2)$的程序来验证$n=100$以内的情况，发现都符合一个简单的公式。不过说出来就没意思了，既然是谜题，还是要充分享受自己探究的乐趣。 可以按最右边连续右括号数目分类，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)$ 我联想到了 树和森林,不过也只是算到了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}.
页:
[1]