不允许出现连续相同符号的括号序列

KeyTo9_Fans

以 “（” 和 “）” 这两种符号构成的、长度为 2n 的合法的括号序列，

我们已经知道是有  卡特兰(n) 种，其中

卡特兰(n) = (2n)!/(n!)^2/(n+1)

我现在想把这个问题扩展一下，要求括号序列里不得出现连续k个 “（”、也不得出现连续k个 “）”，

给定 n 和 k，问长度为 2n 的、不出现 k 个连续相同符号的括号序列有多少种？

这是一个二维数列，OEIS称之为“Table”，

我们求出来之后，看看OEIS收录了这个“Table”没有，

如果有，我们向他学习，了解更多相关知识；

如果没有，我们把这个新的“Table”贡献给他。

northwolves

(1, 1, [0])
(2, 2, [0, 1])
(3, 5, [0, 1, 4])
(4, 14, [0, 1, 8, 13])
(5, 42, [0, 1, 17, 34, 41])
(6, 132, [0, 1, 37, 93, 122, 131])
(7, 429, [0, 1, 82, 262, 374, 417, 428])
(8, 1430, [0, 1, 185, 753, 1173, 1357, 1416, 1429])
(9, 4862, [0, 1, 423, 2198, 3745, 4495, 4769, 4846, 4861])
(10, 16796, [0, 1, 978, 6502, 12126, 15107, 16297, 16681, 16778, 16795])
(11, 58786, [0, 1, 2283, 19449, 39718, 51386, 56369, 58131, 58647, 58766, 58785])
(12, 208012, [0, 1, 5373, 58724, 131372, 176558, 196972, 204685, 207175, 207847, 207990, 208011])

mathe

我们假设长度为2n连续同向括号数目小于k的序列数目为f(k-1,n)
于是我们知道对于k>n+1,必然有f(k,n)=f(k-1,n), 而且f(1,n)=1 (只能左右括号交替),而且记f(k,0)=1.
我们分析f(k,n)的情况,也就是2n个符号，连续括号数目不超过k+1的计数情况
第一个位置必然在左括号，我们分析和这个位置匹配的右括号位置必然在某个偶数位置，如果这个位置为2s
那么1~2s之间我们去掉第一个位置的左括号和第2s位置的右括号，得到一个长度为2(s-1),所有连续括号数目小于k的序列，所以数目为f(k-1,s-1), 而余下2n-2s个数匹配方案数目为f(k,n-s).
于是我们得到递归公式$f(k,n)=\sum_{s=1}^n f(k-1,s-1)f(k,n-s)$。 这个算法复杂度$O(n^3)$很容易计算到n较大的情况
计算得到
? getn(2)
%3 = [1, 2]
? getn(3)
%4 = [1, 4, 5]
? getn(4)
%5 = [1, 8, 13, 14]
? getn(5)
%6 = [1, 16, 34, 41, 42]
? getn(6)
%7 = [1, 32, 89, 122, 131, 132]
? getn(7)
%8 = [1, 64, 233, 365, 417, 428, 429]
? getn(8)
%9 = [1, 128, 610, 1094, 1341, 1416, 1429, 1430]
? getn(9)
%10 = [1, 256, 1597, 3281, 4334, 4744, 4846, 4861, 4862]
? getn(10)
%11 = [1, 512, 4181, 9842, 14041, 16016, 16645, 16778, 16795, 16796]
? getn(11)
%12 = [1, 1024, 10946, 29525, 45542, 54320, 57686, 58598, 58766, 58785, 58786]
? getn(12)
%13 = [1, 2048, 28657, 88574, 147798, 184736, 201158, 206516, 207783, 207990, 208011, 208012]
? getn(13)
%14 = [1, 4096, 75025, 265721, 479779, 629280, 704420, 732825, 740924, 742626, 742876, 742899, 742900]
? getn(14)
%15 = [1, 8192, 196418, 797162, 1557649, 2145600, 2473785, 2613834, 2660139, 2671892, 2674117, 2674414, 2674439, 2674440]
对应第三列 A001519 , 第四列 A007051， 第五列 A080937等
northwolves n=5 k=3时为17，我的16应该是他包含了有括号连续k个情况如(()(()()))

northwolves

n=3, 5, ['((()))', '(()())', '(())()', '()(())', '()()()']
k=1, 0, []]
k=2, 1, ['()()()']
k=3, 4, ['(()())', '(())()', '()(())', '()()()']

n=4, 14, ['(((())))', '((()()))', '((())())', '((()))()', '(()(()))', '(()()())', '(()())()', '(())(())', '(())()()', '()((()))', '()(()())', '()(())()', '()()(())', '()()()()']
k=1, 0, []]
k=2, 1, ['()()()()']
k=3, 8, ['(()()())', '(()())()', '(())(())', '(())()()', '()(()())', '()(())()', '()()(())', '()()()()']
k=4, 13, ['((()()))', '((())())', '((()))()', '(()(()))', '(()()())', '(()())()', '(())(())', '(())()()', '()((()))', '()(()())', '()(())()', '()()(())', '()()()()']

