给两个数列，求通项公式

KeyTo9_Fans

考虑$1$个长度为$n$，有以下$8$种符号的序列：

、 、 、 、 、 、 、 ，

其中，“”表示空格。

这个序列需要符合以下要求：

$1$、必须是合法的括号序列：左右括号必须能一一配对。配对时，左括号在前、右括号在后，左圆括号必须和右圆括号配对，左方括号必须和右方括号配对。

$2$、序列里要么有且只有$1$个并且没有，要么有且只有$1$个并且没有。

$3$、方括号不能放在任何一对圆括号里面。

$4$、不能出现以下子序列：
















问：长度为$n$的，符合要求的序列有多少个？

例如，长度为$5$的符合要求的序列有$33$个：


































给定$n$，答案就是$1$楼的第$1$个数列，该数列的递推式是$2$楼或$17$楼。

而我需要的是通项公式。

wayne

17# KeyTo9_Fans 刚才试了下把方程组做z变换，发现可以得到两组解，解的结构比我想象的要简洁。 可惜做逆z变换的时候，Mathematica罢工了。

2. b[0]=b[1]=b[2]=b[3]=c[0]=c[1]=c[2]=c[3]=1;
3. b[4]=c[4]=2;
4. d[0]=d[1]=d[2]=d[3]=0;
5. d[4]=1;
6. ZTransform[{
7. a[n]==Sum[b[i](c[n-i+3]-c[n-i+2]),{i,0,n-1}],
8. b[n+3]==1+Sum[b[i]d[n+3-i],{i,0,n-1}],
9. c[n+4]==c[n+3]+Sum[b[i]c[n+2-i],{i,0,n}],
10. d[n+1]==d[n]+c[n+1]
11. },n,z]

复制代码

附件是 a[z]的其中一个解， 如果能得到该式子的逆z变换的表达，此题就可以破了： $\frac{z^6}{2 (z-2)}-\frac{3 z^5}{z-2}+\frac{6 z^4}{z-2}-\frac{9 z^3}{2 (z-2)}-z^3+\frac{z^2}{z-2}+z^2-\frac{\sqrt{z^4-6 z^3+9 z^2-4} z^4}{2 (z-2)}+\frac{3 \sqrt{z^4-6 z^3+9 z^2-4} z^3}{2 (z-2)}-\frac{\sqrt{z^4-6 z^3+9 z^2-4} z^2}{2 (z-2)}$

wayne

用Mathematica自带的DifferenceRoot函数，可以得到b[n],c[n],d[n]的符号表达。 但a[n]不行。

1. b[n]=
2. UnitStep[2-n]-2^(n-2) (1-UnitStep[2-n]) DifferenceRoot[Function[{y,n},{(-2+n) y[n]+(2-n) y[1+n]+(-9-9 n) y[2+n]+(39+21 n) y[3+n]+(-46-16 n) y[4+n]+(16+4 n) y[5+n]==0,y[-3]==0,y[-2]==0,y[-1]==0,y[0]==0,y[1]==1}]][n]

复制代码

=====================

1. c[n]=
2. UnitStep[1-n]-1/2 (1-UnitStep[1-n]) DifferenceRoot[Function[{y,n},{(-8+4 n) y[n]+(8-4 n) y[1+n]+(-9-9 n) y[2+n]+(24+15 n) y[3+n]+(-19-7 n) y[4+n]+(4+n) y[5+n]==0,y[0]==0,y[1]==1,y[2]==-2,y[3]==-2,y[4]==-2}]][1+n]

复制代码

=====================

1. d[n]=
2. 1/2 UnitStep[n-4] (1+DifferenceRoot[Function[{y,n},{4 (-2+n) (2+n) (3+n) y[n]-4 (-2+n) (2+n) (3+n) y[1+n]-9 n (1+n) (3+n) y[2+n]+3 n (19+21 n+5 n^2) y[3+n]-n (2+n) (18+7 n) y[4+n]+n (2+n) (3+n) y[5+n]==0,y[1]==0,y[2]==-3,y[3]==-3,y[4]==-3,y[5]==-11}]][n-2]-DifferenceRoot[Function[{y,n},{(-8+4 n) y[n]+(8-4 n) y[1+n]+(-9-9 n) y[2+n]+(24+15 n) y[3+n]+(-19-7 n) y[4+n]+(4+n) y[5+n]==0,y[0]==0,y[1]==1,y[2]==-2,y[3]==-2,y[4]==-2}]][n-2]-(n-3) DifferenceRoot[Function[{y,n},{(-8+4 n) y[n]+(8-4 n) y[1+n]+(-9-9 n) y[2+n]+(24+15 n) y[3+n]+(-19-7 n) y[4+n]+(4+n) y[5+n]==0,y[0]==0,y[1]==1,y[2]==-2,y[3]==-2,y[4]==-2}]][n-2])

复制代码

足够细心的话，就可以从DifferenceRoot找到b,c,d各自的递归式子的，

wayne

囧，好像有问题

KeyTo9_Fans

是$17#$的递推式有问题，还是Mathematica的结果有问题呢？ 我百科了一下Z变换，还是不知道Z变换是什么，怎么用。 wayne大牛如果能说些易懂的话让小弟明白Z变换就再好不过了 ##### 运行$16#$的程序，确实输出了$1$楼的第$1$个数列。 $17#$的递推式是照着$16#$的程序写的，只是变量名变了。 ##### 解释得不错，是时候学习学习了

wayne

25# KeyTo9_Fans 我也不清楚，有时间再排查一下 =============== z变换只是一种积分变换(空间变换)工具，是拉普拉斯变换的一个离散域的版本。 如果一个问题在时域不好解决，我们通过z变换之类的空间变换工具，将它变换到另一个空间(比如这里的频域)，往往会有意想不到的启示(enlightenment，revelation) =========== 举一个例子： 假如wayne某天脑子突然间抽风了，已知地推公式a[n + 2] = 3 a[n + 1] - 2 a[n] ， 却不知道怎么求通项公式a[n]。但他竟然懂得这么做： 1)Z变换，即先将表达式变换到另一个空间里，俗称，将时域变换到频域。 2)逆Z变换，返回到原问题域 3)核查一下结果的正确性 关于Z变换和逆Z变换怎么算出结果的，原则上是根据定义算一下积分，但当我们知道了一些很常见的式子的正反变换，结合Z变换的基本性质， 或者会查Z变换表的话，是可以应对很多一般性的问题的，类似于曾经我们经常翻阅的积分表 ========== 好像已经足够了。 so，Fans 就拿本题实战一下吧

wayne

25# KeyTo9_Fans 用Z变换的好处就是可以套用卷积定理，(时域中的卷积对应于频域中的乘积)， 能将递推式子里的求和(刚好是卷积的形式) 简化成两个函数的乘积的形式。

wayne

17# KeyTo9_Fans 设$ P(n)=\sum _{i=0}^n b(i) d (n-i)$ 则，容易得知： $b(n)=1+P(n)$ $d(n+3)-2d(n+2)+d(n+1) =P(n+1)-P(n)$

chyanog

26# wayne 请教个问题，已知生成函数GeneratingFunction，如何得到通项公式呢？ 我知道Maple里可以用convert(1/(1-2*x),FPS,x);，Mathematica中还不清楚怎么用。

wayne

29# chyanog

1. SeriesCoefficient[1/(1-x-x^2),{x,0,n}]

复制代码