Help:=proc(): print(` SAW(n), IsBad(w1) , DrawWalk(w), RSAW(n) `): end: #2^n<=|SAW(n)|<=4*3^(n-1) #mu:=limit s(n)^(1/n) #2<=mu<=3 #s(n) is sympt. to mu^n*n^theta (theta=11/32) SAW:=proc(n) local Sp,w1,S,w: option remember: if n=0 then RETURN({[]}): fi: Sp:=SAW(n-1): S:={}: for w in Sp do w1:=[op(w),1]: if not IsBad(w1) then S:=S union {w1}: fi: w1:=[op(w),-1]: if not IsBad(w1) then S:=S union {w1}: fi: w1:=[op(w),2]: if not IsBad(w1) then S:=S union {w1}: fi: w1:=[op(w),-2]: if not IsBad(w1) then S:=S union {w1}: fi: od: S: end: IsBad:=proc(w1) local j,x,w2,michael: for j from nops(w1)-1 by -1 to 1 do w2:=[op(j..nops(w1),w1)]: michael:=add(x[w2[i]],i=1..nops(w2)): if coeff(michael,x[1],1)=coeff(michael,x[-1],1) and coeff(michael,x[2],1)=coeff(michael,x[-2],1) then RETURN(true): fi: od: false: end: L:= [4, 12, 36, 100, 284, 780, 2172, 5916, 16268, 44100, 120292, 324932, 881500, 2374444, 6416596, 17245332, 46466676, 124658732, 335116620, 897697164, 2408806028, 6444560484, 17266613812, 46146397316, 123481354908, 329712786220, 881317491628, 2351378582244, 6279396229332, 16741957935348, 44673816630956, 119034997913020, 317406598267076, 845279074648708, 2252534077759844, 5995740499124412, 15968852281708724, 42486750758210044, 113101676587853932, 300798249248474268, 800381032599158340, 2127870238872271828, 5659667057165209612, 15041631638016155884, 39992704986620915140, 106255762193816523332, 282417882500511560972, 750139547395987948108, 1993185460468062845836, 5292794668724837206644, 14059415980606050644844, 37325046962536847970116, 99121668912462180162908, 263090298246050489804708, 698501700277581954674604, 1853589151789474253830500, 4920146075313000860596140, 13053884641516572778155044, 34642792634590824499672196, 91895836025056214634047716, 243828023293849420839513468, 646684752476890688940276172, 1715538780705298093042635884, 4549252727304405545665901684, 12066271136346725726547810652, 31992427160420423715150496804, 84841788997462209800131419244, 224916973773967421352838735684, 596373847126147985434982575724, 1580784678250571882017480243636]: #DrawWalk(w): draws the SAW w DrawWalk:=proc(w) local L,i,pt: L:=[[0,0]]: pt:=[0,0]: for i from 1 to nops(w) do if w[i]=-1 then pt:=pt+[-1,0]: elif w[i]=1 then pt:=pt+[1,0]: elif w[i]=2 then pt:=pt+[0,1]: elif w[i]=-2 then pt:=pt+[0,-1]: fi: L:=[op(L),pt]: od: plot(L,axes=none): end: #RSAW(n): a (not-guaranteed-to-be-uniform) random walk on n steps #in the 2D lattice RSAW:=proc(n) local L,pt,N,i: L:=[[0,0]]: pt:=[0,0]: for i from 1 to n do N:={pt+[1,0],pt+[-1,0],pt+[0,1],pt+[0,-1]} minus {op(L)} : if N={} then RETURN(FAIL,L): fi: pt:=N[rand(1..nops(N))()]: L:=[op(L),pt]: od: L: end: