print(`qEWplus.txt: A maple package to study and compute explicit expressions for the sum of the powers of areas under Dyck and Motzkin type paths`): print(`originally Written By AJ Bu with some additions by Doron Zeilberger`): print(``): print(`It accompanies their paper`): print(``): print(`Explicit Generating Functions for the First 20 moments of the Area Under Dyck and Motzkin Paths`): print(``): print(`https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/qew.html`): print(``): print(`Version of April 22, 2024`): with(combinat): Help:=proc(): print(`Thes main procedures in this package are:`): print(`PowerDyck(n,k)`, `MomDyck(n,k)`, `LimMomDyck(k)`, `DyckStory(n,k) `): print( `PowerMotzkin(n,k,Mn,Mn1)`, `MomMotzkin(n,k,Mn,Mn1)`, `LimMomMotzkin(k)`, `MotzkinStory(n,k)` ): print(`Empir(L,x,P):`): print(` qnwK(S,K,q) qnwdK(S,K,q), FRarea(S,K,q,n,N,C)`): print(`SeqF1(P,Q,R,q,x,K)`, `DerK(P,Q,R,q,x,k)`, `PowerK(P,Q,R,q,x,k)`, `AlphaFE(P,Q,R,x,q,N1) `): print(`qnwdKTrunc(S,K,z,deg), OpeSeq(S,q,k,K2,n,N)`): print(`For details on each procedure try:`): print(`WhatIs(ProcedureName)`): print(`For the supporting procedures try`): print(`Help1()`): end: Help1:=proc(): print(`The secondary procedures are:`): print(`Tr(w)`, `Ar(w)`, `qnw(S,n,q)`): print(`qnwK(S,K,q)`, `qnmwd(S,n,m,q)`, `qnwd(S,n,q)`, `qnwdKi(S,K,q,i)`, `checkqnwd(S,K,q)`, `FRiarea(S,K,q,i,n,N,C)`): print(`Stat(F,t,K)`): print(`D1(f,q,x,K)`, `SeqD(q,x,K)`, `CheckD(q,x,K)`, `SeqMotz(q,x,K)`, `Motz(f,q,x,K)`, `CheckMotz(q,x,K)`): print(`F1(f,P,Q,R,q,x,K)`): print(`DyckDeriv(q,x,k)`, `CheckDyckDeriv(q,x,k,K)`): print(`MotzDeriv(q,x,k)`, `CheckMotzDeriv(q,x,k,K)`): print(`qnmwdTrunc(S,n,m,z,deg)`, `qnwdTrunc(S,n,z,deg)`): print(`GuessCatExp1(L,n,d)`, `GuessCatExp(L,n) `, ` Kk(k) `, `EBk(k) `, `EBkSeq(N) `): print(`GuessMotExp1(L,n,d)`, `GuessMotExp(L,n) `): print(` MotSeq(N) `): end: WhatIs:=proc(arg): if arg=PowerK then print(`PowerK(P,Q,R,q,x,k): inputs polynomials P,Q,R of the variables q,x and`): print(`outputs up (qd/dq)^i (f(x,q)) at q=1, for i=0 to i=k, which satisfies the equation`): print(`f(x,q)=P(x,q)+Q(x,q)*f(x,q)+R(x,q)*f(x,q)*f(q*x,q)`): print(`This gives the sum of the i-th powers of the areas under the Dyck or Motzkin paths in the applications below`): print(`For example for the first 6 terms w.r.t to q evaluated at q=1 for Dyck paths do`): print(`PowerK(1,0,q*x^2,q,x,5);`): print(`For example for the first 6 terms for Motzkin paths do`): elif arg=GuessMotExp1 then print(`GuessMotExp1(L,n,d,Mn): Given a list of numbers tries to match it with`): print(`M(n)*A1(n)+Mn(n+1)*A2(n)+B(n)*3^(n+1)+C(n)*(-1)^n) for polynomials A1(n),A2(n), B(n), and C(n) of degree d. Try:`): print(`M0:=MotSeq(60): L:=[seq(M0[i]*i+M0[i+1]*i^2+(i+2)*3^i+ (5*i+3)*(-1)^i,i=1..59)]: GuessMotExp1(L,n,2,Mn,Mn1);`): elif arg=GuessMotExp then print(`GuessMotExp(L,n,Mn): Given a list of numbers tries to match it with`): print(`M(n)*A1(n)+Mn(n+1)*A2(n)+B(n)*3^(n+1)+C(n)*(-1)^n) for polynomials A1(n),A2(n), B(n), and C(n) . Try:`): print(`M0:=MotSeq(60): L:=[seq(M0[i]*i+M0[i+1]*i^2+(i+2)*3^i+ (5*i+3)*(-1)^i,i=1..59)]: GuessMotExp(L,n,Mn,Mn1);`): elif arg=MotSeq then print(`MotSeq(N): The first N terms of the Motzkin sequence. try:`): print(`MotSeq(20);`): elif arg=PowerMotzkin then print(`PowerMotzkin(n,k,Mn,Mn1): the list of length k whose k-th term is the explicit expression in n for the sum of the k-th power of the areas under all Motzkin paths of length n. Try:`): print(`PowerMotzkin(n,10,Mn,Mn1);`): elif arg=MomMotzkin then print(`MomMotzkin(n,k,Mn,Mn1): the list of length k whose first entry is the exact expression in n for the average are under a Motzkin path from [0,0] to [n,0]`): print(`the second entry is the variance, and the third through the k-th are the moments about the mean. Try:`): print(`MomMotzkin(n,10,Mn,Mn1);`): elif arg=LimMomMotzkin then print(`LimMomMotzkin(k): the list of length k whose first entry is the limit of the average area under a Motzkin path of length n divided by n^(3/2)`): print(`the second entry is the limit of the variance divided by n^3, and the third through the k-th are the limits of the SCALED moments about the mean. `): print(`LimMomMotzkin(10);`): elif arg=MotzkinStory then print(`MotzkinStory(n,k): an article about explicit expressions for the sum of the powers of the area under Motzkin path of length n followed by the asymptotics and thoes of the`): print(`scaled moments. Try:`): print(`MotzkinStory(n,10);`): elif arg=Kk then print(`Kk(k): K_k given by Eq. (7) of Svante Janson's article (p.6)`): elif arg=EBk then print(`EBk(k): The k-th moment of the area under a Brownian motion. Try: `): print(`[seq(EBk(i),i=1..10)];`): elif arg=EBkSeq then print(`EBkSeq(N): the scaled moments about the mean of the area under Brownian Excursion. Try:`): print(`EBkSeq(10);`): elif arg=DyckStory then print(`DyckStory(n,k): an article about explicit expressions for the sum of the powers of the area under Dyck path of length 2n followed by the asymptotics and thoes of the`): print(`scaled moments. Try:`): print(`DyckStory(n,10);`): elif arg=LimMomDyck then print(`LimMomDyck(k): the list of length k whose first entry is the limit of the average area of a Dyck path of length 2n, divided by n^(3/2)`): print(`the second entry is the limit of the variance divided by n^3, and the third through the k-th are the limit of theSCALED moments about the mean. `): print(`LimMomDyck(10);`): elif arg=PowerDyck then print(`PowerDyck(n,k): the list of length k whose k-th term is the explicit expression in n for the sum of the k-th power of the areas under all Dyck paths of length 2*n. Try:`): print(`PowerDyck(n,10);`): print(`PowerKDyck(n,4);`): elif arg=MomDyck then print(`MomDyck(n,k): the list of length k whose first entry is the exact expression in n for the average are under a Dyck path from 0 to 2*n`): print(`the second entry is the variance, and the third through the k-th are the moments about the mean. Try:`): print(`MomDyck(n,10);`): elif arg=PowerDyck then print(`PowerDyck(n,k): the list of length k whose k-th term is the explicit expression in n for the sum of the k-th power of the areas under all Dyck paths of length 2*n. Try:`): print(`PowerDyck(n,10);`): print(`PowerKDyck(n,4);`): elif arg=AlphaFE then print(`AlphaFE(P,Q,R,q,x,K,N1): inputs polynomials P,Q,R of the variables q,x, a positive integer k and pos. integer N1, N2`): print(`Alpha(coeff(f(x,q),x,i),q,k); for i from N1 to N2. Try:`): print(`AlphaFE(1,x,q*x^2,q,x,6,20);`): elif arg=DerK then print(`DerK(P,Q,R,q,x,k): inputs polynomials P,Q,R of the variables q,x and`): print(`outputs up to the k-th derivative with resect to q of the function f(x,q), which satisfies the equation`): print(`f(x,q)=P(x,q)+Q(x,q)*f(x,q)+R(x,q)*f(x,q)*f(q*x,q)`): print(`evaluated at q=1`): print(`For example for the first 5 derivatives w.r.t to q evaluated at q=1 for Dyck paths do`): print(`DerK(1,0,q*x^2,q,x,5);`): print(`For example for the first 5 derivatives w.r.t to q evaluated at q=1 for Motzkin paths do`): print(`DerK(1,x,q*x^2,q,x,5);`): elif arg=Empir then print(`Empir(L,x,P): inputs a list L and tries to guess an algebraic equation for P=Sum(L[i+1]*x^i,i=0..nops(L)-1)`): print(`Try: `): print(`Empir([seq((2*i)!/i!/(i+1)!,i=0..30)],x,P);`): elif arg=SeqF1 then print(`SeqF1(P,Q,R,q,x,K): For the set of walks whose bivariate generating function f(x,q), where q^ix^n denotes a walk of length n with area i,`): print(`satisfies the equation`): print(`f(x,q)=P(x,q)+Q(x,q)*f(x,q)+R(x,q)*f(x,q)*f(q*x,q),`): print(`outputs the function enumerating the areas of walks of length 1 through K`): elif arg=qnwK then print(`qnwK(S,K,q): inputs a set of steps S, a positive integer K, and a variable q`): print(`outputs a list of length K, whose i-th entry is the enumerating function for the area of walks of length i with steps in S`): print(`WARNING: FOR CHECKING ONLY, does it by brute force`): print(`Try: qnwK([[1,1],[1,-1],[1,0]],5,q)`): elif arg=qnwdK then print(`qnwdK(S,K,q): inputs a set of steps S, a positive integer K, and a variable q`): print(`Uses Dynamical programming, much faster then qnwK `): print(`outputs a list of length K+1, whose i-th entry is the enumerating function for the area of walks of length i-1 with steps in S`): print(`For example, for the first 11 terms of the weight-enumerator of Dyck paths: type:`): print(`Try: qnwdK([[1,1],[1,-1]],10,q); `): print(`For the first 11 terms of the weight-enumerator of Motzkin paths: type:`): print(`Try: qnwdK([[1,1],[1,-1],[1,0]],10,q); `): elif arg=qnwdKTrunc then print(`qnwdKTrunc(S,K,z,deg): inputs a set of steps S, a positive integer K, a variable z, and a positive integer deg`): print(`outputs a list of length K, whose i-th entry is the enumerating function for the area of walks of length i with steps in S truncated to degree deg`): print(`Try: qnwdKTrunc([[1,1],[1,-1],[1,0]],5,z,5)`): elif arg=SeqOld then print(`SeqOld(S,K1,q,k,K2): inputs a set of steps S, positive integers K1, k, K2, and a variable q`): print(`Finds the recurrence for the enumerating function for the area of walks of length i with steps in S evaluated at q=1`): print(`and its derivative at q=1`): print(`Uses these recurrences to generate sequences L0 and L1, respectively`): print(`Outputs the last 40 terms of the sequence L0[i]/L1[i]/i`): elif arg=OpeSeq then print(`Seq(S,q,k,K2,n,N): inputs a set of steps S, positive integer k, and a variable q, large pos. intgeger K2, and symbols n and N`): print(`returns the recurrence up to complexity (ORDER+DEGREE), k, for the enumerating function for the area of walks of length i with steps in S evaluated at q=1`): print(`and its derivative at q=1`): print(`Uses these recurrences to generate sequences L0 (the number of walks with to [n,0]) and L1 (sum of the areas of all such walks) `): print(`Outputs the the last 40 terms of the sequence L1[i]/L0[i]. In other words, the average area. Try:`): print(`OpeSeq({[1,0],[1,-1],[1,1]},q,10,1000,n,N);`): elif arg=GuessCatExp1 then print(`GuessCatExp1(L,n,d): Given a list of numbers tries to match it with`): print(`(2*n)!/(n!*(n+1)!)*A(n)+B(n)*4^n for polynomials A(n) and B(n) of degree d. Try:`): print(`GuessCatExp1([seq((-4)^i*binomial(1/2,i+1)*(i^2+3)+(5*i^2+11*i+1)*(4)^i,i=1..14)],n,2);`): elif arg=GuessCatExp then print(`GuessCatExp(L,n): Given a list of numbers tries to match it with`): print(`(2*n)!/(n!*(n+1)!)*A(n)+B(n)*4^n for polynomials A(n) and B(n) of degree <=(nops(L)-6))/2. Try:`): print(`GuessCatExp1([seq((-4)^i*binomial(1/2,i+1)*(i^2+3)+(5*i^2+11*i+1)*(4)^i,i=1..14)],n,2);`): else print(`There is no help for`, args[1]): fi: end: ###start from HISTABRUT #AveAndMoms(f,x,N): Given a probability generating function #f(x) (a polynomial, rational function and possibly beyond) #returns a list whose first entry is the average #(alias expectation, alias mean) #followed by the variance, the third moment (about the mean) and #so on, until the N-th moment (about the mean). #If f(1) is not 1, than it first normalizes it by dividing #by f(1) (if it is not 0) . #For example, try: #AveAndMoms(((1+x)/2)^100,x,4); AveAndMoms:=proc(f,x,N) local mu,F,memu1,gu,i: mu:=simplify(subs(x=1,f)): if mu=0 then print(f, `is neither a prob. generating function nor can it be made so`): RETURN(FAIL): fi: F:=f/mu: memu1:=simplify(subs(x=1,diff(F,x))): gu:=[memu1]: F:=F/x^memu1: F:=x*diff(F,x): for i from 2 to N do F:=x*diff(F,x): gu:=[op(gu),simplify(subs(x=1,F))]: od: gu: end: #Alpha(f,x,N): Given a probability generating function #f(x) (a polynomial, rational function and possibly beyond) #returns a list, of length N, whose #(i) First entry is the average #(ii): Second entry is the variance #for i=3...N, the i-th entry is the so-called alpha-coefficients #that is the i-th moment about the mean divided by the #variance to the power i/2 (For example, i=3 is the skewness #and i=4 is the Kurtosis) #If f(1) is not 1, than it first normalizes it by dividing #by f(1) (if it is not 0) . #For example, try: #Alpha(((1+x)/2)^100,x,4); Alpha:=proc(f,x,N) local gu,i: gu:=AveAndMoms(f,x,N): if gu=FAIL then RETURN(gu): fi: if gu[2]=0 then print(`The variance is 0`): RETURN(FAIL): fi: [gu[1],gu[2],seq(gu[i]/gu[2]^(i/2),i=3..N)]: end: ###end from HISTABRUT Tr:=proc(w) local i,P: P:=[[0,0]]: for i from 1 to nops(w) do P:=[op(P),P[-1]+w[i]]: od: P: end: Ar:=proc(w) local i,P: P:=[[0,0]]: for i from 1 to nops(w) do P:=[op(P),P[-1]+w[i]]: od: add(P[i][2],i=1..nops(P)) end: qnw:=proc(S,n,q) local W,w: W:=walksnpos(S,n): add(q^Ar(w),w in W): end: qnwK:=proc(S,K,q) local n: [seq(qnw(S,n,q),n=0..K)]: end: qnmwd:=proc(S,n,m,q) local W,S2,s,W1: option remember: W := 0: if n=0 then RETURN(0): elif n=1 then if member([1,m],S)=true and 0<=m then RETURN(x*q^(m/2)) else RETURN(0): fi: else for s in S do if 0<=m - s[2] and 0<=n-s[1] then W1 := qnmwd(S,n - s[1],m - s[2],q): if W1<>0 then W := expand(W+x*q^(m-s[2]/2)*W1): fi: fi: od: fi: W: end: qnwd:=proc(S,n,q) option remember: qnmwd(S,n,0,q): end: qnwdK:=proc(S,K,q) local n,j: [1,seq(subs(x=1,coeff(add(qnwd(S,n,q),n=1..K),x,j)),j=1..K)]: end: qnwdKi:=proc(S,K,q,i) local n: [seq(qnwd(S,n*i,q),n=1..K)]: end: checkqnwd:=proc(S,K,q): evalb(qnwK(S,K,q)=qnwdK(S,K,q)): end: qnmwdTrunc:=proc(S,n,m,z,deg) local W,S2,s,W1: option remember: W := 0: S2 := {seq(s[2],s in S)}: if n=0 then RETURN(1): elif n=1 then if member(m,S2)=true and 0<=m then RETURN( simplify((1+z)^m,{z^(deg+1)})): else RETURN(0): fi: else for s in S2 do if 0<=m - s then : W1 := simplify(qnmwd(S,n - 1,m - s,z+1),{z^(deg+1)}): if W1<>0 then W := simplify(expand(W+q^m*W1),{z^(deg+1)}): fi: fi: od: fi: W: end: qnwdTrunc:=proc(S,n,z,deg) option remember: expand(qnmwdTrunc(S,n,0,z,deg)): end: qnwdKTrunc:=proc(S,K,z,deg) local n: [seq(qnwdTrunc(S,n,z,deg),n=1..K)]: end: FRarea:=proc(S,K,q,n,N,C) local L: L:=qnwdK(S,K,q): qFR(L,q,n,N,C): end: FRiarea:=proc(S,K,q,i,n,N,C) local L: L:=qnwdKi(S,K,q,i): qFR(L,q,n,N,C): end: D1:=proc(f,q,x,K) local g,i: g:=expand(1+x^2*f*q*subs(x=q*x,f)): add(coeff(g,x,i)*(x)^i,i=0..K): end: SeqD:=proc(q,x,K) local f1,f2,f3,i: f1:=1: f2:=D1(f1,q,x,K): while f1<>f2 do f3:=D1(f2,q,x,K): f1:=f2: f2:=f3: od: f2: end: CheckD:=proc(q,x,K) local L,i: L:=qnwdK({[1,1],[1,-1]},K,q): evalb(SeqD(q,x,K)=1+add(L[i]*x^i,i=1..nops(L))): end: Motz:=proc(f,q,x,K) local g,i: g:=expand(1+x^2*f*q*subs(x=q*x,f)+x*f): add(coeff(g,x,i)*x^i,i=0..K): end: SeqMotz:=proc(q,x,K) local f1,f2,f3,i: f1:=1: f2:=Motz(f1,q,x,K): while f1<>f2 do f3:=Motz(f2,q,x,K): f1:=f2: f2:=f3: od: f2: end: CheckMotz:=proc(q,x,K) local L,i: L:=qnwdK({[1,1],[1,-1],[1,0]},K,q): evalb(SeqMotz(q,x,K)=1+add(L[i]*x^i,i=1..nops(L))): end: F1:=proc(f,P,Q,R,q,x,K) local g, i: g:=expand(P+Q*f+R*f*subs(x=q*x,f)): add(coeff(g,x,i)*x^i,i=0..K): end: SeqF1:=proc(P,Q,R,q,x,K) local f1,f2,f3: f1:=1: f2:=F1(f1,P,Q,R,q,x,K): while f1<>f2 do f3:=F1(f2,P,Q,R,q,x,K): f1:=f2: f2:=f3: od: f2: end: DyckDeriv:=proc(q,x,k) local i,f,C,L,F,c,G,j,m: f[0]:=solve(C=1+x^2*C^2,C)[2]: F:=taylor(sum((q-1)^i*C[i](x)/i!,i=0..k)-(1+q*x^2*sum((q-1)^i*C[i](x)/i!,i=0..k)*sum((q-1)^i*C[i](q*x)/i!,i=0..k)),q=1,k+1): L:=[f[0]]: for i from 1 to k do c:=coeff(F,q-1,i): G:=solve(c,C[i](x)): G:=simplify(subs({seq(seq((D@@j)(C[m-1])(x)=diff(L[m],x$j),j=1..i),m=1..i), seq(C[m-1](x)=L[m], m=1..i)},G)): L:=[op(L),G]: od: L: end: CheckDyckDeriv:=proc(q,x,k,K) local i,j,S,L: L:=DyckDeriv(q,x,k): S:=SeqD(q,x,K): evalb([seq(coeff(taylor(L[1],x=0,K+10),x,j),j=0..K)]=[seq(coeff(subs(q=1,S),x,j),j=0..K)]), seq(evalb([seq( coeff(taylor(L[i+1],x=0,K+10),x,j),j=0..K)]=[seq(coeff(subs(q=1,diff(S,q$i)),x,j),j=0..K)]),i=1..k): end: MotzDeriv:=proc(q,x,k) local i,f,M,L,F,c,G,j,m: f[0]:=solve(M=1+x^2*M^2+x*M,M)[2]: F:=taylor(sum((q-1)^i*M[i](x)/i!,i=0..k)-(1+q*x^2*sum((q-1)^i*M[i](x)/i!,i=0..k)*sum((q-1)^i*M[i](q*x)/i!,i=0..k)+x*sum((q-1)^i*M[i](x)/i!,i=0..k)),q=1,k+1): L:=[f[0]]: for i from 1 to k do c:=coeff(F,q-1,i): G:=solve(c,M[i](x)): G:=simplify(subs({seq(seq((D@@j)(M[m-1])(x)=diff(L[m],x$j),j=1..i),m=1..i), seq(M[m-1](x)=L[m], m=1..i)},G)): L:=[op(L),G]: od: L: end: CheckMotzDeriv:=proc(q,x,k,K) local i,j,S,L: L:=MotzDeriv(q,x,k): S:=SeqMotz(q,x,K): evalb([seq(coeff(taylor(L[1],x=0,K+10),x,j),j=0..K)]=[seq(coeff(subs(q=1,S),x,j),j=0..K)]), seq(evalb([seq( coeff(taylor(L[i+1],x=0,K+10),x,j),j=0..K)]=[seq(coeff(subs(q=1,diff(S,q$i)),x,j),j=0..K)]),i=1..k): end: DerK:=proc(P,Q,R,q,x,k) local eq,sol,test,L,i,m,j,F,c,G,f: option remember: eq:=f=subs(q=1,P)+subs(q=1,Q)*f+subs(q=1,R)*f^2: sol:=solve(eq,f): test:=[type(series(sol[1],x),taylor),type(series(sol[2],x),taylor)]: if test[1]=true then sol:=sol[1]: elif test[2]=true then sol:=sol[2]: else RETURN(FAIL): end: L:=[sol]: F := taylor(sum((q - 1)^i*f[i](x)/i!, i = 0 .. k) - P - Q*sum((q - 1)^i*f[i](x)/i!, i = 0 .. k)-R*sum((q - 1)^i*f[i](x)/i!, i = 0 .. k)*sum((q - 1)^i*f[i](x*q)/i!, i = 0 .. k), q = 1, k + 1): for i to k do c := coeff(F, q - 1, i): G := solve(c, f[i](x)): G := simplify(subs({seq(seq((D@@j)(f[m-1])(x)=diff(L[m],x$j),j=1..i),m=1..i), seq(f[m-1](x)=L[m], m=1..i)},G)): L := [op(L), G]: od: end: ####### From EW.txt ######## Help1EW:=proc(): print(`The Main procedures are:`): print(`walksn(S,n)`, `numwalksn(S,n)`,`numwalksK(S,K)`, `findrecwalks(S,K,n,N,maxC)`): print(`walksnpos(S,n)`, `numwalksnpos(S,n)`, `numwalksKpos(S,K)`, `findrecposwalks(S,K,n,N,maxC)`): #print(`walksnm(S,n,m)`, `walksn(S,n)`, `walksK(S,K)`): #print(`walksnmpos(S,n,m)`, `walksnpos(S,n)`, `walksKpos(S,K)`): #print(`numwalksnm(S,n,m)`, `numwalksn(S,n)`, `numwalksK(S,K)`): #print(`numwalksnmpos(S,n,m)`, `numwalksnpos(S,n)`, `numwalksKpos(S,K)`): end: #walksnm(S,n,m): the set of walks of length n with steps in S={[1,b1],[1,b2],...} from [0,0] to [n,m] walksnm:=proc(S,n,m) local W, S2,s,W1,w: option remember: W:={}: S2:={seq(s[2],s in S)}: if n=0 then RETURN({[]}): elif n=1 then if member(m,S2)=true then W:={[m]}: else RETURN({}): fi: else for s in S2 do W1:=op({walksnm(S,n-1,m-s)} minus {{}}): if W1<>{} then W:=W union {seq([op(w),s],w in W1)}: fi: od: fi: W: end: #walksn(S,n): the set of walks of length n with steps in S={[1,b1],[1,b2],...} from [0,0] to [n,0] walksn:=proc(S,n) local W,w,i: W:=walksnm(S,n,0): {seq([seq([1,w[i]],i=1..nops(w))],w in W)}: end: #walksK(S,K): the sequence enumerating walks of length n with steps in S={[1,b1],[1,b2],...} from [0,0] to [n,0] from n=1 to n=k walksK:=proc(S,K) local W,n: seq(nops(walksn(S,n)),n=1..K): end: #walksnmpos(S,n,m): the set of walks of length n with steps in S={[1,b1],[1,b2],...} from [0,0] to [n,m]that have non-negative height walksnmpos:=proc(S,n,m) local W, S2,s,W1,w: option remember: W:={}: S2:={seq(s[2],s in S)}: if n=0 then RETURN({[]}): elif n=1 then if (member(m,S2)=true and m>=0) then W:={[m]}: else RETURN({}): fi: else for s in S2 do if m-s>=0 then W1:=op({walksnmpos(S,n-1,m-s)} minus {{}}): if W1<>{} then W:=W union {seq([op(w),s],w in W1)}: fi: fi: od: fi: W: end: #walksnpos(S,n): the set of walks of length n with steps in S={[1,b1],[1,b2],...} from [0,0] to [n,0]that never have negative height walksnpos:=proc(S,n) local W,i,w: W:=walksnmpos(S,n,0): {seq([seq([1,w[i]],i=1..nops(w))],w in W)}: end: #walksKpos(S,K): the sequence enumerating walks of length n with steps in S={[1,b1],[1,b2],...} from [0,0] to [n,0] from n=1 to n=k that never have negative height walksKpos:=proc(S,K) local W,n: seq(nops(walksnpos(S,n)),n=1..K): end: numwalksnm:=proc(S,n,m) local W, S2,s,W1: option remember: W:=0: S2:={seq(s[2],s in S)}: if n=0 then RETURN(1): elif n=1 then if member(m,S2)=true then RETURN(1): else RETURN(0): fi: else for s in S2 do W1:=numwalksnm(S,n-1,m-s): if W1<>{} then W:=W +W1: fi: od: fi: W: end: #numwalksn(S,n): the number of walks of length n with steps in S={[1,b1],[1,b2],...} from [0,0] to [n,0] numwalksn:=proc(S,n) local W: numwalksnm(S,n,0): end: #numwalksK(S,K): the sequence enumerating walks of length n with steps in S={[1,b1],[1,b2],...} from [0,0] to [n,0] from n=1 to n=k numwalksK:=proc(S,K) local W,n: [seq(numwalksnm(S,n,0),n=1..K)]: end: numwalksnmpos:=proc(S,n,m) local W, S2,s,W1: option remember: W:=0: S2:={seq(s[2],s in S)}: if n=0 then RETURN(1): elif n=1 then if member(m,S2)=true and m>=0 then RETURN(1): else RETURN(0): fi: else for s in S2 do if m-s>=0 then W1:=numwalksnmpos(S,n-1,m-s): if W1<>{} then W:=W +W1: fi: fi: od: fi: W: end: #numwalksnpos(S,n): the number of walks of length n with steps in S={[1,b1],[1,b2],...} from [0,0] to [n,0] numwalksnpos:=proc(S,n) local W,w,i: numwalksnmpos(S,n,0): end: #numwalksKpos(S,K): the sequence enumerating walks of length n with steps in S={[1,b1],[1,b2],...} from [0,0] to [n,0] from n=1 to n=k numwalksKpos:=proc(S,K) local W,n: [seq(numwalksnpos(S,n),n=1..K)]: end: findrecposwalks:=proc(S,K,n,N,maxC): Findrec(numwalksKpos(S,K),n,N,maxC): end: findrecwalks:=proc(S,K,n,N,maxC): Findrec(numwalksK(S,K),n,N,maxC): end: SeqOld:=proc(S,K1,q,k,K2) local L,L1,ope,L0,ope0,ope1,L0a,L1a,N,i,n: L:= qnwdK(S,K1,q): L0:=subs(q=1, L): L1:=[seq(subs(q=1, diff(L[i],q)),i=1..nops(L))]: ope0:=Findrec(L0,n,N,15): if ope0=FAIL then print(`can't find recurrence`): RETURN(FAIL): fi: L0a:=SeqFromRec(ope0,n,N,[op(1..degree(ope0,N),L0)],K2): ope1:=Findrec(L1,n,N,15): if ope1=FAIL then print(`can't find recurrence for derivative`): RETURN(FAIL): fi: L1a:=SeqFromRec(ope1,n,N,[op(1..degree(ope1,N),L1)],K2): seq(evalf(L1a[i]/L0a[i]/i),i=nops(L1a)-40..nops(L1a)): end: OpeSeq:=proc(S,q,k,K2,n,N) local K1,L,L1,ope,L0,ope0,ope1,L0a,L1a,i,D1: K1:=max(seq((2+D1)*(1+k-D1),D1=0..k))+8: L:= qnwdK(S,K1,q): L0:=subs(q=1, L): L1:=[seq(subs(q=1, diff(L[i],q)),i=1..nops(L))]: ope0:=Findrec(L0,n,N,k): if ope0=FAIL then print(`can't find recurrence`): RETURN(FAIL): fi: L0a:=SeqFromRec(ope0,n,N,[op(1..degree(ope0,N),L0)],K2): ope1:=Findrec(L1,n,N,k): if ope1=FAIL then print(`can't find recurrence for derivative`): RETURN(FAIL): fi: L1a:=SeqFromRec(ope1,n,N,[op(1..degree(ope1,N),L1)],K2): [ope0,ope1,seq(evalf(L1a[i]/L0a[i]),i=nops(L1a)-40..nops(L1a))]: end: #################### From Findrec.txt #################### #findrec(f,DEGREE,ORDER,n,N): guesses a recurrence operator annihilating #the sequence f of degree DEGREE and order ORDER #For example, try: findrec([seq(i,i=1..10)],0,2,n,N); findrec:=proc(f,DEGREE,ORDER,n,N) local ope,var,eq,i,j,n0,kv,var1,eq1,mu,a: option remember: if not findrecEx(f,DEGREE,ORDER,ithprime(20)) then RETURN(FAIL): fi: if not findrecEx(f,DEGREE,ORDER,ithprime(40)) then RETURN(FAIL): fi: if not findrecEx(f,DEGREE,ORDER,ithprime(80)) then RETURN(FAIL): fi: if (1+DEGREE)*(1+ORDER)+5+ORDER>nops(f) then ERROR(`Insufficient data for a recurrence of order`,ORDER, `degree`,DEGREE): fi: ope:=0: var:={}: for i from 0 to ORDER do for j from 0 to DEGREE do ope:=ope+a[i,j]*n^j*N^i: var:=var union {a[i,j]}: od: od: eq:={}: for n0 from 1 to (1+DEGREE)*(1+ORDER)+4 do eq1:=0: for i from 0 to ORDER do eq1:=eq1+subs(n=n0,coeff(ope,N,i))*op(n0+i,f): od: eq:= eq union {eq1}: od: var1:=solve(eq,var): kv:={}: for i from 1 to nops(var1) do mu:=op(i,var1): if op(1,mu)=op(2,mu) then kv:= kv union {op(1,mu)}: fi: od: ope:=subs(var1,ope): if ope=0 then RETURN(FAIL): fi: ope:={seq(coeff(expand(ope),kv[i],1),i=1..nops(kv))} minus {0}: if nops(ope)>1 then RETURN(Yafe(ope[1],N)[2]): elif nops(ope)=1 then RETURN(Yafe(ope[1],N)[2]): else RETURN(FAIL): fi: end: Yafe:=proc(ope,N) local i,ope1,coe1,L: if ope=0 then RETURN(1,0): fi: ope1:=expand(ope): L:=degree(ope1,N): coe1:=coeff(ope1,N,L): ope1:=normal(ope1/coe1): ope1:=normal(ope1): ope1:= convert( [seq(factor(coeff(ope1,N,i))*N^i,i=ldegree(ope1,N)..degree(ope1,N))],`+`): factor(coe1),ope1: end: #Findrec(f,n,N,MaxC): Given a list f tries to find a linear recurrence equation with #poly coffs. #of maximum DEGREE+ORDER<=MaxC #e.g. try Findrec([1,1,2,3,5,8,13,21,34,55,89],n,N,2); Findrec:=proc(f,n,N,MaxC) local DEGREE, ORDER,ope,L: for L from 0 to MaxC do for ORDER from 1 to L do DEGREE:=L-ORDER: if (2+DEGREE)*(1+ORDER)+4>=nops(f) then print(`Insufficient data for degree`, DEGREE, `and order `,ORDER): RETURN(FAIL): fi: ope:=findrec([op(1..(2+DEGREE)*(1+ORDER)+4,f)],DEGREE,ORDER,n,N): if ope<>FAIL then RETURN(ope): fi: od: od: FAIL: end: #SeqFromRec(ope,n,N,Ini,K): Given the first L-1 #terms of the sequence Ini=[f(1), ..., f(L-1)] #satisfied by the recurrence ope(n,N)f(n)=0 #extends it to the first K values SeqFromRec:=proc(ope,n,N,Ini,K) local ope1,gu,L,n1,j1: ope1:=Yafe(ope,N)[2]: L:=degree(ope1,N): if nops(Ini)<>L then ERROR(`Ini should be of length`, L): fi: ope1:=expand(subs(n=n-L,ope1)/N^L): gu:=Ini: for n1 from nops(Ini)+1 to K do gu:=[op(gu), -add(gu[nops(gu)+1-j1]*subs(n=n1,coeff(ope1,N,-j1)), j1=1..L)]: od: gu: end: #end Findrec with(linalg): #findrecEx(f,DEGREE,ORDER,m1): Explores whether thre #is a good chance that there is a recurrence of degree DEGREE #and order ORDER, using the prime m1 #For example, try: findrecEx([seq(i,i=1..10)],0,2,n,N,1003); findrecEx:=proc(f,DEGREE,ORDER,m1) local ope,var,eq,i,j,n0,eq1,a,A1, D1,E1,Eq,Var,f1,n,N: option remember: f1:=f mod m1: if (1+DEGREE)*(1+ORDER)+5+ORDER>nops(f) then ERROR(`Insufficient data for a recurrence of order`,ORDER, `degree`,DEGREE): fi: ope:=0: var:={}: for i from 0 to ORDER do for j from 0 to DEGREE do ope:=ope+a[i,j]*n^j*N^i: var:=var union {a[i,j]}: od: od: eq:={}: for n0 from 1 to (1+DEGREE)*(1+ORDER)+4 do eq1:=0: for i from 0 to ORDER do eq1:=eq1+subs(n=n0,coeff(ope,N,i))*op(n0+i,f1) mod m1: od: eq:= eq union {eq1}: od: Eq:= convert(eq,list): Var:= convert(var,list): D1:=nops(Var): E1:=nops(Eq): if E10 then RETURN(false): fi: if E1-D1>=1 then for j from 1 to nops(Var) do A1[D1,j]:=coeff(Eq[D1+1],Var[j]): od: if det(A1) mod m1 <>0 then RETURN(false): fi: fi: if E1-D1>=2 then for j from 1 to nops(Var) do A1[D1,j]:=coeff(Eq[D1+2],Var[j]): od: if det(A1) mod m1 <>0 then RETURN(false): fi: fi: true: end: ####### From qFindRec.txt by Doron Zeilberger ######## #qFR1(L,deg1,ord1,q,n,N): inputs a list L of polynomials (or rational functions) in q, and non-negative integers #deg1 and ord1 tries to find an operator ope(q,q^n,N) annihilating L. Try #qFR1([seq(q^(i1^2),i1=1..10)],1,2,q,n,N); qFR1:=proc(L,deg1,ord1,q,n,N) local a,ope,var,i,j,eq,eq1,hal,i1,n1,lu,hal1,lu1: if nops(L)<= (ord1+1)*(deg1+2)+3 then print(`The list is too short, it has `, nops(L), `terms but it should have at least`, (ord1+1)*(deg1+2)+3, `terms .` ): RETURN(FAIL): fi: ope:=add(add(a[i,j]*(q^(n*i))*N^j,i=0..deg1),j=0..ord1): var:={seq(seq(a[i,j],i=0..deg1),j=0..ord1)}: eq:=expand({seq(add(subs(n=n1,coeff(ope,N,i1))*L[n1+i1],i1=0..ord1),n1=1..(ord1+1)*(deg1+1)+3 ) }): eq1:=subs(q=2,eq): hal:=solve(eq1,var): if expand(subs(hal,ope))=0 then RETURN(FAIL): else print(`There is hope for a recurrence of order`, ord1, `and degree`, deg1): fi: hal:=solve(eq,var): if expand(subs(hal,ope))=0 then RETURN(FAIL): fi: lu:={}: for hal1 in hal do if op(1,hal1)=op(2,hal1) then lu:=lu union {op(1,hal1)}: fi: od: if nops(lu)>1 then print(`Non unique solution`): RETURN({seq(coeff(ope,lu1,1),lu1 in lu)}): fi: ope:=subs(hal,ope): ope:=subs(lu[1]=1,ope): if normal(expand({seq(add(subs(n=n1,coeff(ope,N,i1))*L[n1+i1],i1=0..ord1),n1=(ord1+1)*(deg1+1)+3..nops(L)-ord1 ) }))<>{0} then print(ope, `did not work out`): RETURN(FAIL): fi: add(factor(coeff(ope,N,i1))*N^i1,i1=0..ord1): end: #qFR(L,q,n,N,C): inputs a list L of polynomials (or rational functions) in q, and non-negative integers # tries to find an operator ope(q,q^n,N) of degree deg1 and order ord1 such that deg1+ord1<=C #annihilating L. or returns FAIL. L must be at least of length (C+3)^2/4+4. Try #qFR([seq(q^(i1^2),i1=1..10)],q,n,N,3); qFR:=proc(L,q,n,N,C) local ope, ord1,deg1,C1: if nops(L)< (C+3)^2/4+4 then print(`L must be at least of length`, trunc((C+3)^2/4+4)): RETURN(FAIL): fi: for C1 from 1 to C do for ord1 from 1 to C1 do deg1:=C1-ord1: ope:=qFR1(L,deg1,ord1,q,n,N): if ope<>FAIL then RETURN(ope): fi: od: od: FAIL: end: #Stat(F,t,K): Given a generating function F of t, for a r.v. finds the statistical information. Try: #Stat((1_t)^10000,4); Stat:=proc(F,t,K) local gu,mu,sd,k,f: f:=evalf(F/subs(t=1,F)): mu:=subs(t=1,diff(f,t)): gu:=[mu]: f:=f/t^mu: f:=t*diff(t*diff(f,t),t): sd:=sqrt(subs(t=1,f)): gu:=[op(gu),sd]: for k from 3 to K do f:=t*diff(f,t): gu:=[op(gu),subs(t=1,f)/sd^k]: od: gu: end: #empir(gu,degx,degP,x,P) #to "fit" an algebraic equation F(P(x),x)=0 of degree #degP in P(x) and degx in n for P(x):=sum_i gu[i]*x^i empir:=proc(gu,degx,degP,x,P) local i1,i2,F,a,cand,lu,eq,var,mu,flo,pip: if (1+degx)*(1+degP) > nops(gu)-3 then RETURN(`sequence too small`): fi: F:=0: var:={}: for i1 from 0 to degx do for i2 from 0 to degP do F:=F+a[i1,i2]*x^i1*P^i2: var:=var union {a[i1,i2]}: od: od: cand:=0: for i1 from 0 to nops(gu)-1 do cand:=cand+op(i1+1,gu)*x^i1: od: lu:=subs(P=cand,F): lu:=taylor(lu,x=0,nops(gu)-1): eq:={}: for i1 from 0 to nops(gu)-2 do eq:=eq union {coeff(lu,x,i1)=0} od: mu:=solve(eq,var): F:=subs(mu,F): if F=0 then RETURN(0): fi: flo:=degree(F,P): pip:=coeff(F,P,flo): flo:=degree(pip,x): pip:=coeff(pip,x,flo): F:=F/pip: normal(F): end: #Empir(L,x,P): Guesses an algebraic equation Empir:=proc(gu,x,P) local degx,degP,L,lu,i: for L from 1 to (nops(gu)-3)/3 do for degP from 1 to L do for degx from 0 to min(trunc((nops(gu)-3)/(1+degP))-1,L-degP) do lu:=empir(gu,degx,degP,x,P): if lu<>0 then lu:=add(factor(coeff(lu,P,i))*P^i,i=0..degree(lu,P)): RETURN(lu): fi: od: od: od: 0: end: PowerK:=proc(P,Q,R,q,x,k) local gu,mu,mu1,i,j: option remember: gu:=DerK(P,Q,R,q,x,k): mu:=[gu[1]]: for i from 1 to k do mu1:=simplify(normal(add(stirling2(i,j)*gu[j+1],j=1..i))): mu:=[op(mu),mu1]: od: mu: end: ###start from HISTABRUT #AveAndMoms(f,x,N): Given a probability generating function #f(x) (a polynomial, rational function and possibly beyond) #returns a list whose first entry is the average #(alias expectation, alias mean) #followed by the variance, the third moment (about the mean) and #so on, until the N-th moment (about the mean). #If f(1) is not 1, than it first normalizes it by dividing #by f(1) (if it is not 0) . #For example, try: #AveAndMoms(((1+x)/2)^100,x,4); AveAndMoms:=proc(f,x,N) local mu,F,memu1,gu,i: mu:=simplify(subs(x=1,f)): if mu=0 then print(f, `is neither a prob. generating function nor can it be made so`): RETURN(FAIL): fi: F:=f/mu: memu1:=simplify(subs(x=1,diff(F,x))): gu:=[memu1]: F:=F/x^memu1: F:=x*diff(F,x): for i from 2 to N do F:=x*diff(F,x): gu:=[op(gu),simplify(subs(x=1,F))]: od: gu: end: #Alpha(f,x,N): Given a probability generating function #f(x) (a polynomial, rational function and possibly beyond) #returns a list, of length N, whose #(i) First entry is the average #(ii): Second entry is the variance #for i=3...N, the i-th entry is the so-called alpha-coefficients #that is the i-th moment about the mean divided by the #variance to the power i/2 (For example, i=3 is the skewness #and i=4 is the Kurtosis) #If f(1) is not 1, than it first normalizes it by dividing #by f(1) (if it is not 0) . #For example, try: #Alpha(((1+x)/2)^100,x,4); Alpha:=proc(f,x,N) local gu,i: gu:=AveAndMoms(f,x,N): if gu=FAIL then RETURN(gu): fi: if gu[2]=0 then print(`The variance is 0`): RETURN(FAIL): fi: [gu[1],gu[2],seq(gu[i]/gu[2]^(i/2),i=3..N)]: end: ###end from HISTABRUT #AlphaFE(P,Q,R,q,x,k,N1): Alpha(coeff(f(x,q),x,i),q,N1) AlphaFE:=proc(P,Q,R,q,x,k,N1) local lu,i,gu,j,ku1,av,fu,j1: lu:=PowerK(P,Q,R,q,x,k): lu:=[seq(coeff(taylor(lu[i],x=0,N1+3),x,N1),i=1..nops(lu))]: lu:=[seq(lu[i+1]/lu[1],i=1..nops(lu)-1)]: av:=lu[1]: gu:=[av]: for j from 2 to k do ku1:=add(binomial(j,j1)*(-av)^j1*lu[j-j1],j1=0..j-1)+(-av)^j: gu:=[op(gu),ku1]: od: fu:=[gu[1],gu[2]]: for i from 3 to k do fu:=[op(fu),gu[i]/gu[2]^(i/2)]: od: fu: end: #GuessCatExp1(L,n,d): Given a list of numbers tries to match it with #(-4)^n*binomial(1/2,n+1)*A(n)+B(n)*4^n for polynomials A(n) and B(n) of degree d. Try: #GuessCatExp1([seq( (2*i)!/(i!*(i+1)!)*(i^2+3)+(4)^i*(5*i^2+11*i+1),i=1..14),n,2); GuessCatExp1:=proc(L,n,d) local A,B,a,b,i,var,eq,gu,n1: if nops(L)-(2*d+2)<=4 then print(`the list L should have at least 2*d+6 term`): RETURN(FAIL): fi: A:=add(a[i]*n^i,i=0..d): B:=add(b[i]*n^i,i=0..d): gu:=(2*n)!/(n!*(n+1)!)*A+4^n*B: eq:={seq(eval(subs(n=n1,gu))-L[n1],n1=1..2*d+6)}: var:={seq(a[i],i=0..d),seq(b[i],i=0..d)}: var:=solve(eq,var): if var=NULL then RETURN(FAIL): fi: gu:=subs(var,gu): if {seq(eval(subs(n=n1,gu))-L[n1],n1=2*d+7..nops(L))}<>{0} then RETURN(FAIL): fi: gu: end: #GuessCatExp(L,n): Given a list of numbers tries to match it with #(2*n)!/(n!*(n+1)!)*A(n)+B(n)*4^n for polynomials A(n) and B(n) #GuessCatExp([seq( (2*i)!/(i!*(i+1)!)*(i^2+3)+(4)^i*(5*i^2+11*i+1),i=1..14),n); GuessCatExp:=proc(L,n) local d,gu: for d from 0 to trunc((nops(L)-6)/2) do gu:=GuessCatExp1(L,n,d): if gu<>FAIL then RETURN(gu): fi: od: FAIL: end: #PowerDyck(n,k): the list of length k whose k-th term is the explicit expression in n for the sum of the k-th power of the areas under all Dyck paths of length 2*n. Try: #PowerDyck(n,10); PowerDyck:=proc(n,k) local gu,lu,lu1,k1,q,x,i: option remember: gu:=PowerK(1,0,q*x^2,q,x,k): gu:=subs(x=sqrt(x),gu): lu:=[]: for k1 from 1 to k do lu1:=taylor(gu[k1+1],x=0,4*k+13): lu1:=[seq(coeff(lu1,x,i),i=1..4*k+6)]: lu1:=GuessCatExp(lu1,n): if lu1=FAIL then RETURN(lu): else lu:=[op(lu),lu1]: fi: od: lu: end: #MomDyck(n,k): the list of length k whose first entry is the exact expression in n for the average are under a Dyck path from 0 to 2*n #the second entry is the variance, and the third through the k-th are the moments about the mean. Try: #MomDyck(n,10); MomDyck:=proc(n,k) local gu,av,gu0,lu,lu1,i,k1: option remember: gu0:=(2*n)!/(n!*(n+1)!): gu:=PowerDyck(n,k): av:=gu[1]/gu0: gu:=[seq(normal(gu[i]/gu0),i=1..k)]: lu:=[av]: for k1 from 2 to k do lu1:=add((-av)^i*binomial(k1,i)*gu[k1-i],i=0..k1-1)+(-av)^k1: lu1:=normal(lu1): lu:=[op(lu),lu1]: od: lu: end: #LimMomDyck(n): the list of length k whose first entry is the average area are under a Dyck path from 0 to 2*n divided by n^(3/2) #the second entry is the limit of the variance divided by n^3, and the third through the k-th are the limits the SCALED moments about the mean. #It also returns the limits of the scaled moments starting at the third moment (skewness). Try: #LimMomDyck(n,10); LimMomDyck:=proc(k) local gu,i,n: gu:=MomDyck(n,k): gu:=[limit(gu[1]/n^(3/2),n=infinity), limit(gu[2]/n^3,n=infinity), seq(limit(gu[i]/gu[2]^(i/2),n=infinity),i=3..k)]: normal(gu): end: #DyckStory(n,k): an article about explicit expressions for the sum of the powers of the area under Dyck path of length 2n followed by the asymptotics and thoes of the #scaled moments. Try: #DyckStory(n,10); DyckStory:=proc(n,k) local gu,lu,i,j,t0,ku: t0:=time(): print(`Explicit Expressions, in n, for the sum of the powers of the areas under Dyck paths of length 2n from the first all the way to the`, k, `-th and the implied limiting scaled moments `): print(`using AJ Bu's Maple package qEW.txt `): print(``): print(`By Shalosh B. Ekhad `): print(``): gu:=PowerDyck(n,k): print(``): for i from 1 to k do print(``): print(`------------------------------------------------------------`): print(``): print(`The sum of the`, i, `-th power of the areas of all Dyck paths of length 2n is`): print(``): print(gu[i]): print(``): print(`and in Maple notation`): print(``): lprint(gu[i]): print(``): print(`For the sake of the OEIS, the first 30 terms are`): print(``): print([seq(eval(subs(n=j,gu[i])),j=1..30)]): print(``): od: print(``): print(`-----------------------------------------------`): lu:=LimMomDyck(k): print(`The average of the area is asympotic to`, lu[1]*n^(3/2) ): print(``): print(`The variance of the area is asympotic to`, lu[2]*n^3 ): print(``): if k>=3 then print(`The limiting skewness is`, lu[3]): print(``): print(`and in Maple notation`): print(``): lprint(lu[3]): print(``): fi: if k>=4 then print(`The limiting kurtosisis`, lu[4]): print(`and in Maple notation`): print(``): lprint(lu[4]): print(``): fi: print(`The limiting scaled moments up to the`, k, `-th is`): print(``): print([op(3..k,lu)]): print(``): print(`and in Maple notation`): print(``): lprint([op(3..k,lu)]): print(``): print(`and in decimals`): print(``): lprint( evalf([op(3..k,lu)])): print(``): ku:=EBkSeq(k): if [seq(simplify(ku[i]-lu[i]),i=3..k)]<>[0$(k-2)] then print(`unfortunately the limiting scaled moments do not match with those of the area under Brownian excrusion`): print( [seq(simplify(ku[i]-lu[i]),i=3..k)]): else print(`Note that the limits of the scaled moments up to the`, k, `-th match those of the area under Brownian excursion`): fi: print(``): print(`----------------------------------------------`): print(``): print(`This took`, time()-t0, `moments `): end: #Kk(k): K_k given by Eq. (7) of Svante Janson's article (p.6) Kk:=proc(k) local j: option remember: if k=0 then -1/2: else (3*k-4)/4*Kk(k-1)+add(Kk(j)*Kk(k-j),j=1..k-1): fi: end: #EBk(k): The k-th moment of the area under a Brownian motion. Try: #[seq(EBk(i),i=1..10)]: EBk:=proc(k) 4*sqrt(Pi)*2^(-k/2)*k!/GAMMA((3*k-1)/2)*Kk(k): end: #EBkSeq(N): the scaled moments about the mean of the area under Brownian Excursion EBkSeq:=proc(N) local mu,m2,mk,j,L,i: mu:=EBk(1): m2:=EBk(2)-mu^2: L:=[mu,m2]: for i from 3 to N do mk:=add((-mu)^j*EBk(i-j)*binomial(i,j),j=0..i): L:=[op(L),mk]: od: L:=[L[1],L[2],seq(L[i]/m2^(i/2),i=3..N)]: end: #MotSeq(N): The first N terms of the Motzkin sequence MotSeq:=proc(N) local f1,i: f1:=PowerK(1,x,q*x^2,q,x,2)[1]: f1:=taylor(f1,x=0,N+10): [seq(coeff(f1,x,i),i=1..N)]: end: #MotSeq1(N): The first N terms of the Motzkin sequence 3^(n+1)+(-1)^n MotSeq1:=proc(N) local i: [seq(3^(i+1)+(-1)^i,i=1..N)]: end: ##### #GuessMotExp1(L,n,d,Mn,Mn1): Given a list of numbers tries to match it with #A1(n)*M(n)+A2(n)*M(n+1)+B(n)*(3^(n+1)+(-1)^n) for polynomials A(n), B(n), and C(n) of degree d. Try: GuessMotExp1:=proc(L,n,d,Mn,Mn1) local A1,A2,B,C,a1,a2,b,c,i,var,eq,n1,M0,gu: if nops(L)-(4*d+10)<=4 then print(`the list L should have at least`, 4*d+15, ` term`): RETURN(FAIL): fi: M0:=MotSeq(nops(L)+10): A1:=add(a1[i]*n^i,i=0..d): A2:=add(a2[i]*n^i,i=0..d): B:=add(b[i]*n^i,i=0..d): C:=add(c[i]*n^i,i=0..d): gu:=Mn*A1+Mn1*A2+B*3^n+C*(-1)^n: eq:={seq(eval(subs({n=n1,Mn=M0[n1],Mn1=M0[n1+1]},gu))-L[n1],n1=1..4*d+10)}: var:={seq(a1[i],i=0..d),seq(a2[i],i=0..d),seq(b[i],i=0..d), seq(c[i],i=0..d) }: var:=solve(eq,var): if var=NULL then RETURN(FAIL): fi: gu:=subs(var,gu): if {seq(eval(subs({n=n1,Mn=M0[n1],Mn1=M0[n1+1]},gu))-L[n1],n1=4*d+11..nops(L)-1)}<>{0} then RETURN(FAIL): fi: gu: end: #GuessMotExp(L,n,Mn,Mn1): Given a list of numbers tries to match it with #Mn(n)*A1(n)+Mn(n+1)*A2(n)+B(n)*(3^(n+1)+C(n)*(-1)^n)/4 for polynomials A1(n), A2(n), and B(n) where Mn are the Motzkin numbers GuessMotExp:=proc(L,n,Mn,Mn1) local d,gu: for d from 0 to trunc((nops(L)-20)/4) do gu:=GuessMotExp1(L,n,d,Mn,Mn1): if gu<>FAIL then RETURN(gu): fi: od: FAIL: end: #PowerMotzkin(n,k,Mn,Mn1): the list of length k whose k-th term is the explicit expression in n for the sum of the k-th power of the areas under all Motzkin paths of length n. Try: #PowerMotzkin(n,10,Mn,Mn1); PowerMotzkin:=proc(n,k,Mn,Mn1) local gu,lu,lu1,k1,q,x,i: option remember: gu:=PowerK(1,x,q*x^2,q,x,k): lu:=[]: for k1 from 1 to k do lu1:=taylor(gu[k1+1],x=0,10*k+100): lu1:=[seq(coeff(lu1,x,i),i=1..10*k+90)]: lu1:=GuessMotExp(lu1,n,Mn,Mn1): if lu1=FAIL then RETURN(lu): else lu:=[op(lu),lu1]: fi: od: lu: end: #AsyMot(n): The asympotic expansion of the Motzkin numbers AsyMot:=proc(n): sqrt(3/4/Pi)*3^(n+1)/n^(3/2)* (-16/39*n+1-205/96/n+29295/6656/n^2-3807433/425984/n^3+122752707/6815744/n^4-\ 1819489265/50331648/n^5+19445004755/268435456/n^6-14948395979231/103079215104/n ^7+159501459942363/549755813888/n^8-10210770100027665/17592186044416/n^9): end: #MomMotzkin(n,k,Mn,Mn1): the list of length k whose first entry is the exact expression in n for the average are under a Motzkin path from [0,0] to [n,0] #the second entry is the variance, and the third through the k-th are the moments about the mean. #Here Mn is short for M(n) and Mn1 for M(n+1). #Try: #MomMotzkin(n,10,Mn,Mn1); MomMotzkin:=proc(n,k,Mn,Mn1) local gu,av,gu0,lu,lu1,i,k1: option remember: gu:=PowerMotzkin(n,k,Mn,Mn1): av:=gu[1]/Mn: gu:=[seq(normal(gu[i]/Mn),i=1..k)]: lu:=[av]: for k1 from 2 to k do lu1:=add((-av)^i*binomial(k1,i)*gu[k1-i],i=0..k1-1)+(-av)^k1: lu1:=normal(lu1): lu:=[op(lu),lu1]: od: lu: end: #LimMomMotzkin(k): the list of length k whose first entry is the asympotic to order r in n for the average are under a Dyck path from 0 to 2*n #the second entry is the asympotitc for variance, and the third through the k-th are the asympotics to order r of the SCALED moments about the mean. #It also returns the limits of the scaled moments starting at the third moment (skewness). Try: #LimMomMotzkin(10); LimMomMotzkin:=proc(k) local n,gu,i,Mn,Mn1,lu,lu1: gu:=MomMotzkin(n,k,Mn,Mn1): #lu:=sqrt(3/4/Pi)*3^(n+1)/n^(3/2)*(-16/39*n+1-205/96/n+29295/6656/n^2-3807433/425984/n^3+122752707/6815744/n^4): lu:=sqrt(3/4/Pi)*3^(n+1)/n^(3/2): lu1:=subs(n=n+1,lu): gu:=subs({Mn=lu,Mn1=lu1},gu): gu:=[limit(gu[1]/n^(3/2),n=infinity), limit(gu[2]/n^3,n=infinity), seq(limit(gu[i]/gu[2]^(i/2),n=infinity),i=3..k)]: normal(gu): end: #MotzkinStory(n,k): an article about explicit expressions for the sum of the powers of the area under Motzkin path of length n followed by the asymptotics and thoes of the #scaled moments. Try: #MotzkinStory(n,7); MotzkinStory:=proc(n,k) local gu,lu,i,j,Mn,Mn1,M,r,M0,ku,t0: t0:=time(): M0:=MotSeq(50): print(`Explicit Expressions, in n, for the sum of the powers of the areas under Motzkin paths of length n from the first all the way to the`, k, `-th and the implied limiting scaled moments `): print(`using AJ Bu's Maple package qEW.txt (and its extension qEWplus.txt) `): print(``): print(`By Shalosh B. Ekhad `): print(``): gu:=PowerMotzkin(n,k,Mn,Mn1): print(``): print(`Let M[n] denote the Motzkin numbers, that may be defined by`): print(``): print(M[n]=Sum(n!*(2*r)!/(r!^2*(n-r)!*(r+1)!),r=0..n)): print(``): print(`The number of Motzkin paths is famously`, M[n]): print(``): for i from 1 to k do print(``): print(`-----------------------------------------`): print(``): print(`The sum of the`, i, `-th power of the areas of all Motzkin paths of length n is`): print(``): print(subs({Mn=M[n],Mn1=M[n+1]},gu[i])): print(``): print(`and in Maple notation`): print(``): lprint(subs({Mn=M[n],Mn1=M[n+1]},gu[i])): print(``): print(`For the sake of the OEIS, the first 30 terms are`): print(``): print([seq(eval(subs({n=j,Mn=M0[j],Mn1=M0[j+1]},gu[i])),j=1..30)]): print(``): od: print(``): print(`-----------------------------------------------`): lu:=LimMomMotzkin(k): print(`The average of the area is asympotic to`, lu[1]*n^(3/2) ): print(``): print(`The variance of the area is asympotic to`, lu[2]*n^3 ): print(``): if k>=3 then print(`The limiting skewness is`, lu[3]): print(``): print(`and in Maple notation`): print(``): lprint(lu[3]): print(``): fi: if k>=4 then print(`The limiting kurtosisis`, lu[4]): print(`and in Maple notation`): print(``): lprint(lu[4]): print(``): fi: print(`The limiting scaled moments up to the`, k, `-th is`): print(``): print([op(3..k,lu)]): print(``): print(`and in Maple notation`): print(``): lprint([op(3..k,lu)]): print(``): print(`and in decimals`): print(``): lprint( evalf([op(3..k,lu)])): print(``): print(``): ku:=EBkSeq(k): print(``): if [seq(simplify(ku[i]-lu[i]),i=3..k)]<>[0$(k-2)] then print(`unfortunately the limiting scaled moments do not match with those of the area under Brownian excrusion`): print([seq(simplify(ku[i]-lu[i]),i=3..k)]<>[0$(k-2)]): else print(`Note that the limits of the scaled moments up to the`, k, `-th match those of the area under Brownian excursion`): fi: print(``): print(`----------------------------------------------`): print(``): print(`This took`, time()-t0, `moments `): end: