{VERSION 6 0 "IBM INTEL NT" "6.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal " -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 12 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Title " -1 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 } 3 1 0 0 12 12 1 0 1 0 2 2 19 1 }{PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 8 8 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 48 "A linear recurrence for t he numbers of Pi-Shapes" }}{PARA 19 "" 0 "" {TEXT -1 39 "Andy Lorenz, \+ Yann Ponty and Peter Clote" }}{PARA 0 "" 0 "" {TEXT -1 567 "A classica l result in the field of combinatorics states that the numbers of word s of size n issued from a context-free grammar satisfy a linear recurr ence involving a number of terms independant from n.\nThis result is e xtremely useful for the random generation of algebraic combinatorial s tructures, and a set of Maple procedures has been implemented in the M aple package GFun (B.Salvy, P. Zimmerman) to automatically compute the se recurrences. In addition to this invaluable tool, we use the biject ion proven earlier to exhibit a linear recurrence for the Pi-Shapes." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "restart:libname := \"c:/a lgolib\", libname; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(libnameG6$Q+ c:/algolib6\"Q>C:\\Program~Files\\Maple~10/libF'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "with(gfun):Res3 := algeqtodiffeq(S = z*S*z*S+ z*S+1,S(z),\{\});" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%Res3G,(\"\"#\" \"\"*&,(F&!\"\"*&\"\"$F'%\"zGF'F'*&F,F')F-F&F'F'F'-%\"SG6#F-F'F'*&,(F- F**&F&F'F/F'F'*&F,F')F-F,F'F'F'-%%diffG6$F0F-F'F'" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 36 "Res4 := diffeqtorec(Res3,S(z),m(n));" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%%Res4G<%,(*&,&\"\"$\"\"\"*&F)F*%\"nG F*F*F*-%\"mG6#F,F*F**&,&\"\"&F**&\"\"#F*F,F*F*F*-F.6#,&F*F*F,F*F*F**&, &\"\"%!\"\"F,F;F*-F.6#,&F,F*F4F*F*F*/-F.6#\"\"!F*/-F.6#F*F*" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "The claimed recurrence for the Mot zkin numbers is then:" }}{PARA 0 "" 0 "" {TEXT -1 5 " " }{XPPEDIT 18 0 "m(n) = ((3*n-3)*m(n-2)+(1+2*n)*m(n-1))/(n+2)m(0) = 1m(1) = 1;" " 6%/-%\"mG6#%\"nG*&,&*&,&*&\"\"$\"\"\"F'F.F.F-!\"\"F.-F%6#,&F'F.\"\"#F/ F.F.*&,&F.F.*&F3F.F'F.F.F.-F%6#,&F'F.F.F/F.F.F.,&F'F.F3F.F//-F%6#\"\"! F./-F%6#F.F." }}{PARA 0 "" 0 "" {TEXT -1 189 "From such recurrences it is possible to evaluate efficiently the numbers of motzkin words of a rbitrary size. For instance, the following calculus takes less than 1 \+ sec on a modern computer." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "MotzNumbers:=rectoproc(Res4,m(n),remember);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%,MotzNumbersGf*6#%\"nG6\"6#%)rememberGE\\s#\"\"!\"\" \"F-F-,$*&,(*&\"\"$F--9!6#,&9$F-\"\"#!\"\"F-F--F46#,&F7F-F-F9F9*&,&*&F 2F-F3F-F9*&F8F-F:F-F9F-F7F-F-F-,&F7F-F8F-F9F9F(F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "M10000:=MotzNumbers(10000);\n" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%'M10000G\"id]lFi.A$y2O?')Q@!4$zLDu#[!\\ryJ W?-M'*[1:ucE0m!\\jzV(\\xGUm#e#QLYQYKP$4la_!o:Qvt!))yI+[@:/#\\wZfN4]o7. wk[kWYP12-T^XoHfIa([\"3(3i`0?vBdys5F>**yvNXC!f3/Z:<-<)38JDs0lcyamAhMC* [j\"=R]I:,xV5KZ$Hw@Pavk%f8JYA1,23%\\<$3&[Q=q%p(y)[$*[\\G\"H$yE!o7Wp3OY V3(Rgic@H0&*41H?z$=l'f)[3qY6q*GJbXhQ61>/+HoM^&RSWsH6u=\\^7\"ecNstsOlZ. e+wy\\:4iej)=K`$zzNr[w#Hi!\\N,=;L#fMw#zNji;$Ry5(*H&>`W(*4!QmSl9)zk-(H! )*HB6x+3-\"Qu@U5?Lx6A5qh!p-p-2]nI\"H9)[**zjZbQO0LE'G-l%G--'*[2jXcvo@]zE0OMJaR%fwprJ *o-fTQCF*ejSc'p3%o8!\\T\\G7Ai)RQqI&G?pp$3N%H\\sNGJU+<\\_@Wyj,`=y\"Rv8] I)yxGXN)>m@([sp(>Qt'*)4A\"fo0sO!*[;$p\"3F,&R?xD77&)**\\[s@))*p$3['z6?Q uWR/wTV'4%\\P!3d()zsn$HfB/>tV'>f)4vZJl(=*=xkub*3gl/_&)R+qa!z1o1v2\"e\" QVTTQ%)\\ideZS'*e$zt!egx/6=*He\"G[lAW7;[U'ppU#Rtyo'\\7z& ftfWw`WZI`mik;Vo?=Gg[mg$[#oF\">*>dr(*4p)>eKE\"o[t.)4b?YAl[F!4y'ef?I!op 7YWB(yFFJ;;\\KX#31M)zxyd#f\"R.WyG\\F#G)\\BR+GT#GLWYIdkO$Q&oSUo!eZ!>-gp V*[\"ywkXC!*y?fs4\"eo/0.^3UK5k%G_O*zrDCON$p[%3hM:5bt1BAXU:t]^$\\n\"=up X^!Qw%*o]7_%e!od!>`pi_)QU\"okL6RsKs.x0s7PMRdzZ?7Kj!\\Ojq!f6FCWu:P*[ID \"*p\"o@lzN;g:PT)Rb]7GB%QwQ*G`WXJ-#3'e)y>['z(\\z'eJ,2]`U7uBv[OGA5votHfd/@vNOD*R(o7dOrS_;[l5;k,Z`f>/K89SrJIBE2@\"G\" pR!z$*HXw%4&Q_t%)4^iE!o+DLGo!zO!=+#)H+Efvw8rQ+xRIw'\\B6wd*>6fBhN(4qJN, .l3`U82X=(4sbrPp$f#RHAz'*ye[4`s'3%3@jk_(G#3Tix2#\\djE<4,vT``!*3'*)*f%= =R.8$zF'\\e^9]g*>E\\$QIZigSH#)yyD\\%HJJ+#R:j3,MVa%\\-&3.'=AjI\"RR>4< `a,Q#[+r(48W#zd:q9g:Jqajm*H'4ZW%HS?@x_t.0 \\[)z9NyhBBXJC]1CJgD*o:=G&\\kE3*[p^8T**Q2R/r\\;K9mXCF\\o3`ixKXu&yo0#y^ yeHrW[/Eh)eGV>)ela?e;=D&GW*R\\$)\\-i31))*4xUm,Y*>R7!Q*e?bF=%4x#)*=jKh! ej)=2+5(>`.w$y,#Hl%)REzQdGYQ'HA=)[_H-baH'\\.TO?!3-S@-D)H$e1;\\p([\\! fm[l7NxqW)H/3`P)*H#**G)ek'egL?!)f^\"oQ_$[&3mp?Z'Q#*H!orGlM2f\"\\Yv+\\6 jcoCCqjcTC&4\"o(*RntC8l@oYF2wID734C`T`_Uf>,$o3VmR*3!)pYu!*oKzI`)f,B_#R 0Buq*z#)zfPALWRps7TP&R#eYx?l>d`Vn/.ecNXc1$>]s7p2dz3n!=ArIY8<*>=<-w>br& >A)3MhY_8d?+dUD?,SXsj&)fjFRfj(3hi,zK$pj8O#zQ&*pc,3#fEg%>DBGB*=9Q Nf5BT?UTJ(R9kh(pVe;;zoy`l)4**[f`Tkm!yLz%fOn+j]O9>/15yv(=uz/s[E9\")QN&3 hqz2V*3Hm$R]y\"p<>o_-&\\.b*GnVW5K&HIv=P)ptPI_sb,T8?LwFOP^-E28/J6FkZ]Xl /#)**ykQiL\"H3s$R\"e)3ASfW\"pA8Bd@H*z+1V`Em!R#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 99 "As it has been proven that m(n) = s(2n+2), we can tr anspose the previous recurrence and state that:" }}{PARA 0 "" 0 "" {TEXT -1 31 " " }{XPPEDIT 18 0 "s(n) = ( 3*(n-4)*s(n-4)+(2*n-2)*s(n-2))/(n+2)s(1) = 0s(2) = 1s(3) = 0s(0) = 1; " "6'/-%\"sG6#%\"nG*&,&*(\"\"$\"\"\",&F'F,\"\"%!\"\"F,-F%6#F-F,F,*&,&* &\"\"#F,F'F,F,F5F/F,-F%6#,&F'F,F5F/F,F,F,,&F'F,F5F,F//-F%6#F,\"\"!/-F% 6#F5F,/-F%6#F+F=/-F%6#F=F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 85 "Res5 := \{s(0)=1, s(1)=0, s(2)=1, s(3)=0, s(n)=(3*(n-4)*s(n-4)+(2* n-2)*s(n-2))/(2+n)\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%Res5G<'/-% \"sG6#%\"nG*&,&*(\"\"$\"\"\",&F*F/\"\"%!\"\"F/-F(6#F0F/F/*&,&*&\"\"#F/ F*F/F/F8F2F/-F(6#,&F*F/F8F2F/F/F/,&F*F/F8F/F2/-F(6#F/\"\"!/-F(6#F8F//- F(6#F.F@/-F(6#F@F/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "PiSha pesNumbers:=rectoproc(Res5,s(n),remember);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%0PiShapesNumbersGf*6#%\"nG6\"6#%)rememberGE\\s%\"\"! \"\"\"F-F,\"\"#F-\"\"$F,,$*&,(*&\"#7F--9!6#,&9$F-\"\"%!\"\"F-F-*&F.F-- F66#,&F9F-F.F;F-F-*&,&*&F/F-F5F-F;*&F.F-F=F-F;F-F9F-F-F-,&F9F-F.F-F;F; F(F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "S20002:= PiShapes Numbers(20002);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%'S20002G\"id]lFi. A$y2O?')Q@!4$zLDu#[!\\ryJW?-M'*[1:ucE0m!\\jzV(\\xGUm#e#QLYQYKP$4la_!o: Qvt!))yI+[@:/#\\wZfN4]o7.wk[kWYP12-T^XoHfIa([\"3(3i`0?vBdys5F>**yvNXC! f3/Z:<-<)38JDs0lcyamAhMC*[j\"=R]I:,xV5KZ$Hw@Pavk%f8JYA1,23%\\<$3&[Q=q% p(y)[$*[\\G\"H$yE!o7Wp3OYV3(Rgic@H0&*41H?z$=l'f)[3qY6q*GJbXhQ61>/+HoM^ &RSWsH6u=\\^7\"ecNstsOlZ.e+wy\\:4iej)=K`$zzNr[w#Hi!\\N,=;L#fMw#zNji;$R y5(*H&>`W(*4!QmSl9)zk-(H!)*HB6x+3-\"Qu@U5?Lx6A5qh!p-p-2]nI\"H9)[**zjZbQO0LE'G-l%G-- '*[2jXcvo@]zE0OMJaR%fwprJ*o-fTQCF*ejSc'p3%o8!\\T\\G7Ai)RQqI&G?pp$3N%H \\sNGJU+<\\_@Wyj,`=y\"Rv8]I)yxGXN)>m@([sp(>Qt'*)4A\"fo0sO!*[;$p\"3F,&R ?xD77&)**\\[s@))*p$3['z6?QuWR/wTV'4%\\P!3d()zsn$HfB/>tV'>f)4vZJl(=*=xk ub*3gl/_&)R+qa!z1o1v2\"e\"QVTTQ%)\\ideZS'*e$zt!egx/6=*He \"G[lAW7;[U'ppU#Rtyo'\\7z&ftfWw`WZI`mik;Vo?=Gg[mg$[#oF\">*>dr(*4p)>eKE \"o[t.)4b?YAl[F!4y'ef?I!op7YWB(yFFJ;;\\KX#31M)zxyd#f\"R.WyG\\F#G)\\BR+ GT#GLWYIdkO$Q&oSUo!eZ!>-gpV*[\"ywkXC!*y?fs4\"eo/0.^3UK5k%G_O*zrDCON$p[ %3hM:5bt1BAXU:t]^$\\n\"=upX^!Qw%*o]7_%e!od!>`pi_)QU\"okL6RsKs.x0s7PMRd zZ?7Kj!\\Ojq!f6FCWu:P*[ID\"*p\"o@lzN;g:PT)Rb]7GB%QwQ*G`WXJ-#3'e)y>['z( \\z'eJ,2]`U7uBv[OGA5votHfd/@vNOD*R(o7dOrS_;[l5 ;k,Z`f>/K89SrJIBE2@\"G\"pR!z$*HXw%4&Q_t%)4^iE!o+DLGo!zO!=+#)H+Efvw8rQ+ xRIw'\\B6wd*>6fBhN(4qJN,.l3`U82X=(4sbrPp$f#RHAz'*ye[4`s'3%3@jk_(G#3Tix 2#\\djE<4,vT``!*3'*)*f%==R.8$zF'\\e^9]g*>E \\$QIZigSH#)yy D\\%HJJ+#R:j 3,MVa%\\-&3.'=AjI\"RR>4<`a,Q#[+r(48W#zd:q9g:Jqajm*H'4ZW%HS?@x_t.0\\[)z9NyhBBXJC]1CJgD*o:=G&\\kE3*[p^8T**Q2R/r\\; K9mXCF\\o3`ixKXu&yo0#y^yeHrW[/Eh)eGV>)ela?e;=D&GW*R\\$)\\-i31))*4xUm,Y *>R7!Q*e?bF=%4x#)*=jKh!ej)=2+5(>`.w$y,#Hl%)REzQdGYQ'HA=)[_H-baH'\\.T O?!3-S@-D)H$e1;\\p([\\!fm[l7NxqW)H/3`P)*H#**G)ek'egL?!)f^\"oQ_$[&3mp?Z 'Q#*H!orGlM2f\"\\Yv+\\6jcoCCqjcTC&4\"o(*RntC8l@oYF2wID734C`T`_Uf>,$o3V mR*3!)pYu!*oKzI`)f,B_#R0Buq*z#)zfPALWRps7TP&R#eYx?l>d`Vn/.ecNXc1$>]s7p 2dz3n!=ArIY8<*>=<-w>br&>A)3MhY_8d?+dUD?,SXsj&)fjFRfj(3hi,zK$pj8O#zQ&*p c,3#fEg%>DBGB*=9QNf5BT?UTJ(R9kh(pVe;;zoy`l)4**[f`Tkm!yLz%fOn+j]O 9>/15yv(=uz/s[E9\")QN&3hqz2V*3Hm$R]y\"p<>o_-&\\.b*GnVW5K&HIv=P)ptPI_sb ,T8?LwFOP^-E28/J6FkZ]Xl/#)**ykQiL\"H3s$R\"e)3ASfW\"pA8Bd@H*z+1V`Em!R# " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 2 "A " }{TEXT 256 10 "validation " }{TEXT -1 252 " of the recurrence may be obtained by comparing the n umbers of Motzkin words of size 10000 to that of pi-shapes having size 20002, both computed using the recurrences. Because of the one-to-one correspondence, these two numbers should be equal. Indeed:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "M10000-S20002;" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "11 0 2" 22 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 } {PAGENUMBERS 0 1 2 33 1 1 }