n=5, 42, ['((((()))))', '(((()())))', '(((())()))', '(((()))())', '(((())))()', '((()(())))', '((()()()))', '((()())())', '((()()))()', '((())(()))', '((())()())', '((())())()', '((()))(())', '((()))()()', '(()((())))', '(()(()()))', '(()(())())', '(()(()))()', '(()()(()))', '(()()()())', '(()()())()', '(()())(())', '(()())()()', '(())((()))', '(())(()())', '(())(())()', '(())()(())', '(())()()()', '()(((())))', '()((()()))', '()((())())', '()((()))()', '()(()(()))', '()(()()())', '()(()())()', '()(())(())', '()(())()()', '()()((()))', '()()(()())', '()()(())()', '()()()(())', '()()()()()']
k=1, 0, []]
k=2, 1, ['()()()()()']
k=3, 17, ['(()(())())', '(()()()())', '(()()())()', '(()())(())', '(()())()()', '(())(()())', '(())(())()', '(())()(())', '(())()()()', '()(()()())', '()(()())()', '()(())(())', '()(())()()', '()()(()())', '()()(())()', '()()()(())', '()()()()()']
k=4, 34, ['((()()()))', '((()())())', '((()()))()', '((())(()))', '((())()())', '((())())()', '((()))(())', '((()))()()', '(()(()()))', '(()(())())', '(()(()))()', '(()()(()))', '(()()()())', '(()()())()', '(()())(())', '(()())()()', '(())((()))', '(())(()())', '(())(())()', '(())()(())', '(())()()()', '()((()()))', '()((())())', '()((()))()', '()(()(()))', '()(()()())', '()(()())()', '()(())(())', '()(())()()', '()()((()))', '()()(()())', '()()(())()', '()()()(())', '()()()()()']
k=5, 41, ['(((()())))', '(((())()))', '(((()))())', '(((())))()', '((()(())))', '((()()()))', '((()())())', '((()()))()', '((())(()))', '((())()())', '((())())()', '((()))(())', '((()))()()', '(()((())))', '(()(()()))', '(()(())())', '(()(()))()', '(()()(()))', '(()()()())', '(()()())()', '(()())(())', '(()())()()', '(())((()))', '(())(()())', '(())(())()', '(())()(())', '(())()()()', '()(((())))', '()((()()))', '()((())())', '()((()))()', '()(()(()))', '()(()()())', '()(()())()', '()(())(())', '()(())()()', '()()((()))', '()()(()())', '()()(())()', '()()()(())', '()()()()()']

northwolves

1. def kuohao(n,l,r,s,t):
   
2.     if(l == n and r == n):
   
3.         t.append(s)
   
4.         return
   
5.     if(l < n):
   
6.         kuohao(n, l+1, r, s+"(", t)
   
7.     if(r < l):
   
8.         kuohao(n, l, r + 1, s+")", t)
   
9. # def diag(n):
   
10. #     x,y=[],[]
    
11. #     kuohao(n, 0, 0, "", x)
    
12. #     for k in range(1,n+1):
    
13. #         a,b=('('*k,')'*k)
    
14. #         t=[s for s in x if not ((a in s) or (b in s))]
    
15. #         y.append(len(t))
    
16. #     return(n,len(x),y)
    
17. 
    
18. def diag(n):
    
19.     x,y=[],[]
    
20.     kuohao(n, 0, 0, "", x)
    
21.     y.append(['n='+str(n),len(x),x])
    
22.     for k in range(1,n+1):
    
23.         a,b=('('*k,')'*k)
    
24.         t=[s for s in x if not ((a in s) or (b in s))]
    
25.         y.append(['k='+str(k),len(t),t])
    
26.     return(y)
    
27. 
    
28. for n in range(3,6):
    
29.     y=diag(n)
    
30.     for k in range(n+1):
    
31.         print(y[k])

复制代码

northwolves

字符串比较的穷举硬算，速度实在不怎么样

mathe

我弄错了，我这个计算的是嵌套深度小于k的数目，而不是连续符号不超过k的数目。
计算连续符号小于k的数目，我们也可以采用动态规划来做。
我们想像建立一个坐标轴，从原点出发，每遇到一个(, 那么向右上方移动一格（长度$\sqrt{2}$，每次遇到一个),那么向右下方移动一格。遍历2n个符号以后，必然到达坐标(2n,0). 而在这个遍历过程中，每次连续上升或连续下降的线段长度都小于$\sqrt{2}k$,而且移动过程永远不会跑到横坐标下方。
我们采用动态规划计算从原点出发，在某个上升线段终点到达点(x,y)的不同方案数目为A(k,x,y), 在某个下降线段终点到达点(x,y)的不同方案数目为B(k,x,y). 其中$0\le y\le x$.
于是B(k,0,0)=1, A(k,0,0)=0,而且y<0时$A(k,x,y)=B(k,x,y)=0$。当$y>x, A(k,x,y)=B(k,x,y)=0$
于是$A(k,x,y)=\sum_{h=1}^{k-1} B(k,x-h,y-h), B(k,x,y) = \sum_{h=1}^{k-1} A(k,x-h,y+h)$
于是$B(k,2n,0)$就是我们要求的结果。

