#Ross Berkowitz HW3.txt # Posting Permission Granted Help:=proc(): print(`inv1(p), gf(n,q), PerFast(M)`): end: ## 2 # I required Digits:=77: to get results accurate up to the first four digits. ### 3 #inv1(p) computes the number of inversions in a given permutation inv1:=proc(p) local i,j,n,s: s:=0: n:=nops(p): for i from 1 to n do for j from i+1 to n do if p[i] > p[j] then s:=s+1: fi: od: od: s: end: ### 4 #gf(n,q) returns the generating function of the number of permutations of # [n] with \$k\$ inversions. gf:=proc(n,q) local i,P,p,f: with(combinat): P:=permute(n): f:=0: for p in P do f:=f+q^(inv1(p)): od: f: end: #### 5 #PerFast(M) Implements Ryser's Algorithm to compute permanent much more quickly. PerFast:=proc(M) local n,P,S,i,j: with(combinat): n:=nops(M): P:=powerset(n): (-1)^n*add( (-1)^(nops(S))*mul(add(M[i][j],j in S),i=1..n), S in P): end: ###################### CLASS STUFF ################# #C3.txt:Jan. 30, 2014 Help3:=proc(): print(` Hil(n), Per(M), SD(M) `) : print(`sig1(p) `): end: with(combinat): Hil:=proc(n) local i,j: [ seq( [seq(1/(i+j-1),j=1..n)], i=1..n) ]: end: #Per(M): inputs a square matrix (given as a list of lists) #and outputs the permanent (same as det. but no sign(pi) #in front) Per:=proc(M) local i,j,n,P,p: n:=nops(M): P:=permute(n): add( mul(M[i][p[i]],i=1..n), p in P): end: #SD(M): inputs a square matrix (given as a list of lists) #and outputs the determinant using the definition SD:=proc(M) local i,j,n,P,p: n:=nops(M): P:=permute(n): add( sig1(p)* mul(M[i][p[i]],i=1..n), p in P): end: # sig1:=proc(p) local i,j,n,s: s:=1: n:=nops(p): for i from 1 to n do for j from i+1 to n do if p[i] > p[j] then s:=-s: fi: od: od: s: end: #AliceD(M): inputs a square matrix and outputs #the determinant using Dodgson (aka Lewis Carroll) #condensation method #det(M)=((det(UpLeft)*det(BotRight)-det(UpRright)*det(BotLeft)) #/det(Middle) AliceD:=proc(M) local n,UL,BR,UR,BL,MI, i,j: option remember: n:=nops(M): if n=0 then RETURN(1): fi: if n=1 then RETURN(M[1][1]): fi: UL:=[seq( [op(1..n-1,M[i])], i=1..n-1)]: UR:=[seq( [op(2..n,M[i])], i=1..n-1)]: BL:=[seq( [op(1..n-1,M[i])], i=2..n)]: BR:=[seq( [op(2..n,M[i])], i=2..n)]: MI:=[seq( [op(2..n-1,M[i])], i=2..n-1)]: if AliceD(MI)=0 then FAIL: else normal( (AliceD(UL)*AliceD(BR)-AliceD(UR)*AliceD(BL))/AliceD(MI)): fi: end: