## Kristen Lew, Homework 4 ## Exp Math Spring 2012 # Use whatever you like Help:=proc(): #print(` G2(a,b), CheckG(a,b), Di(L), NGF(L,x), G(a,b), Gk(k,a,b), Gk1(a,b), CheckGk1(), Gk2(a,b), CheckGk2(), Gk1k2(k1,k2,a,b), F3(a,b,c) `): print(` Old processes: Di(L), NGF(L,x), G(a,b)`): print(` New processes: Gk(k,a,b), Gk1k2(k1,k2,a,b), F3(a,b,c), G3(a,b,c)`): print(` Checking processes: G2(a,b), CheckG(), Gk1(a,b), CheckGk1(), Gk2(a,b), CheckGk2()`): end: ### Problem 2: ## Conjecture that G(a,b) = (a+b)…(a+2)(a-(b-1))/(b!). ## Using G2, we can see G(0,0)=1, G(0,1)=0, G(1,0)=1 and G(a,a+1)=0. ## So the base cases hold. ## Using CheckG, we can see that the conjecture holds true. G2:=proc(a,b) local k: (product(a+b-k, k=0..b-2))*(a-(b-1))/b!: end: CheckG:=proc(): if simplify(G2(a,b)-(G2(a-1,b)+G2(a,b-1))=0) then if simplify(G2(a,0) = 1) then if simplify(G2(a,a)-G2(a,a-1)=0) then RETURN(true): else RETURN(false): fi: else RETURN(false): fi: else RETURN(false): fi: end: ## Di(L) Di:=proc(L) local i: [seq( L[i+1]-L[i], i=1..nops(L)-1 )]: end: ## NGF(L,x) The unique polynomial P(x) expressed in terms # of binomial(x,k) such that P(i)=L[i+1] for i from 0 to nops(L)-1 NGF:=proc(L,x) local i,L1,P: L1:=L: P:=0: for i from 1 to nops(L) do P:= P + L1[1]*binomial(x,i-1): L1:=Di(L1): if convert(L1,set)={0} then RETURN(factor(expand( P))): fi: od: factor(expand(P )): end: ## G(a,b): the number of walks from [0,0] to [a,b] using positive # unit steps ([1,0],[0,1]), always staying in the safe region a>=b G:=proc(a,b) option remember: if b=0 then 1: elif b>a then 0: else G(a-1,b)+G(a,b-1): fi: end: ### Problem 3 ## Gk(k,a,b): the number of walks from [0,0] to [a,b] using positive # unit steps ([1,0],[0,1]), always staying in the safe region a+k >= b Gk:=proc(k,a,b) option remember: if b>a+k then 0: elif b=0 then 1: elif a=0 then 1: else Gk(k,a-1,b)+Gk(k,a,b-1): fi: end: ## Conjecture that Gk(1,a,b) = (a+b+1)…(a+3)(a-b+2) / b! ## Conjecture that Gk(2,a,b) = (a^2+(b+3)*a+b^2+2)(a+b)…(a+4)(a-b+3) / b! ## Using Gk1 and Gk2 (and simplify), we can see that ## Gk1(0,0)=1, Gk1(0,1)=1, Gk1(0,2)=0, Gk1(0,a)=1 ## Gk1(0,0)=1, Gk1(0,1)=1, Gk1(0,2)=1, Gk2(0,3)=0, Gk1(0,a)=1. ## Using CheckGk1 and CheckGk2, we can see that the conjecture holds true. Gk1:=proc(a,b): (product(a+b+1-i, i=0..b-2))*(a-b+2)/b!: end: CheckGk1:=proc(): if simplify(Gk1(a,b)-(Gk1(a-1,b)+Gk1(a,b-1))=0) then if simplify(Gk1(a,a+1) - Gk1(a,a) = 0) then if simplify(Gk1(a,0)-1 = 0) then RETURN(true): else RETURN(false): fi: else RETURN(false): fi: else RETURN(false): fi: end: Gk2:=proc(a,b): (product(a+b+(-i),i=0..(b-4))*(a-b+3)*(a^2+(b+3)*a+b^2+2))/b!: end: CheckGk2:=proc(): if simplify(Gk2(a,b)-(Gk2(a-1,b)+Gk2(a,b-1))=0) then if simplify(Gk2(a,a+1) - Gk2(a,a+2) = 0) then if simplify(Gk2(a,0)-1 = 0) then RETURN(true): else RETURN(false): fi: else RETURN(false): fi: else RETURN(false): fi: end: ### Problem 4 ## Gk1k2(k1,k2,a,b) # Gk1k2(k,k,a,a) for k=1 is in Sloane A059268, but k=2,3 are not listed in Sloane. Gk1k2:=proc(k1,k2,a,b) option remember: if b<=k2 and a=0 then 1: elif b=0 and a<=k1 then 1: elif b-k1>a then 0: elif b+k20 ## Gk1k2(3,3,a,a) = a such that ## a(0) = 1, a(1) = 2, a(n) = 4a(n-1) - 2a(n-2), n >= 2 [oeis.org] ### Problem 5 # F3(a,b,c) compute the number of ways of walking in 3d Manhattan using # unit steps [1,0,0], [0,1,0], [0,0,1]. F3:=proc(a,b,c) option remember: if {a,b,c}={0} or {a,b,c}={0,1} then 1: else F3(a-1,b,c)+F3(a,b-1,c)+F3(a,b,c-1): fi: end: ### Problem 6 # G3(a,b,c) compute number of ways of walking in 3d Manhattan always staying # in the region a>= b >= c G3:=proc(a,b,c) option remember: if {a,b,c}={0} or {a,b,c}={0,1} then 1: elif a