A linear recurrence for the numbers of Pi-Shapes
Andy Lorenz, Yann Ponty and Peter Clote
A classical result in the field of combinatorics states that the numbers of words of size n issued from a context-free grammar satisfy a linear recurrence involving a number of terms independant from n.
This result is extremely useful for the random generation of algebraic combinatorial structures, and a set of Maple procedures has been implemented in the Maple package GFun (B.Salvy, P. Zimmerman) to automatically compute these recurrences. In addition to this invaluable tool, we use the bijection proven earlier to exhibit a linear recurrence for the Pi-Shapes.
> | restart:libname := "c:/algolib", libname; |
> | with(gfun):Res3 := algeqtodiffeq(S = z*S*z*S+z*S+1,S(z),{}); |
> | Res4 := diffeqtorec(Res3,S(z),m(n)); |
The claimed recurrence for the Motzkin numbers is then:
From such recurrences it is possible to evaluate efficiently the numbers of motzkin words of arbitrary size. For instance, the following calculus takes less than 1 sec on a modern computer.
> | MotzNumbers:=rectoproc(Res4,m(n),remember); |
> | M10000:=MotzNumbers(10000); |
As it has been proven that m(n) = s(2n+2), we can transpose the previous recurrence and state that:
> | 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)}; |
> | PiShapesNumbers:=rectoproc(Res5,s(n),remember); |
> | S20002:= PiShapesNumbers(20002); |
A validation of the recurrence may be obtained by comparing the numbers 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:
> | M10000-S20002; |
> |