with(combinat):
 
print(` Version of April 16, 1996`):
lprint(``):
print(`This is alice, a short Maple package, written by Doron Zeilberger`):
print(`accompanying his paper  " Dodgson's Determinant-Evaluation Rule`):
print(`proved by Two-Timing Men and Women"`):
lprint(``):
print(`This package, and the paper, are available from`):
print(` http://www.math.temple.edu/~zeilberg .`):
print(`For general help, and a list of the available functions,`):
print(` type "ezra();". For specific help type "ezra(procedure_name)" `):
lprint(``):
 
 
 
ezra:=proc()
if args=NULL then
print(`alice`):
print(`A Maple package with  the bijections given in `):
print(` the paper  " Dodgson's Determinant-Evaluation Rule`):
print(`proved by two-timing men and women"`):
print(`Contains procedures: `):
print(`T,SB,SC,A,B,C,ST,TSB,TSC`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`T` then
print(`The input: a double-matching a=[pi,sigm], that belongs to the set`):
print(`A of the paper,where pi is given in terms`):
print(`of the set of married couples [m,w], where Mr. m is married to`):
print(`Ms. w, and the Men and Women range over {1,2,..,n},`):
print(`and sigm is the corresponding set for the affairs, i.e.`):
print(`the set of [m,w] where Ms. w is the mistress of Mr. m, and`):
print(`where the Men and Women range over {2,3,..,n-1}.`):
lprint(``):
print(`The output: the image under the mapping T, followed by`):
print(`whether it belongs to B or C.`):
lprint(``):
print(`For example: T([{[1,2],[2,3],[3,1]},{[2,2]}]); should return`):
print(`[{[1,2],[2,3]},{[2,2]}],InC`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`SB` then
print(`The input: a double-matching a=[pi,sigm], that belongs to the set`):
print(`B of the paper,where pi is given in terms`):
print(`of the set of married couples [m,w], where Mr. m is married to`):
print(`Ms. w, and the Men and Women range over {1,2,..,n-1},`):
print(`and sigm is the corresponding set for the affairs, i.e.`):
print(`the set of [m,w] where Ms. w is the mistress of Mr. m, and`):
print(`where the Men and Women range over {2,3,..,n}.`):
lprint(``):
print(`The output: the image under the mapping S, followed by`):
print(`whether it belongs to A or C.`):
lprint(``):
print(`For example: SB([{[1,2],[2,1]},{[2,3],[3,2]}]); should return`):
print(`[{[1,2],[2,3]},{[2,1],[3,2]}],InC`):
fi:
 
 
 
if nops([args])=1 and op(1,[args])=`SC` then
print(`The input: a double-matching a=[pi,sigm], that belongs to the set`):
print(`B of the paper,where pi is given in terms`):
print(`of the set of married couples [m,w], where Mr. m is married to`):
print(`Ms. w, and the Men  range over {1,2,..,n-1},`):
print(`and the Women range over {2,3, ... , n},`):
print(`and sigm is the corresponding set for the affairs, i.e.`):
print(`the set of [m,w] where Ms. w is the mistress of Mr. m, and`):
print(`where the Men  range over {2,3,..,n},`):
print(`and the Women  range over {1,2,3,..,n-1}.`):
lprint(``):
print(`The output: the image under the mapping S, followed by`):
print(`whether it belongs to A or B.`):
lprint(``):
print(`For example: SC([{[1,2],[2,3]},{[2,1],[3,2]}]); should return`):
print(`  [{[1,2],[2,1]},{[2,3],[3,2]}],InB`):
fi:
 
 
 
if nops([args])=1 and op(1,[args])=`A` then
print(`A(n) constructs the set of double matchings A(n)`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`B` then
print(`B(n) constructs the set of double matchings B(n)`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`C` then
print(`C(n) constructs the set of double matchings C(n)`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`ST` then
print(`ST(n):verifies that for every single member a of A(n) `):
print(`S( T(a))=a , as it should if S is indeed the inverse of T.`):
print(`Also checks that sign(T(a))=sign(a).`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`TSB` then
print(`TSB(n):verifies that for every single member a of B(n)`):
print(`T( SB(a))=a , if SB (a) belongs to A, and SC(SB(a))=a`):
print(`if SB(a) belongs to C`):
print(`Also checks that sign(SB(a))=sign(a), if a is a good double-matching`):
print(` and sign(SB(a))=-sign(a), if a is a bad guy.`): 
fi:
 
 
 
if nops([args])=1 and op(1,[args])=`TSC` then
print(`TSB(n):verifies that for every single member a of C(n)`):
print(`T( SC(a))=a , if SC (a) belongs to A, and SB(SC(a))=a`):
print(`if SC(a) belongs to B`):
print(`Also checks that sign(SC(a))=sign(a), if a is good, and`):
print(` sign(SC(a))=-sign(a), if a is bad`):
fi:
 
 
end:
 
 
findfemalemate:=proc(pi,husb)
local gu,i:
 
for i from 1 to nops(pi) do
 gu:=op(i,pi):
 if op(1,gu)=husb then
   RETURN(op(2,gu)):
 fi:
od:
 
0:
end:
 
 
findmalemate:=proc(pi,wife)
local gu,i:
 
for i from 1 to nops(pi) do
 gu:=op(i,pi):
 if op(2,gu)=wife then
   RETURN(op(1,gu)):
 fi:
od:
 
0:
end:
 
 
T:=proc(a)
local pi,sigm,chainmar,chainaff,n,currlover,curr,currold:
pi:=op(1,a):
sigm:=op(2,a):
n:=nops(pi):
 
curr:=findfemalemate(pi,n):
chainmar:={[n,curr]}:
chainaff:={}:
 
while curr<>n and curr<>1 do
 currold:=curr:
 currlover:=findmalemate(sigm,curr):
 curr:=findfemalemate(pi,currlover):
 chainaff:=chainaff union {[currlover,currold]}:
 chainmar:=chainmar union {[currlover,curr]}:
od:
 
pi:=(pi minus chainmar) union chainaff:
 
sigm:=(sigm minus chainaff) union chainmar:
 
if curr=n then
RETURN([pi,sigm],InB):
else
RETURN([pi,sigm],InC):
fi:
end:
 
 
SC:=proc(a)
local pi,sigm,chainmar,chainaff,n,curr,curr1,i1:
pi:=op(1,a):
sigm:=op(2,a):
n:=nops(pi)+1:
 
curr:=findmalemate(sigm,1):
chainaff:={[curr,1]}:
 
if curr=n then
 RETURN([pi union chainaff,sigm minus chainaff],InA):
fi:
 
curr1:=findfemalemate(pi,curr):
 
chainmar:={[curr,curr1]}:
 
if curr1=n then
     RETURN([(pi union chainaff) minus chainmar,(sigm minus chainaff) union
chainmar],InB):
fi:
 
 
for i1 from 1 to n+3 do
 
curr:=findmalemate(sigm,curr1):
 chainaff:=chainaff union {[curr,curr1]}:
 if curr=n then
     RETURN([(pi union chainaff) minus chainmar,(sigm minus chainaff) union
chainmar],InA):
fi:
 
 
curr1:=findfemalemate(pi,curr):
 chainmar:=chainmar union {[curr,curr1]}:
 if curr1=n then
     RETURN([(pi union chainaff) minus chainmar,(sigm minus chainaff) union
chainmar],InB):
fi:
 
od:
 
 
end:
 
 
 
 
SB:=proc(a)
local pi,sigm,chainmar,chainaff,n,curr,curr1,i1:
pi:=op(1,a):
sigm:=op(2,a):
n:=nops(pi)+1:
 
curr:=findmalemate(sigm,n):
chainaff:={[curr,n]}:
 
if curr=n then
 RETURN([pi union chainaff,sigm minus chainaff],InA):
fi:
 
curr1:=findfemalemate(pi,curr):
 
chainmar:={[curr,curr1]}:
 
if curr1=1 then
     RETURN([(pi union chainaff) minus chainmar,(sigm minus chainaff) union
chainmar],InC ):
fi:
 
 
for i1 from 1 to n+3 do
 
curr:=findmalemate(sigm,curr1):
 chainaff:=chainaff union {[curr,curr1]}:
 if curr=n then
     RETURN([(pi union chainaff) minus chainmar,(sigm minus chainaff) union
chainmar],InA):
fi:
 
 
curr1:=findfemalemate(pi,curr):
 chainmar:=chainmar union {[curr,curr1]}:
 if curr1=1 then
     RETURN([(pi union chainaff) minus chainmar,(sigm minus chainaff) union
chainmar],InC):
fi:
 
od:
 
 
end:
 
 
 
#A(n) constructs the set of double-matchings A(n)
A:=proc(n)
local lu,perm,gu1,gu2,gu,i,j,mu1,mu2:
 
gu1:=permute(n):
 
mu1:={}:
 
for i from 1 to nops(gu1) do
 perm:=op(i,gu1):
 lu:={}:
 for j from 1 to n do
  lu:=lu union {[j,op(j,perm)]}:
 od:
 mu1:=mu1 union {lu}:
od:
 
gu2:=permute([seq(i,i=2..n-1)]):
 
mu2:={}:
 
for i from 1 to nops(gu2) do
 perm:=op(i,gu2):
 lu:={}:
 for j from 1 to n-2 do
  lu:=lu union {[j+1,op(j,perm)]}:
 od:
 mu2:=mu2 union {lu}:
od:
 
gu:={}:
 
for i from 1 to nops(mu1) do
 for j from 1 to nops(mu2) do
  gu:=gu union {[op(i,mu1),op(j,mu2)]}:
od:
od:
gu:
end:
 
 
 
#B(n) constructs the set of double-matchings B(n)
B:=proc(n)
local lu,perm,gu1,gu2,gu,i,j,mu1,mu2:
 
gu1:=permute(n-1):
 
mu1:={}:
 
for i from 1 to nops(gu1) do
 perm:=op(i,gu1):
 lu:={}:
 for j from 1 to n-1 do
  lu:=lu union {[j,op(j,perm)]}:
 od:
 mu1:=mu1 union {lu}:
od:
 
gu2:=permute([seq(i,i=2..n)]):
 
mu2:={}:
 
for i from 1 to nops(gu2) do
 perm:=op(i,gu2):
 lu:={}:
 for j from 1 to n-1 do
  lu:=lu union {[j+1,op(j,perm)]}:
 od:
 mu2:=mu2 union {lu}:
od:
 
gu:={}:
 
for i from 1 to nops(mu1) do
 for j from 1 to nops(mu2) do
  gu:=gu union {[op(i,mu1),op(j,mu2)]}:
od:
od:
gu:
end:
 
 
 
 
#C(n) constructs the set of double-matchings C(n)
C:=proc(n)
local lu,perm,gu1,gu2,gu,i,j,mu1,mu2:
 
gu1:=permute([seq(i,i=2..n)]):
 
mu1:={}:
 
for i from 1 to nops(gu1) do
 perm:=op(i,gu1):
 lu:={}:
 for j from 1 to n-1 do
  lu:=lu union {[j,op(j,perm)]}:
 od:
 mu1:=mu1 union {lu}:
od:
 
gu2:=permute([seq(i,i=1..n-1)]):
 
mu2:={}:
 
for i from 1 to nops(gu2) do
 perm:=op(i,gu2):
 lu:={}:
 for j from 1 to n-1 do
  lu:=lu union {[j+1,op(j,perm)]}:
 od:
 mu2:=mu2 union {lu}:
od:
 
gu:={}:
 
for i from 1 to nops(mu1) do
 for j from 1 to nops(mu2) do
  gu:=gu union {[op(i,mu1),op(j,mu2)]}:
od:
od:
gu:
end:
 
 
 
ST:=proc(n)
local gu,i,matc,imag,imagimag,ratsign:
 
gu:=A(n):
 
for i from 1 to nops(gu) do
matc:=op(i,gu):
imag:=T(matc):
 
if imag[2]=InB then
  imagimag:=SB(imag[1])[1]:
  ratsign:=signA(matc)/signB(imag[1]):
else
  imagimag:=SC(imag[1])[1]:
   ratsign:=signA(matc)/signC(imag[1]):
fi:
 
print(`When the double matching is`,matc):
print(`and you apply ST, you get`, imagimag):
 if matc=imagimag then
 print(`Indeed they are equal to each other`):
 else
 print(`They are not equal to each other and the paper is wrong`):
 fi:
print(`The ratio of the sign of the original to that of its image is`,ratsign)
:
 
od:
 
end:
 
 
 
TSB:=proc(n)
local gu,i,matc,imag,imagimag,ratsign:
 
gu:=B(n):
 
for i from 1 to nops(gu) do
matc:=op(i,gu):
imag:=SB(matc):
 
if imag[2]=InC then
  imagimag:=SC(imag[1])[1]:
   ratsign:=signB(matc)/signC(imag[1]):
else
  imagimag:=T(imag[1])[1]:
   ratsign:=signB(matc)/signA(imag[1]):
fi:
 
print(`When the double matching is`,matc):
 
if imag[2]=InC then
 print(`This a bad double-matching`):
print(`The ratio of the sign of the original to that of its image is`,ratsign)
:
 print(`When you apply SCSB, you get`, imagimag):
fi:
 
if imag[2]=InA then
 print(matc,`is a good double-matching`):
print(`The ratio of the sign of the original to that of its image is`,ratsign)
:
 print(`When you apply TSB, you get`, imagimag):
fi:
 
 if matc=imagimag then
 print(`Indeed they are equal to each other`):
 else
 print(`They are not equal to each other and the paper is wrong`):
 fi:
 
 
od:
 
end:
 
 
 
 
TSC:=proc(n)
local gu,i,matc,imag,imagimag,ratsign:
 
gu:=C(n):
 
for i from 1 to nops(gu) do
matc:=op(i,gu):
imag:=SC(matc):
 
if imag[2]=InB then
  imagimag:=SB(imag[1])[1]:
   ratsign:=signC(matc)/signB(imag[1]):
else
  imagimag:=T(imag[1])[1]:
   ratsign:=signC(matc)/signA(imag[1]):
fi:
 
print(`When the double matching is`,matc):
 
if imag[2]=InB then
 print(`This is a bad double-matching`):
print(`The ratio of the sign of the original to that of its image is`,ratsign)
:
 print(`When you apply SBSC, you get`, imagimag):
fi:
 
if imag[2]=InA then
 print(matc,`is a good double-matching`):
print(`The ratio of the sign of the original to that of its image is`,ratsign)
:
 print(`When you apply TSC, you get`, imagimag):
fi:
 
 if matc=imagimag then
 print(`Indeed they are equal to each other`):
 else
 print(`They are not equal to each other and the paper is wrong`):
 fi:
 
 
od:
 
 
end:
 
 
#signA(a) finds the sign of the double matching a=[pi,sigm] \n A
 
signA:=proc(a)
local gu,n,pi,sigm,i,j:
pi:=op(1,a):
sigm:=op(2,a):
n:=nops(pi):
 
gu:=1:
 
for i from 1 to n do
 for j from i+1 to n do
  if findfemalemate(pi,i)>findfemalemate(pi,j) then
   gu:=(-1)*gu:
  fi:
 od:
od:
 
 
for i from 2 to n-1 do
 for j from i+1 to n-1 do
  if findfemalemate(sigm,i)>findfemalemate(sigm,j) then
   gu:=(-1)*gu:
  fi:
 od:
od:
 
gu:
end:
 
 
 
#signB(a) finds the sign of the double matching a=[pi,sigm] \n B
 
signB:=proc(a)
local gu,n,pi,sigm,i,j:
pi:=op(1,a):
sigm:=op(2,a):
n:=nops(pi)+1:
 
gu:=1:
 
for i from 1 to n-1 do
 for j from i+1 to n-1 do
  if findfemalemate(pi,i)>findfemalemate(pi,j) then
   gu:=(-1)*gu:
  fi:
 od:
od:
 
 
for i from 2 to n do
 for j from i+1 to n do
  if findfemalemate(sigm,i)>findfemalemate(sigm,j) then
   gu:=(-1)*gu:
  fi:
 od:
od:
 
gu:
end:
 
 
 
#signC(a) finds the sign of the double matching a=[pi,sigm] \n C
 
signC:=proc(a)
local gu,n,pi,sigm,i,j:
pi:=op(1,a):
sigm:=op(2,a):
n:=nops(pi)+1:
 
gu:=-1:
 
for i from 1 to n-1 do
 for j from i+1 to n-1 do
  if findfemalemate(pi,i)>findfemalemate(pi,j) then
   gu:=(-1)*gu:
  fi:
 od:
od:
 
 
for i from 2 to n do
 for j from i+1 to n do
  if findfemalemate(sigm,i)>findfemalemate(sigm,j) then
   gu:=(-1)*gu:
  fi:
 od:
od:
 
gu:
end: