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;

libname :=

>    with(gfun):Res3 := algeqtodiffeq(S = z*S*z*S+z*S+1,S(z),{});

Res3 := 2+(-2+3*z+3*z^2)*S(z)+(-z+2*z^2+3*z^3)*diff(S(z),z)

>    Res4 := diffeqtorec(Res3,S(z),m(n));

Res4 := {(3+3*n)*m(n)+(5+2*n)*m(1+n)+(-4-n)*m(n+2), m(0) = 1, m(1) = 1}

The claimed recurrence for the Motzkin numbers is then:

      m(n) = ((3*n-3)*m(n-2)+(1+2*n)*m(n-1))/(n+2), m(0) = 1, m(1) = 1

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);

MotzNumbers := proc (n) option remember; -(3*procname(n-2)-procname(n-1)+(-3*procname(n-2)-2*procname(n-1))*n)/(n+2) end proc; MotzNumbers(0) := 1; MotzNumbers(1) := 1
MotzNumbers := proc (n) option remember; -(3*procname(n-2)-procname(n-1)+(-3*procname(n-2)-2*procname(n-1))*n)/(n+2) end proc; MotzNumbers(0) := 1; MotzNumbers(1) := 1
MotzNumbers := proc (n) option remember; -(3*procname(n-2)-procname(n-1)+(-3*procname(n-2)-2*procname(n-1))*n)/(n+2) end proc; MotzNumbers(0) := 1; MotzNumbers(1) := 1
MotzNumbers := proc (n) option remember; -(3*procname(n-2)-procname(n-1)+(-3*procname(n-2)-2*procname(n-1))*n)/(n+2) end proc; MotzNumbers(0) := 1; MotzNumbers(1) := 1

>    M10000:=MotzNumbers(10000);

M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
M10000 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...

As it has been proven that m(n) = s(2n+2), we can transpose the previous recurrence and state that:

                                s(n) = (3*(n-4)*s(n-4)+(2*n-2)*s(n-2))/(n+2), s(1) = 0, s(2) = 1, s(3) = 0, s(0) = 1

>    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)};

Res5 := {s(n) = (3*(n-4)*s(n-4)+(2*n-2)*s(n-2))/(n+2), s(1) = 0, s(2) = 1, s(3) = 0, s(0) = 1}

>    PiShapesNumbers:=rectoproc(Res5,s(n),remember);

PiShapesNumbers := proc (n) option remember; -(12*procname(n-4)+2*procname(n-2)+(-3*procname(n-4)-2*procname(n-2))*n)/(n+2) end proc; PiShapesNumbers(0) := 1; PiShapesNumbers(1) := 0; PiShapesNumbers(2...
PiShapesNumbers := proc (n) option remember; -(12*procname(n-4)+2*procname(n-2)+(-3*procname(n-4)-2*procname(n-2))*n)/(n+2) end proc; PiShapesNumbers(0) := 1; PiShapesNumbers(1) := 0; PiShapesNumbers(2...
PiShapesNumbers := proc (n) option remember; -(12*procname(n-4)+2*procname(n-2)+(-3*procname(n-4)-2*procname(n-2))*n)/(n+2) end proc; PiShapesNumbers(0) := 1; PiShapesNumbers(1) := 0; PiShapesNumbers(2...
PiShapesNumbers := proc (n) option remember; -(12*procname(n-4)+2*procname(n-2)+(-3*procname(n-4)-2*procname(n-2))*n)/(n+2) end proc; PiShapesNumbers(0) := 1; PiShapesNumbers(1) := 0; PiShapesNumbers(2...

>    S20002:= PiShapesNumbers(20002);

S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...
S20002 := 23906626534306007992921572313226914459402208858139372082913362386478998204654550476427113104130726025137362776332013410155725230377369837187530295321044436728955034950252681917691785039366290...

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;

0

>