1. #include <iostream>
   
2. #include <gmpxx.h>
   
3. 
   
4. #define MAXN 100
   
5. #define K 3
   
6. mpz_class A[2*MAXN+1][2*MAXN+1];
   
7. mpz_class B[2*MAXN+1][2*MAXN+1];
   
8. 
   
9. void init()
   
10. {
    
11.         B[0][0]=1;
    
12.         A[0][0]=0;
    
13. }
    
14. 
    
15. int main()
    
16. {
    
17.         int x,y,h;
    
18.         init();
    
19.         for(x=1;x<=2*MAXN;x++){
    
20.                 for(y=0;y<=x;y++){
    
21.                         mpz_class r=0;
    
22.                         for(h=1;h<K;h++){
    
23.                                 if(x-h>=0&&y-h>=0){
    
24.                                         r+=B[x-h][y-h];
    
25.                                 }
    
26.                         }
    
27.                         A[x][y]=r;
    
28.                         r=0;
    
29.                         for(h=1;h<K;h++){
    
30.                                 if(x-h>=0&&y+h<=x-h){
    
31.                                         r+=A[x-h][y+h];
    
32.                                 }
    
33.                         }
    
34.                         B[x][y]=r;
    
35.                 }
    
36.         }
    
37.         for(x=1;x<=MAXN;x++){
    
38.                 std::cout<<"count "<<x<<"="<<B[2*x][0]<<std::endl;
    
39.         }
    
40.         return 0;
    
41. 
    
42. }
    

复制代码

比如k=3对应的结果如下:
count 1=1
count 2=2
count 3=4
count 4=8
count 5=17
count 6=37
count 7=82
count 8=185
count 9=423
count 10=978
count 11=2283
count 12=5373
count 13=12735
count 14=30372
count 15=72832
count 16=175502
count 17=424748
count 18=1032004
count 19=2516347
count 20=6155441
count 21=15101701
count 22=37150472
count 23=91618049
count 24=226460893
count 25=560954047
count 26=1392251012
count 27=3461824644
count 28=8622571758
count 29=21511212261
count 30=53745962199
count 31=134474581374
count 32=336908488839
count 33=845139060165
count 34=2122553644686
count 35=5336735929371
count 36=13432403613621
count 37=33843022209066
count 38=85349327734485
count 39=215440028338359
count 40=544288586926914
count 41=1376230297675914
count 42=3482537223611046
count 43=8819175375714063
count 44=22349794473772659
count 45=56678600914995057
count 46=143830921235537742
count 47=365225623668676437
count 48=927972354829010775
count 49=2359192024476568203
count 50=6001174121892988758
count 51=15273713134056377698
count 52=38893747432145085266
count 53=99090832134641995427
count 54=252579381177903040849
count 55=644118340220292169786
count 56=1643348924746923013481
count 57=4194532932723720267271
count 58=10710773165730370402070
count 59=27361217667381195152609
count 60=69923263927774760117419
count 61=178761583832906815958299
count 62=457180542019634361749654
count 63=1169653910683020997823700
count 64=2993493968182857335738916
count 65=7663836950023084292126586
count 66=19627124209913879819201256
count 67=50281185027971273570344779
count 68=128851301008215990676245297
count 69=330295607482296149639113771
count 70=846922848867278127081934118
count 71=2172243398314031502060434813
count 72=5573055540747246795936497203
count 73=14301951559375317288722742625
count 74=36712267090479571354186761752
count 75=94262318866766131085885820862
count 76=242087967735412291153757221292
count 77=621890217530867044998372625244
count 78=1597927417599990976164331285618
count 79=4106772441264045401019924649921
count 80=10557037252659735639822884541089
count 81=27144318295978988020876731613899
count 82=69808615378820015816460193046634
count 83=179568484819409906464233459965565
count 84=461998012612770916903282585499931
count 85=1188877068859680412470053314034196
count 86=3059980617900905437254279674385261
count 87=7877408686568953921404087246339411
count 88=20282861001228149602530202549462410
count 89=52234134723235412099021791134645474
count 90=134541797507827311283829108795938674
count 91=346605946314513254492433135097630809
count 92=893077485129793636878895057273178901
count 93=2301521609537728551186835553085928773
count 94=5932151623905973421624468114595077244
count 95=15292526112023196667544094397358322057
count 96=39428894200253097844359818441341768857
count 97=101675651191856047918093722573856681533
count 98=262231577763896699071580185616362344474
count 99=676421455498354043694557131153096948242
count 100=1745070036795404191515676477125772132266
对应https://oeis.org/A004148

northwolves

k=4, https://oeis.org/A186236