print( `This is ROBBINS, Version of April 28, 1995`): print(``): print(`This is ROBBINS,a Maple package companion, written by Doron Zeilberger`): print(`To accompany his proof of the alternating sign matrix conjecture`): print(`Given in his paper "Proof of the Alternating Sign Matrix Conj."`): print(`That appeared in the Elect. J. of Combinatorics v.3(2), R13 (1996)`): print(`(in the special issue to honor Dominque Foata).`): print(`Package, and paper are in http:/www.math.temple.edu/~zeilberg.`): print(`Many Thanks to Paul Zimmermann for suggesting some of the`): print(`new features in this version. In particular, try out`): print(`ASM(k), and GOG(k,n) and MAGOG(k,n).`): print(``): print(`For genral help, and a list of the available functions`): print(` type ezra();, for specific help type ezra(procedure);`): #ROBBINS: A PACKAGE FOR EMPRIRICAL CORROBARATION OF ALL THE #NON-TRIVIAL STATEMENTS IN D.ZEILBERGER'S PROOF OF THE ALTERNATING SIGN #MATRIX THEOREM. THE PROCEDURE NAMES CORRESPOND TO THE SUBLEMMAS #Written by D. Zeilberger ezra:=proc() if args=NULL then print(`Version of April 28, 1995`): print(`ROBBINS:A PACKAGE FOR THE EMPRIRICAL VERIFICATION OF ALL `): print(`THE NON-TRIVIAL STATEMENTS IN DORON ZEILBERGER'S PROOF OF `): print(`THE MILLS-ROBBINS-RUMSERY ALTERNATING SIGN MATRIX CONJECTURE.`): print(`Contains the following procedures`): print(` 'ASM','GOG','MAGOG','LOMA','LOGOG','ELOGOG','Tkn','GOGTOASM' `): print( ` 'B', 'b','bfast','Bext','S1111' ,'S1111all','X', 'S1113','Delta' `): print(` 'S1112','S11121','S11122','C', 'S111','S11','S112' `): print(`'antisymmetrizerS_k'`): print(` 'CT' ,'Res','M','Mt' ,'m','S12','S121','S1211','S1211all'`): print(`'S1','S12121','S12121all','S12122','S12123','S12124','S12125' `): print(` ,'H', 'Y', 'S1213', 'antisymmetrizerWB_k', 'Phi' `): print(` 'IterRes','fnk','S13spec','S13','Fnk','S14spec','S14','S15' `): print(`'S151', 'S1511','S1512','S152','S1521','S1522','S15221'`): print(`'S1523','S1524','S131','S1311', 'S13111', 'S1312', 'S1313', 'S1314' `): print(`'S141','S1411', 'S14111', 'S1412', 'S1413', 'S1414','S1415','S1416' `): print(`'S1313S1314','S1413to6'`): print(`For help with a specific prodecure, type ezra(procedure_name)`): fi: if nops([args])=1 and op(1,[args])=`ASM` then print(`ASM(k): lists all the ASMs of size k`): fi: if nops([args])=1 and op(1,[args])=`GOG` then print(`GOG(k,n): lists all the n by k Gog Trapezoids`): fi: if nops([args])=1 and op(1,[args])=`MAGOG` then print(`MAGOG(k,n): lists all the n by k Gog Trapezoids`): fi: if nops([args])=1 and op(1,[args])=`GOGTOASM` then print(`GOGTOASM(mt): converts a GOG triangle mt, given as a list of`): print(`of lists, to an ASM`): fi: if nops([args])=1 and op(1,[args])=`LOMA` then print(`LOMA(k,n): Gives the domain Land_Of_Magog_k for`): print(`the given n`): fi: if nops([args])=1 and op(1,[args])=`LOGOG` then print(`LOGOG(k,n): Gives the domain Land_Of_Gog_k for the given n`): fi: if nops([args])=1 and op(1,[args])=`ELOGOG` then print(`ELOGOG(k,n): Gives the extended Land_Of_Gog_k for the given n`): fi: if nops([args])=1 and op(1,[args])=`Tkn` then print(`Tkn(k,n,a): Gives the set T_k(n;a_1, .., a_k) defined in the middle`): print(`of p.25, in the proof of 1.2.1.1`): fi: if nops([args])=1 and op(1,[args])=`B` then print(`B(k,n,a): computes nu. of n by k Magog-trapezoids, with n>=k>=1`): print(`whose rightmost diagonal is prescribed by the list`): print( `a=[a_1, a_2 , ..a_k]. The domain must be the`): print(` Land_Of_Magog_k, defined in p. x, i.e. n>=a_1 >= ... `): print(`>=1, and a_i<=n-i+1, for i=1..k`): print(`It uses the recurrence (Ekhad) in the act I "Counting Magog"`): print(`that follows straight from the combinatorial definition of B_k`): fi: if nops([args])=1 and op(1,[args])=`C` then print(`C(k,n,a): computes the constant term expressin C_k(n; a_1 ... a_k)`): print(`given in subsublemma 1.1.1 for any input (n; a_1 , ... , a_k) with`): print(`positive integers`): fi: if nops([args])=1 and op(1,[args])=`S1` then print(`S1(k,n): verifies Lemmas 1, for k,n`): fi: if nops([args])=1 and op(1,[args])=`Delta` then print(`Delta(k) gives Delta_k defined in (Delta) of act I: Couting Magog`): fi: if nops([args])=1 and op(1,[args])=`fnk` then print(`fnk(k,n) gives f_{n,k} defined in sublemma 1.3 of Act III`): fi: if nops([args])=1 and op(1,[args])=`Bext` then print(`Bext(k,n,a): is an extended version of B(k,n,a)`): print(`extended to the domain \overline{Land_Of_Magog}`): print(`Bext(k,n,a) is defined to be B(k,n,a) if a is`): print(`in the original domain, and 0 elsewhere, see act I`): print(`Counting Magog`): fi: if nops([args])=1 and op(1,[args])=`b` then print(`b(k,n):gives the number of nxk Magog-trapezoids, with n>=k>=1`): print(`by summing over all comnceivable B_k(n;a_1, ..., a_k)`): print(`In particular b(k,k) gives the number of k by k Magog triangles`): print(`which are trivially equal to the number of TSSCP in [0,2k]^3`): print(`This gives an empirical verification to Andrews' result of ref.`): print(`[A2], i.e. JCT 66 (1994), 28-39`): fi: if nops([args])=1 and op(1,[args])=`S11` then print(`S11(k,n):empirically verifies sublemma 1.1 for (k,n)`): print(` by computing the constant term expression on the right side`): print(`of (MagogTotal), and comparing it to the left side, b_k(n)`): fi: if nops([args])=1 and op(1,[args])=`bfast` then print(`bfast(k,n):gives the number of nxk Magog-trapezoids, where n>=k>=1`): print(`by summing over all comnceivable X_k(n;a_1, ..., a_k)`): print(`Where X_k is computed by the difference scheme of 1113`): print(`Since we know that X_k=B_k, and it is much faster to compute`): print(`X_k, this gives us a fast way to compute b_k(n)`): print(`In particular b(k,k) gives the number of k by k Magog triangles`): print(`which are trivially equal to the number of TSSCP in [0,2k]^3`): print(`This gives a fast empirical verification to Andrews' result of ref.`): print(`[A2], i.e. JCT 66 (1994), 28-39`): fi: if nops([args])=1 and op(1,[args])=`S1111` then print(`S1111(k,n,a):gives the left side`): print(`and right sides of (P \Delta E (B_k)) in the statement of`): print(` (sub)^3lemma 1.1.1.1, in act I "Counting Magog" `): print(` which better be equal! (or your money back!) `): fi: if nops([args])=1 and op(1,[args])=`S1111all` then print(`S1111all(k,n):gives the left side`): print(`and right sides of (P \Delta E (B_k)) in the statement of`): print(` (sub)^3lemma 1.1.1.1, in act I "Counting Magog", p. x`): print(` for every applicable a=(a_1 ,..., a_k) . They should be equal`): fi: if nops([args])=1 and op(1,[args])=`S1112` then print(`S1112(k):empirically verifies subsublemma 1.1.1.2 for k`): print(` by verifying the first and second part of (C3) i.e. that when`): print(`k>=a_k>=a_{k-1}>= ... >=a_1>=2 it is zero, while when`): print(`a_k=1 it it coincides with C_{k-1}(k;a_1 , ..., a_{k-1})`): fi: if nops([args])=1 and op(1,[args])=`S11121` then print(`S11121(k,a):empirically verifies subsublemma 1.1.1.2.1 for k`): print(`and a=[a_1, ... , a_k], with `): print(`k>=a_k>=a_{k-1}>= ... >=a_1>=2 `): fi: if nops([args])=1 and op(1,[args])=`S11122` then print(`S11121(k,a):empirically verifies subsublemma 1.1.1.2.2 for k`): print(`and a=[a_1, ... , a_k], with `): print(`k>=a_k>=a_{k-1}>= ... >=a_1>=2 `): fi: if nops([args])=1 and op(1,[args])=`X` then print(`X(k,n,a): computes X(k,n,a), where (n;a_1 , ... , a_k)`): print(`is in the extended Land of Magog, according to the finite`): print(` difference scheme of subsubsublemma 1.1.1.3, (P \Delta E)(X_k)`): fi: if nops([args])=1 and op(1,[args])=`S1113` then print(`S1113(k,n) verifies subsubsublemma 1.1.1.3 by displaying all the`): print(`values of X(k,n,a) for all relevant a`): print(`The success of the program verifies that X is indeed well defined`): fi: if nops([args])=1 and op(1,[args])=`S111` then print(`S111(k,n) verifies subsublemma 1.1.1 by displaying all the`): print(`values of B(k,n,a) and C(k,n,a) for all relevant a`): print(`The sublemma predicts that they are always equal`): fi: if nops([args])=1 and op(1,[args])=`S112` then print(`S112(k,n) verifies subsublemma 1.1.2 by computing`): print(`the left and right sides of (Geroge) for the inputted k and n`): fi: if nops([args])=1 and op(1,[args])=`S113` then print(`S113(k) verifies subsublemma 1.1.3 by computing`): print(`the left hand side of (Issai) for the inputted k`): fi: if nops([args])=1 and op(1,[args])=`antisymmetrizerS_k` then print(`antisymmetrizerS_k(f,k) finds the anti-symmetrizer w.r.t.`): print(`the symmetric group S_k, of a rational`): print(`function f(x[1], ... , x[k])`): fi: if nops([args])=1 and op(1,[args])=`antisymmetrizerWB_k` then print(`antisymmetrizerWB_k(f,k) finds the anti-symmetrizer w.r.t.`): print(`the group of signed permutations W(B_k), of a rational`): print(`function f(x[1], ... , x[k])`): fi: if nops([args])=1 and op(1,[args])=`Phi` then print(`Phi(k) gives Phi_k defined in (Phi) in the statement`): print(` of sublemma 1.2 of act II: Couting Gog`): fi: if nops([args])=1 and op(1,[args])=`H` then print(`H(k,n,a): computes the constant term expressin H_k(n; a_1 ... a_k)`): print(`given in subsublemma 1.1.1 for any input (n; a_1 , ... , a_k) with`): print(`positive integers`): fi: if nops([args])=1 and op(1,[args])=`m` then print(`m(k,n):gives the numbe of n by k Gog-trapezoids, where n>=k>=1`): print(`by summing over all comnceivable M_k(n;a_1, ..., a_k)`): print(`In particular m(k,k) gives the number of k by k Gog triangles`): print(`which are trivially equal to the number of nxn ASMs`): print(`This gives an empirical verification to the Alternating Sign`): print(`Matrix conjecture proved in the paper`): fi: if nops([args])=1 and op(1,[args])=`S12` then print(`S12(k,n):empirically verifies sublemma 1.2 for (k,n)`): print(` by computing the constant term expression on the right side`): print(`of (GogTotal), and comparing it to the left side, m_k(n)`): fi: if nops([args])=1 and op(1,[args])=`S121` then print(`S121(k,n) verifies subsublemma 1.2.1 by displaying all the`): print(`values of \tilde M(k,n,a) and H(k,n,a) for all relevant a`): print(`The sublemma predicts that they are always equal`): fi: if nops([args])=1 and op(1,[args])=`S1212` then print(`S1212(k,n):empirically verifies subsublemma 1.2.1.2 for (k,n,a)`): fi: if nops([args])=1 and op(1,[args])=`S12121` then print(`S12121(k,n,a):empirically verifies subsublemma 1.2.1.2.1 for k,n and`): print(` a by verifying that H_k satisfies (P\DeltaE(H_k))`): print(` in the statement of 1.2.1.2`): fi: if nops([args])=1 and op(1,[args])=`S12121all` then print(`S12121(k,n):empirically verifies subsublemma 1.2.1.2.1 for k=k>=1, and the `): print(`signed permutation g=pi,eps`): fi: if nops([args])=1 and op(1,[args])=`S13` then print(`S13(k,n) verifies sublemma 1.3 for n>=k>=1, all the k!*2^k `): print(`signed permutation g=pi,eps`): fi: if nops([args])=1 and op(1,[args])=`S131` then print(`S131(k,n) verifies subsublemma 1.3.1 for n>=k>=1, all the k!*2^k `): print(`signed permutation g=pi,eps`): fi: if nops([args])=1 and op(1,[args])=`S1311` then print(`S1311(k,R) verifies subsubsublemma 1.3.1.1 for k, and 1<=R<=k`): fi: if nops([args])=1 and op(1,[args])=`S1312` then print(`S1312(k,n,eps,R) verifies subsubsublemma 1.3.1.2 for n>=k>=1, a sign-`): print(`assignment eps and 1<=R<=k. i.e. it does (Celia) but with the parts `): print(`marked by ma[i]'s to faciliate verifying 1.3.1.3 and 1.3.1.4`): fi: if nops([args])=1 and op(1,[args])=`S13111` then print(`S13111(k,R,i) verifies subsubsubsublemma 1.3.1.1.1 for k`): print(`R and i s.t. 1<=i,R<=k. i<>R`): fi: if nops([args])=1 and op(1,[args])=`S1313S1314` then print(`S1313S1314(k,n) verifies subsubsublemmas 1.3.1.3 and 1.3.1.4 for k`): print(`and n, where n>=k>=1`): fi: if nops([args])=1 and op(1,[args])=`S1313` then print(`S1313(k,n) verifies subsubsublemmas 1.3.1.3 for k`): print(`and n, where n>=k>=1 by calling in S1313S1314 that does both`): fi: if nops([args])=1 and op(1,[args])=`S1314` then print(`S1314(k,n) verifies subsubsublemmas 1.3.1.4 for k`): print(`and n, for n>=k>=1 by calling in S1313S1314 that does both`): fi: if nops([args])=1 and op(1,[args])=`S141` then print(`S141(k,n) verifies subsublemma 1.4.1 for n>=k>=1, all the k!*2^k `): print(`signed permutation g=pi,eps`): fi: if nops([args])=1 and op(1,[args])=`S1411` then print(`S1411(k,R) verifies subsubsublemma 1.4.1.1 for k, and 1<=R<=k`): fi: if nops([args])=1 and op(1,[args])=`S1412` then print(`S1412(k,n,eps,R) verifies subsubsublemma 1.4.1.2 for n>=k>=1, a sign-`): print(`assignment eps and 1<=R<=k. i.e. it does (Celia) but with the parts `): print(`marked by ma[i]'s to faciliate verifying 1.4.1.[3,4,5,6]`): fi: if nops([args])=1 and op(1,[args])=`S14111` then print(`S14111(k,R,i) verifies subsubsubsublemma 1.4.1.1.1 for k`): print(`R and i s.t. 1<=i,R<=k. i<>R`): fi: if nops([args])=1 and op(1,[args])=`S1413to6` then print(`S1413to6(k,n) verifies subsubsublemmas 1.4.1.3 through 1.3.1.6 for k`): print(`and n`): fi: if nops([args])=1 and op(1,[args])=`S1413` then print(`S1413(k,n) verifies subsubsublemmas 1.4.1.3 for k`): print(`and n, by calling in S1413to6 that does both`): fi: if nops([args])=1 and op(1,[args])=`S1414` then print(`S1414(k,n) verifies subsubsublemmas 1.4.1.4 for k`): print(`and n, by calling in S1413to6 that does both`): fi: if nops([args])=1 and op(1,[args])=`S1415` then print(`S1415(k,n) verifies subsubsublemmas 1.4.1.5 for k`): print(`and n, by calling in S1413to6 that does both`): fi: if nops([args])=1 and op(1,[args])=`S1416` then print(`S1416(k,n) verifies subsubsublemmas 1.4.1.6 for k`): print(`and n, by calling in S1413to6 that does both`): fi: if nops([args])=1 and op(1,[args])=`S14spec` then print(`S14spec(k,n,pi,eps) verifies sublemma 1.4 for n>=k>=1, and the `): print(`signed permutation g=pi,eps`): fi: if nops([args])=1 and op(1,[args])=`S14` then print(`S14(k,n) verifies sublemma 1.4 for n>=k>=1, all the k!*2^k `): print(`signed permutation g=pi,eps`): fi: if nops([args])=1 and op(1,[args])=`Fnk` then print(`Fnk(k,n) gives F_{n,k} defined in sublemma 1.4 of Act IV`): fi: if nops([args])=1 and op(1,[args])=`Omegak` then print(`Omegak(k) gives \Omega_k(x[1], ..., x[k]):=Phi_k(x)/Delta_k(x)`): print(` of sublemma 1.2.1.2.2.1.1 of act II: Couting Gog`): print(` and subsublemma 1.5.2 in act V: Gog=Magog`): fi: if nops([args])=1 and op(1,[args])=`Lk` then print(`Lk(k) gives L_k(x[1], ..., x[k]), the left side of (Gog=Magog)`): print(` in the statement of sublemma 1.5, divided by (-1)^k*Delta(x)^2`): fi: if nops([args])=1 and op(1,[args])=`S15` then print(`S15(k) verifies sublemma 1.5 for k, by subtracting the left side`): print(` of (Gog=Magog) divided by ((-1)^k*Delta_k(x)^2), what is called`): print(`L_k(x) in the proof, from the right side divided by the same`): print(`i.e. Omega_k(x)^2; The sublemma predicts that the difference is 0`): fi: if nops([args])=1 and op(1,[args])=`S151` then print(`S151(k) checks subsublemma 1.5.1 for k, by dividing the left side`): print(` of (1.5.1a) for i=2,by its right side`): print(`as is noted in the proof, (1.5.1b) is equivalent`): print(`Then the procedure does the same for (1.5.1c)`): print(`The subsublemma predicts that both ratios equal 1`): fi: if nops([args])=1 and op(1,[args])=`S152` then print(`S152(k) checks subsublemma 1.5.2 for k, by dividing the left side`): print(` of (1.5.2a) for i=2,by its right side`): print(`as is noted in the proof, (1.5.2b) is equivalent`): print(`Then the procedure does the same for (1.5.2c)`): print(`The subsublemma predicts that both ratios equal 1`): fi: if nops([args])=1 and op(1,[args])=`S1511` then print(`S1511() proves (rigorously!) subsubsublemma 1.5.1.1 by having`): print(`Maple performs the completely routine division of the left side`): print(`of (1.5.1.1) by its right side`): fi: if nops([args])=1 and op(1,[args])=`S1512` then print(`S1512() proves (rigorously!) subsubsublemma 1.5.1.2 by having`): print(`Maple performs the completely routine division of the left side`): print(`of (1.5.1.2) by its right side`): fi: if nops([args])=1 and op(1,[args])=`M` then print(`M(k,n,a): computes nu. of n by k Gog-trapezoids, with n>=k>=1`): print(`whose upper-rightmost diagonal is prescribed by the list`): print( `a=[a_1, a_2 , ..a_k]. More precisely it is the number of`): print(` n by k Gog-trapezoids, d_{i,j} s.t. d_{n-k+i,k-i+1}=a[i]`): print(`(n;a) must be in`): print(` Land_Of_Gog_k, defined in p. x, i.e. n>=a_1 >= ... `): print(`>=1, and a_i>=k-i+1, for i=1..k`): print(`It uses the recurrence (Howard) in act II: "Counting Gog"`): print(`that follows straight from the combinatorial definition of M_k`): fi: if nops([args])=1 and op(1,[args])=`Mt` then print(`Mt(k,n,a): computes tilde M_k, with n>=k>=1, defined in Eq.`): print(`(tilde M_k), right before the statement of subsublemma 1.2.1`): fi: if nops([args])=1 and op(1,[args])=`S1211` then print(`S1211(k,n,a):gives the left side`): print(`and right sides of (P \Delta E (tilde M_k)) in the statement of`): print(` (sub)^3lemma 1.2.1.1, in act II: "Counting Gog", p. x`): print(` They better be equal`): fi: if nops([args])=1 and op(1,[args])=`S1211all` then print(`S1211all(k,n):gives the left side`): print(`and right sides of (P \Delta E (tilde M_k)) in the statement of`): print(` (sub)^3lemma 1.2.1.1, in act II: "Counting Gog", p. x`): print(` for every applicable a=(a_1 ,..., a_k) . They should always equal`): fi: if nops([args])=1 and op(1,[args])=`S1212all` then print(`S1212all(k,n):gives the left side`): print(`and right sides of (P \Delta E (H_k)) in the statement of`): print(` (sub)^3lemma 1.2.1.2, in actII: "Counting Gog", p. x`): print(` for every applicable a=(a_1 ,..., a_k) . They should always equal`): fi: if nops([args])=1 and op(1,[args])=`Y` then print(`Y(k,n,a): computes Y(k,n,a), where (n;a_1 , ... , a_k)`): print(`is in the extended Land of Gog, according to the finite`): print(` difference scheme of subsubsublemma 1.2.1.3, (P \Delta E)(Y_k)`): print(`Valid in the Land_Of_Gog, and the boundary/initial conditions there`): print(`i.e. that it is 0 at points that are not in Land_Of_Gog and`): print(`Y_k(k;k,a_2,..., a_k)=Y_{k-1}(k;a_2, ... , a_k`): fi: if nops([args])=1 and op(1,[args])=`S1213` then print(`S1213(k,n) verifies subsubsublemma 1.2.1.3 by displaying all the`): print(`values of Y(k,n,a) for a s.t. (n;a) is in the extended Land_Of_Gog`): print(`[Warning: The order of the (n;a) displayed is random!]`): print(`except for those with a[1]=n+1 for which we don't bother`): print(`The success of the program verifies that Y is indeed well defined`): fi: if nops([args])=1 and op(1,[args])=`C` then print(`C(k,n,a): computes the constant term expressin C_k(n; a_1 ... a_k)`): print(`given in subsublemma 1.1.1 for any input (n; a_1 , ... , a_k) with`): print(`positive integers`): fi: if nops([args])=1 and op(1,[args])=`CT` then print(`CT(f,x): computes the constant term of the rational function f`): print(`with respect to the variable x`): fi: if nops([args])=1 and op(1,[args])=`Res` then print(`Res(f,x): computes the (formal) residue of the rational function f`): print(`with respect to the variable x`): fi: if nops([args])=1 and op(1,[args])=`IterRes` then print(`IterRes(f,varlist): computes the `): print(`iterated (formal) residue of the rational function f`): print(`with respect to the variable list varlist`): fi: if nops([args])=1 and op(1,[args])=`S1521` then print(`S1521(k) verifies subsubsublemma 1.5.2.1 for k`): fi: if nops([args])=1 and op(1,[args])=`S1522` then print(`S1522(k) verifies subsubsublemma 1.5.2.2 for k`): print(`i.e. plugging x_2=1-1/x_j into x_2^{k-2} Omega_k(x_2^(-1),x_2,..,x_k`): print(`with j=3, .., k, you always get 0`): fi: if nops([args])=1 and op(1,[args])=`S15221` then print(`S15221() proves rigorously subsubsubsublemma 1.5.2.2.1`): print(`i.e. if you plug x[1]=1/x[2] and x[3]=1/(1-x[2]) into`): print(`the expression for each conceivable signed permutation of W(B_3)`): print(`you always get 0`): fi: if nops([args])=1 and op(1,[args])=`S1523` then print(`S1523(k) checks subsubsubsublemma 1.5.2.3 for k>=2`): fi: end: B:=proc(k,n,a) local schum,i,j,gu,mu,b: option remember: if n=k`): fi: if k<1 then ERROR(` k must be >=1`): fi: if nops(a)<>k then ERROR(`the length of the list a must be exactly k`): fi: if not n>=a[1] then ERROR(`You must have n>=a_1`): fi: for i from 1 to k-1 do if not a[i]>=a[i+1] then ERROR(`Since we don't have a_i >=a_(i+1) for i=`,i, `a is out of range`): fi: od: if not a[k]>=1 then ERROR(`Since a_`,k,`is not >=1, it is out of range`): fi: for i from 1 to k do if not a[i]<=n-i+1 then ERROR(`Since a_i is not <=n-i+1, for i=`,i,`it is out of range`): fi: od: if n=1 and k=1 then RETURN(1): fi: if n=k then if a[k]<>1 then ERROR(`Illegal a_k`): fi: RETURN(B(k-1,k,[op(1..k-1,a)])): fi: #gu is a polynomial in x[1], ... x[k] the coeff. of each monomial of #is 1, and such the monomials are t x[1]^b_1 ... x_[k]^b_k #for all b=(b_1, ... ,b_k) in eq. (1) of the paper on Act I: #Counting Magog) gu:=1: for i from 1 to k-1 do gu:=gu*x[i]^a[i+1]* normal((1-x[i]^(min(a[i],n-i)-a[i+1]+1))/(1-x[i])): od: gu:=gu*x[k]*normal((1-x[k]^min(a[k],n-k))/(1-x[k])): gu:=expand(gu): #schum is the running sum in (1) over all monomials schum:=0: if type(gu,`+`) then for j from 1 to nops(gu) do #mu is the jth monomial mu:=op(j,gu): b:=[]: for i from 1 to k do b:=[op(b),degree(mu,x[i])]: od: schum:=schum+B(k,n-1,b): od: else b:=[]: for i from 1 to k do b:=[op(b),degree(gu,x[i])]: od: schum:=schum+B(k,n-1,b) fi: schum: end: #polmagog(k,n) gives the sum of all monomials x_1^a_1 ... x_k^a_k #for which n>=a_1 >= ...>= a_k>=1 and a_i<=n-i+1 , which are #all the conceivable (k,n,[a_1, ... , a_k]) contributing a non-zero #term to the total b_k(n) of n by k Magog trapezoids (First equality of George) polmagog:=proc(k,n) local gu,i,gu1,j,mu: gu:=1: mu:=1: for i from 1 to k do mu:=mu*x[i]: gu:=gu*x[i]/(1-mu): od: for i from 1 to k do gu:=taylor(gu,x[i],n-i+2): gu1:=0: for j from 1 to n-i+1 do gu1:=gu1+coeff(gu,x[i],j)*x[i]^j: od: gu:=gu1: od: expand(gu): end: #b(k,n) sums over all non-zero B_k(n; a_1, ... , a_k) to give #the total number of k by n Magog trapezoids. It does that #by using polmagog(k,n) to get the generating polynomial for all #monomials b:=proc(k,n) local a,gu,schum,i,mu,j: gu:=polmagog(k,n): schum:=0: if type(gu,`+`) then for j from 1 to nops(gu) do mu:=op(j,gu): a:=[]: for i from 1 to k do a:=[op(a),degree(mu,x[i])]: od: schum:=schum+B(k,n,a): od: else mu:=gu: a:=[]: for i from 1 to k do a:=[op(a),degree(mu,x[i])]: od: schum:=schum+B(k,n,a): fi: schum: end: Bext:=proc(k,n,a) local i: option remember: if n=k`): fi: if k<1 then ERROR(` k must be >=1`): fi: if nops(a)<>k then ERROR(`the length of the list a must be exactly k`): fi: if not n>=a[1]-1 then ERROR(`You must have n>=a_1-1`): fi: for i from 1 to k-1 do if not a[i]>=a[i+1]-1 then ERROR(`Since we don't have a_i >=a_(i+1)-1 for i=`,i, `a is out of range`): fi: od: if not a[k]>=0 then ERROR(`Since a_`,k,`is not >=0, it is out of range`): fi: for i from 1 to k do if not a[i]<=n-i+1 then RETURN(0): fi: od: #This is condition (B1_i) on p.x of the act I: Counting Magog for i from 1 to k-1 do if a[i]-a[i+1]=-1 then RETURN(0): fi: od: #This is condition (B1_k) if a[k]=0 then RETURN(0): fi: #This is condition (B2) if a[1]=n+1 then RETURN(0): fi: B(k,n,a): end: #S1111 verifes empirically Subsubsublemma 1.1.1.1 S1111:=proc(k,n,a) local i,gu,b,j,mu,schum,t: if not n>k then ERROR(`The input is not applicable to (sub)^3lemma 1.1.1.1`): fi: if not n>=a[1] then ERROR(`The input is not applicable to (sub)^3lemma 1.1.1.1`): fi: for i from 1 to k-1 do if not a[i]>=a[i+1] then ERROR(`The input is not applicable to (sub)^3lemma 1.1.1.1`): fi: od: if not a[k]>=1 then ERROR(`The input is not applicable to (sub)^3lemma 1.1.1.1`): fi: gu:=1: for i from 1 to k do gu:=gu*(1+t*x[i]): od: gu:=expand(gu): #gu is the umbral represantation of the difference operator schum:=0: for j from 1 to nops(gu) do mu:=op(j,gu): b:=[]: for i from 1 to k do b:=[op(b),op(i,a)-degree(mu,x[i])]: od: schum:=schum+(-1)^(degree(mu,t))*Bext(k,n,b): od: print(`When k=`,k,`and n=`,n, `and the vector a is`,a, `then`): print(`the left side of (P \Delta E)(B_k) is`,schum): print(`and the right side of (P \Delta E)(B_k) is`,Bext(k,n-1,a)): schum,Bext(k,n-1,a): end: S1111all:=proc(k,n) local a,gu,i,gu1,j,mu,b: print(`The left sides of (P \Delta E)(B_k) for all applicable`): print(`a=(a_1 , ... , a_k), when k=`,k,`and n=`,n,`is as follows.`): #gu is the generating poly for all monomials in n>=a_1 >= ... a_k>=1 gu:=1: mu:=1: for i from 1 to k do mu:=mu*x[i]: gu:=gu*x[i]/(1-mu): od: for i from 1 to k do gu:=taylor(gu,x[i],n+1): gu1:=0: for j from 1 to n do gu1:=gu1+coeff(gu,x[i],j)*x[i]^j: od: gu:=gu1: od: gu:=expand(gu): if type(gu,`+`) then for j from 1 to nops(gu) do mu:=op(j,gu): a:=[]: for i from 1 to k do a:=[op(a),degree(mu,x[i])]: od: S1111(k,n,a): od: else mu:=gu: a:=[]: for i from 1 to k do a:=[op(a),degree(gu,x[i])]: od: S1111(k,n,a): fi: end: X:=proc(k,n,a) local b,schum,j,mu,i,gu: option remember: if n=k`): fi: if k<1 then ERROR(` k must be >=1`): fi: if nops(a)<>k then ERROR(`the length of the list a must be exactly k`): fi: if not n>=a[1]-1 then ERROR(`You must have n>=a_1-1`): fi: for i from 1 to k-1 do if not a[i]>=a[i+1]-1 then ERROR(`Since we don't have a_i >=a_(i+1)-1 for i=`,i, `a is out of range`): fi: od: if not a[k]>=0 then ERROR(`Since a_`,k,`is not >=0, it is out of range`): fi: #This is condition (X4) if n=k and k=1 then if a[1]=1 then RETURN(1): else RETURN(0): fi: fi: #This is condition (X3) if n=k and k> 1 then if a[k]=1 then RETURN(X(k-1,k,[op(1..k-1,a)])): else RETURN(0): fi: fi: #This is condition (X1_i) of the act I: Counting Magog for i from 1 to k-1 do if a[i]-a[i+1]=-1 then RETURN(0): fi: od: #This is condition (X1_k) if a[k]=0 then RETURN(0): fi: #This is condition (X2) if a[1]=n+1 then RETURN(0): fi: gu:=1: for i from 1 to k do gu:=gu*(1+t*x[i]): od: gu:=expand(gu-1): #gu is the umbral represantation of the difference operator schum:=X(k,n-1,a): if type(gu,`+`) then for j from 1 to nops(gu) do mu:=op(j,gu): b:=[]: for i from 1 to k do b:=[op(b),op(i,a)-degree(mu,x[i])]: od: schum:=schum-(-1)^(degree(mu,t))*X(k,n,b): od: else mu:=gu: b:=[]: for i from 1 to k do b:=[op(b),op(i,a)-degree(mu,x[i])]: od: schum:=schum-(-1)^(degree(mu,t))*X(k,n,b): fi: schum: end: bfast:=proc(k,n) local a,gu,schum,i,mu,j: gu:=polmagog(k,n): schum:=0: if type(gu,`+`) then for j from 1 to nops(gu) do mu:=op(j,gu): a:=[]: for i from 1 to k do a:=[op(a),degree(mu,x[i])]: od: schum:=schum+B(k,n,a): od: else mu:=gu: a:=[]: for i from 1 to k do a:=[op(a),degree(mu,x[i])]: od: schum:=schum+X(k,n,a): fi: schum: end: S1113:=proc(k,n) local a,gu,i,gu1,j,mu: #gu is the generating poly for all monomials in n>=a_1 >= ... a_k>=1 gu:=1: mu:=1: for i from 1 to k do mu:=mu*x[i]: gu:=gu*x[i]/(1-mu): od: for i from 1 to k do gu:=taylor(gu,x[i],n+1): gu1:=0: for j from 1 to n do gu1:=gu1+coeff(gu,x[i],j)*x[i]^j: od: gu:=gu1: od: gu:=expand(gu): if type(gu,`+`) then for j from 1 to nops(gu) do mu:=op(j,gu): a:=[]: for i from 1 to k do a:=[op(a),degree(mu,x[i])]: od: print( `X(`,k,n,a,`)=`, X(k,n,a)): od: else mu:=gu: a:=[]: for i from 1 to k do a:=[op(a),degree(gu,x[i])]: od: print( `X(`,k,n,a,`)=`, X(k,n,a)): fi: end: Delta:=proc(k) local gu,i,j: gu:=1: for i from 1 to k do gu:=gu*(1-2*x[i]): od: for i from 1 to k do for j from i+1 to k do gu:=gu*(x[j]-x[i])*(x[j]+x[i]-1): od: od: gu: end: fnk:=proc(k,n) local i,j, gu: gu:=Delta(k): for i from 1 to k do gu:=gu/(1-x[i])^(n+k+1)/x[i]^(n+k-i): od: for i from 1 to k do for j from i+1 to k do gu:=gu/(1-x[i]*x[j]): od: od: gu: end: Fnk:=proc(k,n) local i,j, gu: gu:=Phi(k): for i from 1 to k do gu:=gu/(1-x[i])^(n+i+1)/x[i]^(n+1): od: for i from 1 to k do for j from i+1 to k do gu:=gu/(1-x[i]*x[j])/(1-(1-x[i])*x[j]): od: od: gu: end: C:=proc(k,n,a) local i,gu: if nops(a)<>k then ERROR(`a must be with`,k,`components`): fi: gu:=Delta(k): for i from 1 to k do gu:=gu/(1-x[i])^(k+n)/x[i]^(a[i]+k-i-1): od: for i from k by -1 to 1 do gu:=CT(gu,x[i]): od: gu: end: S111:=proc(k,n) local a,gu,i,gu1,j,mu: #gu is the generating poly for all monomials in n>=a_1 >= ... a_k>=1 gu:=1: mu:=1: for i from 1 to k do mu:=mu*x[i]: gu:=gu*x[i]/(1-mu): od: for i from 1 to k do gu:=taylor(gu,x[i],n+1): gu1:=0: for j from 1 to n do gu1:=gu1+coeff(gu,x[i],j)*x[i]^j: od: gu:=gu1: od: gu:=expand(gu): if type(gu,`+`) then for j from 1 to nops(gu) do mu:=op(j,gu): a:=[]: for i from 1 to k do a:=[op(a),degree(mu,x[i])]: od: print( `B(`,k,n,a,`)=`, X(k,n,a), `C(`,k,n,a,`)=`, C(k,n,a) ): od: else mu:=gu: a:=[]: for i from 1 to k do a:=[op(a),degree(gu,x[i])]: od: print( `B(`,k,n,a,`)=`, X(k,n,a), `C(`,k,n,a,`)=`, C(k,n,a) ): fi: end: S11:=proc(k,n) local gu,i,j: gu:=fnk(k,n): resh:=[seq(x[i],i=1..k)]: gu:=IterRes(gu,resh): print(`For k=`,k,`and n=`,n,`The right side of (MagogTotal) is`,gu): print(`The left side, b(`,k,n,`)=`,bfast(k,n)): gu: end: S1112:=proc(k) local a,gu,i,gu1,j,mu,b: print(`Verifing (the only non-trivial part) of subsubsublemma 1.1.1.2`): print(`i.e. (C3) for the case k=`,k): #gu is the generating poly for all monomials in n>=a_1 >= ... a_k>=1 gu:=1: mu:=1: for i from 1 to k do mu:=mu*x[i]: gu:=gu*x[i]/(1-mu): od: for i from 1 to k do gu:=taylor(gu,x[i],k+1): gu1:=0: for j from 1 to k do gu1:=gu1+coeff(gu,x[i],j)*x[i]^j: od: gu:=gu1: od: gu:=expand(gu): if type(gu,`+`) then for j from 1 to nops(gu) do mu:=op(j,gu): a:=[]: for i from 1 to k do a:=[op(a),degree(mu,x[i])]: od: if a[k]=1 then print(`When a=`,a): print(`the left side of (C3) is`,C(k,k,a)): print( `the right side is` ,C(k-1,k,[op(1..k-1,a)])): else print(`When a=`,a): print(`the left side of (C3) is`,C(k,k,a)): print( `the right side is` ,0): fi: od: else mu:=gu: a:=[]: for i from 1 to k do a:=[op(a),degree(gu,x[i])]: od: if a[k]=1 then print(`When a=`,a): print(`the left side of (C3) is`,C(k,k,a)): print( `the right side is` ,C(k-1,k,[op(1..k-1,a)])): else print(`When a=`,a): print(`the left side of (C3) is`,C(k,k,a)): print( `the right side is` ,0): fi: fi: end: S112:=proc(k,n) local gu,lu,i,j: gu:=Delta(k): lu:=1: for i from 1 to k do lu:=lu*x[k-i+1]: gu:=gu*x[i]^i/(1-x[i])^(k+n)/x[i]^(n+k)/(1-lu): od: resh:=[seq(x[i],i=1..k)]: gu:=IterRes(gu,resh): print(`For k=`,k,`and n=`,n,`The right side of (George) is`,gu): print(`The left side, b(`,k,n,`)=`,bfast(k,n)): gu: end: with(combinat): #actpi is the result of the action of the permutation pi #of {1,2, ...,k} on a rational function of (x[1], ... , x[k]) actpi:=proc(f,pi) local g,i,y,k: k:=nops(pi): g:=f: for i from 1 to k do g:=subs(x[i]=y[pi[i]],g): od: for i from 1 to k do g:=subs(y[i]=x[i],g): od: g: end: #acteps(f,eps) is the result of a sign-assignment eps=[eps_1, ... , eps_k] #on a rational function f(x[1], ... , x[k]) acteps:=proc(f,eps) local i,g: g:=f: for i from 1 to nops(eps) do if eps[i]=-1 then g:=subs(x[i]=1-x[i],g): fi: od: g: end: #The action of a signed permutation (pi,eps) in W(B_k) on a rational #function f(x[1], ... , x[k]) actsipi:=proc(f,pi,eps): acteps(actpi(f,pi),eps): end: S13spec:=proc(k,n,pi,eps) local gu,resh,i: gu:=fnk(k,n): gu:=actsipi(gu,pi,eps): resh:=[]: for i from 1 to k do resh:=[op(resh),x[i]]; od: gu:=IterRes(gu,resh): print(`When n=`,n,`and k=`,k,`and the signed permutation (pi,eps) is`): print(`(`,pi,eps,`), the left side of the identity in Sublemma 1.3 is`): print(gu): end: allsigns:=proc(k) local i,gu,reshy,evar: if k<0 then ERROR(`k must be non-negative`): fi: if k=0 then RETURN([[]]): fi: reshy:=allsigns(k-1): gu:=[]: for i from 1 to nops(reshy) do evar:=op(i,reshy): gu:=[op(gu),[op(evar),1],[op(evar),-1]]: od: gu: end: S13:=proc(k,n) local reshsign,reshper,pi,eps,i,j: reshper:=permute(k): reshsign:=allsigns(k): for i from 1 to nops(reshper) do pi:=op(i,reshper): for j from 1 to nops(reshsign) do eps:=op(j,reshsign): S13spec(k,n,pi,eps): od: od: end: S11121:=proc(k,a) local reshsign,reshper,pi,eps,i,j: if not op(k,a)>=2 then ERROR(`a_k must be >=2`): fi: reshper:=permute(k): reshsign:=allsigns(k): for i from 1 to nops(reshper) do pi:=op(i,reshper): for j from 1 to nops(reshsign) do eps:=op(j,reshsign): S11121spec(k,a,pi,eps): od: od: end: S11121spec:=proc(k,a,pi,eps) local gu,resh,i: gu:=Delta(k): for i from 1 to k do gu:=gu*x[i]^(k-op(i,a)+i)/x[i]^(2*k)/(1-x[i])^(2*k): od: gu:=actsipi(gu,pi,eps): resh:=[]: for i from 1 to k do resh:=[op(resh),x[i]]; od: gu:=IterRes(gu,resh): print(`When a=`,a,`and k=`,k,`and the signed permutation (pi,eps) is`): print(`(`,pi,eps,`), the left side of the identity in 1.1.1.2.1 is`): print(gu): end: S11122:=proc(k,a) local gu,resh,i: gu:=1: for i from 1 to k do gu:=gu*x[i]^(k-op(i,a)+i)/x[i]^(2*k)/(1-x[i])^(2*k): od: print(`The left side of (Efes'') is `): print(Delta(k)*antisymmetrizerWB_k(gu,k)): end: allsigns:=proc(k) local i,gu,reshy,evar: if k<0 then ERROR(`k must be non-negative`): fi: if k=0 then RETURN([[]]): fi: reshy:=allsigns(k-1): gu:=[]: for i from 1 to nops(reshy) do evar:=op(i,reshy): gu:=[op(gu),[op(evar),1],[op(evar),-1]]: od: gu: end: S13:=proc(k,n) local reshsign,reshper,pi,eps,i,j: reshper:=permute(k): reshsign:=allsigns(k): for i from 1 to nops(reshper) do pi:=op(i,reshper): for j from 1 to nops(reshsign) do eps:=op(j,reshsign): S13spec(k,n,pi,eps): od: od: end: S13prime:=proc(k,n) local reshsign,reshper,pi,eps,i,j,i1: reshper:=permute(k): reshsign:=allsigns(k): for i from 1 to nops(reshper) do pi:=op(i,reshper): mu:=[seq(x[op(i1,pi)],i1=1..k)]: print(`When pi is`,pi): for j from 1 to nops(reshsign) do eps:=op(j,reshsign): print(`and when eps is`,eps,`the left side of (1.3') is`): print(IterRes(acteps(fnk(k,n),eps),mu)): od: od: end: S131:=proc(k,n) local reshsign,reshper,pi,eps,i,j,i1,eps1: reshper:=permute(k): reshsign:=allsigns(k): for i from 1 to nops(reshper) do pi:=op(i,reshper): mu:=[seq(x[op(i1,pi)],i1=1..k)]: print(`When pi is`,pi): for j from 1 to nops(reshsign) do eps:=op(j,reshsign): print(`and when eps is`,eps): for i1 from 1 to k while op(op(i1,pi),eps)=1 do od: print(`then the altered eps, featuring on the left of S1.3.1 is`): if i1<=k then eps1:=[op(1..i1-1,eps),1,op(i1+1..k,eps)]: print(eps1): print(`The left side of the identity of subsublemma 1.3.1 is`): print(IterRes(acteps(fnk(k,n),eps1),mu)): print(`while its right side of is`): print(IterRes(acteps(fnk(k,n),eps),mu)): fi: od: od: end: S14spec:=proc(k,n,pi,eps) local gu,resh,i: gu:=Fnk(k,n): gu:=actsipi(gu,pi,eps): resh:=[]: for i from 1 to k do resh:=[op(resh),x[i]]; od: gu:=IterRes(gu,resh): print(`When n=`,n,`and k=`,k,`and the signed permutation (pi,eps) is`): print(`(`,pi,eps,`), the left side of the identity in Sublemma 1.4 is`): print(gu): end: S14:=proc(k,n) local reshsign,reshper,pi,eps,i,j: reshper:=permute(k): reshsign:=allsigns(k): for i from 1 to nops(reshper) do pi:=op(i,reshper): for j from 1 to nops(reshsign) do eps:=op(j,reshsign): S14spec(k,n,pi,eps): od: od: end: #inv is the number of inversions of a permutation pi inv:=proc(pi) local schum,i,j,k: schum:=0: k:=nops(pi): for i from 1 to k do for j from i+1 to k do if pi[i]>pi[j] then schum:=schum+1: fi: od: od: schum: end: #signpi gives the sign of a permutation pi signpi:=proc(pi): (-1)^inv(pi): end: #signeps gives the sign of a sign-assignment eps signeps:=proc(eps) local i,gu: gu:=1: for i from 1 to nops(eps) do if eps[i]=-1 then gu:=(-1)*gu: fi: od: gu: end: #signsiper gives the sign of a signed permutation (pi,eps) signsiper:=proc(pi,eps): if nops(pi)<>nops(eps) then ERROR(`pi and eps should have the same size`): fi: signpi(pi)*signeps(eps): end: #The antisymmetrizer of a rational function f(x[1], ..., x[k]) # w.r.t. to the symmetric group antisymmetrizerS_k:=proc(f,k) local pi,j,gu,schum: schum:=0: gu:=permute(k): for j from 1 to nops(gu) do pi:=op(j,gu): schum:=schum+signpi(pi)*actpi(f,pi): od: factor(normal(schum)): end: #S113(k) verifies subsublemma 1.1.3 for k S113:=proc(k) local mu,i,gu: mu:=1; gu:=1; for i from k by -1 to 1 do mu:=mu*x[i]: gu:=gu*x[i]^i/(1-mu): od: gu:=antisymmetrizerS_k(gu,k): print(`The left side of (Issai) in the statement of subsublemma 1.1.3 is`): gu: end: antisymmetrizerWB_k:=proc(f,k) local i,gu: gu:=antisymmetrizerS_k(f,k): for i from 1 to k do gu:=gu-subs(x[i]=1-x[i],gu): od: normal(gu): end: Phi:=proc(k) local gu,i,j: gu:=1; for i from 1 to k do gu:=gu*x[i]^k*(1-x[i])^(k-i): od: for i from 1 to k do for j from i+1 to k do gu:=gu*(1-x[i]*(1-x[j]))*(1-(1-x[i])*(1-x[j])) : od: od: gu:=expand(gu): gu:=antisymmetrizerWB_k(gu,k): gu:=expand((-1)^k*gu): gu: end: Omegak:=proc(k): normal(Phi(k)/Delta(k)): end: Lk:=proc(k) local gu,i,j: gu:=1; for i from 1 to k do gu:=gu*x[i]^(i+1): od: for i from 1 to k do for j from i+1 to k do gu:=gu*(1-(1-x[i])*x[j] )*(1-x[i]*(1-x[j]))*(1-(1-x[i])*(1-x[j])) : od: od: gu:=antisymmetrizerWB_k(gu,k): gu:=normal((-1)^k*gu/Delta(k)): gu: end: S15:=proc(k) local gu: print(`The difference between the two sides of Eq.(Gog=Magog) `): print(`in the statement of Sublemma 1.5 is`): gu:=expand(Lk(k)-Omegak(k)^2): print(gu): gu: end: S151:=proc(k) local y,rig,lef,j: if k<2 then ERROR(`Not applicable`): fi: lef:=Lk(k): lef:=subs(x[1]=1/x[2],lef): rig:=Lk(k-2): for j from 1 to k-2 do rig:=subs(x[j]=y[j+2],rig): od: for j from 3 to k do rig:=subs(y[j]=x[j],rig): od: for j from 3 to k do rig:=rig*((1-(1-x[2])*x[j] )*(1-(1-x[2])*(1-x[j]) )/x[2])^2: od: print(`The ratio of the left side to the right side of (1.5.1a) in the`): print(`the statement of subsublemma 1.5.1, when k=`,k,` is`): print(normal(lef/rig)): lef:=Lk(k): lef:=subs(x[1]=0,lef): rig:=Lk(k-1): for j from 1 to k-1 do rig:=subs(x[j]=y[j+1],rig): od: for j from 2 to k do rig:=subs(y[j]=x[j],rig): od: print(`The ratio of the left side to the right side of (1.5.1c) in the`): print(`the statement of subsublemma 1.5.1 when k=`,k,`is`): print(normal(lef/rig)): end: S152:=proc(k) local y,rig,lef,j: if k<2 then ERROR(`Not applicable`): fi: lef:=Omegak(k): lef:=subs(x[1]=1/x[2],lef): rig:=Omegak(k-2): for j from 1 to k-2 do rig:=subs(x[j]=y[j+2],rig): od: for j from 3 to k do rig:=subs(y[j]=x[j],rig): od: for j from 3 to k do rig:=rig*(1-(1-x[2])*x[j] )*(1-(1-x[2])*(1-x[j]))/x[2] : od: print(`The ratio of the left side to the right side of (1.5.2a) in the`): print(`the statement of subsublemma 1.5.2, when k=`,k,` is`): print(normal(lef/rig)): lef:=Omegak(k): lef:=subs(x[1]=0,lef): rig:=Omegak(k-1): for j from 1 to k-1 do rig:=subs(x[j]=y[j+1],rig): od: for j from 2 to k do rig:=subs(y[j]=x[j],rig): od: print(`The ratio of the left side to the right side of (1.5.2c) in the`): print(`the statement of subsublemma 1.5.2 when k=`,k,`is`): print(normal(lef/rig)): end: S1511:=proc() local t,x2: bar:=proc(u):1-u:end: lef:=((1-bar(1/x2)*t)*(1-(1/x2)*bar(t))*(1-bar(1/x2)*bar(t))/ (t+1/x2-1))* ((1-bar(x2)*t)*(1-x2*bar(t))*(1-bar(x2)*bar(t))/ (t+x2-1)): rig:=( (1-bar(x2)*bar(t))*(1-bar(x2)*t)/x2 )^2: print(`This proves rigorously subsubsublemma 1.5.1.1`): print(`The left side of (1.5.1.1) is`): print(factor(lef)): print(`The right side of (1.5.1.1) is`): print(factor(rig)): print(`Their ratio is`): print(normal(lef/rig)): end: S1512:=proc() local t,x2: bar:=proc(u):1-u:end: lef:=((1/x2)^2/(2/x2-1))*(x2^2/(2*x2-1))* (1-bar(1/x2)*x2)*(1-(1/x2)*bar(x2))*(1-bar(1/x2)*bar(x2))/(x2+1/x2-1): print(`This proves rigorously subsubsublemma 1.5.1.1`): print(`The left side of (1.5.1.1) is`): print(lef): print(`And in normal form this equals`): print(factor(lef)): print(`The right side of (1.5.1.1) is`): print(1): print(`Q.E.D.`): end: M:=proc(k,n,a) local katen,schum,i,j,gu,mu,b: option remember: if n=k`): fi: if k<1 then ERROR(` k must be >=1`): fi: if nops(a)<>k then ERROR(`the length of the list a must be exactly k`): fi: if not n>=a[1] then ERROR(`You must have n>=a_1`): fi: for i from 1 to k-1 do if not a[i]>=a[i+1] then ERROR(`Since we don't have a_i >=a_(i+1) for i=`,i, `a is out of range`): fi: od: if not a[k]>=1 then ERROR(`Since a_`,k,`is not >=1, it is out of range`): fi: for i from 1 to k do if not a[i]>=k-i+1 then ERROR(`Since a_i is not >=k-i+1, for i=`,i,`it is out of range`): fi: od: if n=1 and k=1 then RETURN(1): fi: if n=k then if a[1]<>k then ERROR(`Illegal a_k`): fi: RETURN(M(k-1,k,[op(2..k,a)])): fi: #gu is a polynomial in x[1], ... x[k] the coeff. of each monomial of #is 1, and such the monomials are x[1]^b_1 ... x_[k]^b_k #for all b=(b_1, ... ,b_k) in the set T_k(n;a) defined right before #(Howard) in the set `Counting Gog` gu:=1: for i from 2 to k do gu:=gu*x[i]^(k-i+1)*normal((1-x[i]^(min(a[i],a[i-1]-1)-(k-i+1)+1))/(1-x[i])): od: gu:=gu*x[1]^k*normal((1-x[1]^(a[1]-k+1))/(1-x[1])): gu:=expand(gu): #schum is the running sum in (1) over all monomials schum:=0: if type(gu,`+`) then for j from 1 to nops(gu) do #mu is the jth monomial mu:=op(j,gu): b:=[]: for i from 1 to k do b:=[op(b),degree(mu,x[i])]: od: #katen checks whether n-1>=b[1]>=b[2]>= ... >=b[k]>=1 katen:=1; if not b[1]<=n-1 or not b[k]>=1 then katen:=0: fi: for i from 1 to k-1 do if not b[i]>=b[i+1] then katen:=0: fi: od: if katen=1 then schum:=schum+M(k,n-1,b): fi: od: else b:=[]: for i from 1 to k do b:=[op(b),degree(gu,x[i])]: od: katen:=1; if not b[1]<=n-1 or not b[k]>=1 then katen:=0: fi: for i from 1 to k-1 do if not b[i]>=b[i+1] then katen:=0: fi: od: if katen=1 then schum:=schum+M(k,n-1,b): fi: fi: schum: end: Mt:=proc(k,n,a) local katen,schum,i,j,gu,mu,b: option remember: if n=k`): fi: if k<1 then ERROR(` k must be >=1`): fi: if nops(a)<>k then ERROR(`the length of the list a must be exactly k`): fi: if not n>=a[1]-1 then ERROR(`You must have n>=a_1-1`): fi: for i from 1 to k-1 do if not a[i]>=a[i+1] then ERROR(`Since we don't have a_i >=a_(i+1) for i=`,i, `a is out of range`): fi: od: if not a[k]>=0 then ERROR(`Since a_`,k,`is not >=0, it is out of range`): fi: for i from 1 to k do if not a[i]>=k-i then ERROR(`Since a_i is not >=k-i, for i=`,i,`it is out of range`): fi: od: if n=1 and k=1 then if a[1]=1 then RETURN(1): else RETURN(0): fi: fi: if n=k and k=a[1] and not a[1]>a[2] then RETURN(0): fi: if k>1 and a[1]=n+1 and a[2]>n then RETURN(0): fi: if n=k then if a[1]<>k then RETURN(0): fi: RETURN(Mt(k-1,k,[op(2..k,a)])): fi: if a[1]=n+1 then RETURN(0): fi: #gu is a polynomial in x[1], ... x[k] the coeff. of each monomial of #is 1, and such the monomials are x[1]^b_1 ... x_[k]^b_k #for all b=(b_1, ... ,b_k) in the set T_k(n;a) defined right before #(Howard) in the set `Counting Gog` gu:=1: for i from 1 to k do gu:=gu*x[i]^(k-i+1)*normal((1-x[i]^(a[i]-(k-i+1)+1))/(1-x[i])): od: gu:=expand(gu): #schum is the running sum in (tilde M_k) over all monomials schum:=0: if type(gu,`+`) then for j from 1 to nops(gu) do #mu is the jth monomial mu:=op(j,gu): b:=[]: for i from 1 to k do b:b:=[op(b),degree(mu,x[i])]: od: #katen checks whether n-1>=b[1]>=b[2]>= ... >=b[k]>=1 katen:=1; if not b[1]<=n-1 or not b[k]>=1 then katen:=0: fi: for i from 1 to k-1 do if not b[i]>=b[i+1] then katen:=0: fi: od: if katen=1 then schum:=schum+M(k,n-1,b): fi: od: else b:=[]: for i from 1 to k do b:=[op(b),degree(gu,x[i])]: od: katen:=1; if not b[1]<=n-1 or not b[k]>=1 then katen:=0: fi: for i from 1 to k-1 do if not b[i]>=b[i+1] then katen:=0: fi: od: if katen=1 then schum:=schum+M(k,n-1,b): fi: fi: schum: end: m:=proc(k,n) local i,a: a:=[]: for i from 1 to k do a:=[op(a),n+1]: od: Mt(k,n+1,a): end: #S1211 verifes empirically Subsubsublemma 1.2.1.1 S1211:=proc(k,n,a) local i,gu,b,j,mu,schum,t,a1: if not n>k then ERROR(`The input is not applicable to (sub)^3lemma 1.2.1.1`): fi: if not n>=a[1] then ERROR(`The input is not applicable to (sub)^3lemma 1.2.1.1`): fi: for i from 1 to k-1 do if not a[i]>=a[i+1] then ERROR(`The input is not applicable to (sub)^3lemma 1.2.1.1`): fi: od: if not a[k]>=1 then ERROR(`The input is not applicable to (sub)^3lemma 1.1.1.1`): fi: gu:=1: # gu is the umbral represantation of the difference operator #P^(a) defined in the statement of subsubsublemma 1.2.1.1 for i from 1 to k-1 do if a[i]>a[i+1] then gu:=gu*(1+t*x[i]): fi: od: gu:=gu*(1+t*x[k]): gu:=expand(gu): schum:=0: for j from 1 to nops(gu) do mu:=op(j,gu): b:=[]: for i from 1 to k do b:=[op(b),op(i,a)-degree(mu,x[i])]: od: schum:=schum+(-1)^(degree(mu,t))*Mt(k,n,b): od: print(`When k=`,k,`and n=`,n, `and the vector a is`,a, `then`): print(`the left side of (P \Delta E)(\tilde M_k) is`,schum): #a1 is the vector (a[1], min(a[1]-1,a[2]), ..., min(a[k-1]-1,a[k]) a1:=[op(1,a)]: for i from 2 to k do a1:=[op(a1),min(a[i-1]-1,a[i])]: od: print(`and the right side of (P \Delta E)(M_k) is`,Mt(k,n-1,a1)): schum,Mt(k,n-1,a): end: S1211all:=proc(k,n) local a,gu,i,gu1,j,mu,beseder: print(`The left and right sides of (P \Delta E)(M_k) for all applicable`): print(`a=(a_1 , ... , a_k), when k=`,k,`and n=`,n,`are as follows.`): #gu is the generating poly for all monomials in n>=a_1 >= ... a_k>=1 #and a[1]>=k, a[2]>=k-1, ... a[i]>=k-i+1 , a[k]>=1 if not n>k then ERROR(`The input is not applicable to (sub)^3lemma 1.2.1.1`): fi: gu:=1: mu:=1: for i from 1 to k do mu:=mu*x[i]: gu:=gu*x[i]/(1-mu): od: for i from 1 to k do gu:=taylor(gu,x[i],n+1): gu1:=0: for j from 1 to n do gu1:=gu1+coeff(gu,x[i],j)*x[i]^j: od: gu:=gu1: od: gu:=expand(gu): if type(gu,`+`) then for j from 1 to nops(gu) do mu:=op(j,gu): a:=[]: for i from 1 to k do a:=[op(a),degree(mu,x[i])]: od: beseder:=1: for i from 1 to k do if not a[i]>=k-i+1 then beseder:=0: fi: od: if beseder=1 then S1211(k,n,a): fi: od: else mu:=gu: a:=[]: for i from 1 to k do a:=[op(a),degree(gu,x[i])]: od: beseder:=1: for i from 1 to k do if not a[i]>=k-i+1 then beseder:=0: fi: od: if beseder=1 then S1211(k,n,a): fi: fi: end: #InGog tests whether (n,[a[1], ... , a[k]) belongs to the Land_Of_Gog InGog:=proc(k,n,a) local i: if nk then RETURN(0): fi: for i from 1 to k do if not a[i]>=k-i+1 then RETURN(0): fi: od: if not n>=a[1] then RETURN(0): fi: for i from 1 to k-1 do if not a[i]>=a[i+1] then RETURN(0): fi: od: 1: end: #InEGog tests whether (n,[a[1], ... , a[k]) belongs to the #extended region \overline{Land_Of_Gog} InEGog:=proc(k,n,a) local i: if nk then RETURN(0): fi: for i from 1 to k do if not a[i]>=k-i then RETURN(0): fi: od: if not n>=a[1]-1 then RETURN(0): fi: for i from 1 to k-1 do if not a[i]>=a[i+1] then RETURN(0): fi: od: if k>=2 and a[1]=n+1 and not a[2]<=n then RETURN(0): fi: if k>=2 and n=k and k=a[1] and not a[2]a[i+1] then gu:=gu*(1+t*x[i]): fi: od: gu:=expand(gu-1): #gu is the umbral represantation of the difference operator #a1 is the vector (a[1], min(a[1]-1,a[2]), ..., min(a[k-1]-1,a[k]) a1:=[op(1,a)]: for i from 2 to k do a1:=[op(a1),min(a[i-1]-1,a[i])]: od: schum:=Y(k,n-1,a1): if type(gu,`+`) then for j from 1 to nops(gu) do mu:=op(j,gu): b:=[]: for i from 1 to k do b:=[op(b),op(i,a)-degree(mu,x[i])]: od: schum:=schum-(-1)^(degree(mu,t))*Y(k,n,b): od: else mu:=gu: b:=[]: for i from 1 to k do b:=[op(b),op(i,a)-degree(mu,x[i])]: od: schum:=schum-(-1)^(degree(mu,t))*Y(k,n,b): fi: schum: end: S1213:=proc(k,n) local a,gu,i,gu1,j,mu: #gu is the generating poly for all monomials in n>=a_1 >= ... a_k>=1 gu:=1: mu:=1: for i from 1 to k do mu:=mu*x[i]: gu:=gu*x[i]/(1-mu): od: for i from 1 to k do gu:=taylor(gu,x[i],n+1): gu1:=0: for j from 1 to n do gu1:=gu1+coeff(gu,x[i],j)*x[i]^j: od: gu:=gu1: od: gu:=expand(gu): if type(gu,`+`) then for j from 1 to nops(gu) do mu:=op(j,gu): a:=[]: for i from 1 to k do a:=[op(a),degree(mu,x[i])]: od: if InEGog(k,n,a)=1 then print( `Y(`,k,n,a,`)=`, Y(k,n,a)): fi: od: else mu:=gu: a:=[]: for i from 1 to k do a:=[op(a),degree(gu,x[i])]: od: if InEGog(k,n,a)=1 then print( `Y(`,k,n,a,`)=`, Y(k,n,a)): fi: fi: end: #CT finds the constant term of a rational function w.r.t. to the variable x CT:=proc(f,x) local mu,f1: if normal(f)=0 then RETURN(0): fi: f1:=series(f,x): mu:=op(2,f1): f1:=series(f,x,3-mu): coeff(f1,x,0): end: #Res finds the residue w.r.t to x of the rational function f Res:=proc(f,x) local mu,f1: if f=0 then RETURN(0): fi: f1:=series(f,x): mu:=op(2,f1): f1:=series(f,x,3-mu): RETURN(coeff(f1,x,-1)): end: IterRes:=proc(f,varlist) local i,gu: gu:=f: for i from nops(varlist) by -1 to 1 do gu:=Res(gu,op(i,varlist)): od: gu: end: H:=proc(k,n,a) local i,gu: if nops(a)<>k then ERROR(`a must be with`,k,`components`): fi: gu:=Phi(k): for i from 1 to k do gu:=gu/(1-x[i])^(n+i)/x[i]^(a[i]-1): od: for i from 1 to k do for j from i+1 to k do gu:=gu/(1-x[i]*x[j])/(1-(1-x[i])*x[j]): od: od: for i from k by -1 to 1 do gu:=CT(gu,x[i]): od: gu: end: S12:=proc(k,n) local gu,resh,i: gu:=Fnk(k,n): resh:=[seq(x[i],i=1..k)]: gu:=IterRes(gu,resh): print(`For k=`,k,`and n=`,n,`The right side of (GogTotal) is`,gu): print(`The left side, m(`,k,n,`)=`,m(k,n)): gu: end: S121:=proc(k,n) local a,gu,i,gu1,j,mu,beseder: print(`The left and right sides of (Gog) in the statement of subsublemma`): print(`1.2.1 for all applicable`): print(`a=(a_1 , ... , a_k), when k=`,k,`and n=`,n,`are as follows.`): #gu is the generating poly for all monomials in n>=a_1 >= ... a_k>=1 #and a[1]>=k, a[2]>=k-1, ... a[i]>=k-i+1 , a[k]>=1 if not n>=k then ERROR(`The input is not applicable to (sub)^2lemma 1.2.1`): fi: gu:=1: mu:=1: for i from 1 to k do mu:=mu*x[i]: gu:=gu*x[i]/(1-mu): od: for i from 1 to k do gu:=taylor(gu,x[i],n+1): gu1:=0: for j from 1 to n do gu1:=gu1+coeff(gu,x[i],j)*x[i]^j: od: gu:=gu1: od: gu:=expand(gu): if type(gu,`+`) then for j from 1 to nops(gu) do mu:=op(j,gu): a:=[]: for i from 1 to k do a:=[op(a),degree(mu,x[i])]: od: beseder:=1: for i from 1 to k do if not a[i]>=k-i+1 then beseder:=0: fi: od: if n=k and (not a[1]=k or not a[2]=k-i+1 then beseder:=0: fi: od: if n=k and (not a[1]=k or not a[2]k then ERROR(`The input is not applicable to (sub)^3lemma 1.2.1.1`): fi: if not n>=a[1] then ERROR(`The input is not applicable to (sub)^3lemma 1.2.1.1`): fi: for i from 1 to k-1 do if not a[i]>=a[i+1] then ERROR(`The input is not applicable to (sub)^3lemma 1.2.1.1`): fi: od: if not a[k]>=1 then ERROR(`The input is not applicable to (sub)^3lemma 1.1.1.1`): fi: gu:=1: # gu is the umbral represantation of the difference operator #P^(a) defined in the statement of subsubsublemma 1.2.1.1 for i from 1 to k-1 do if a[i]>a[i+1] then gu:=gu*(1+t*x[i]): fi: od: gu:=gu*(1+t*x[k]): gu:=expand(gu): schum:=0: for j from 1 to nops(gu) do mu:=op(j,gu): b:=[]: for i from 1 to k do b:=[op(b),op(i,a)-degree(mu,x[i])]: od: schum:=schum+(-1)^(degree(mu,t))*H(k,n,b): od: print(`When k=`,k,`and n=`,n, `and the vector a is`,a, `then`): #a1 is the vector (a[1], min(a[1]-1,a[2]), ..., min(a[k-1]-1,a[k]) a1:=[op(1,a)]: for i from 2 to k do a1:=[op(a1),min(a[i-1]-1,a[i])]: od: print(`the left and right sides of (P \Delta E)(H_k) are`,schum, H(k,n-1,a1)): #schum,Mt(k,n-1,a): end: S12121all:=proc(k,n) local a,gu,i,gu1,j,mu,beseder: print(`The left and right sides of (P \Delta E)(H_k) for all applicable`): print(`a=(a_1 , ... , a_k), when k=`,k,`and n=`,n,`are as follows.`): #gu is the generating poly for all monomials in n>=a_1 >= ... a_k>=1 #and a[1]>=k, a[2]>=k-1, ... a[i]>=k-i+1 , a[k]>=1 if not n>k then ERROR(`The input is not applicable to (sub)^3lemma 1.2.1.2`): fi: gu:=1: mu:=1: for i from 1 to k do mu:=mu*x[i]: gu:=gu*x[i]/(1-mu): od: for i from 1 to k do gu:=taylor(gu,x[i],n+1): gu1:=0: for j from 1 to n do gu1:=gu1+coeff(gu,x[i],j)*x[i]^j: od: gu:=gu1: od: gu:=expand(gu): if type(gu,`+`) then for j from 1 to nops(gu) do mu:=op(j,gu): a:=[]: for i from 1 to k do a:=[op(a),degree(mu,x[i])]: od: beseder:=1: for i from 1 to k do if not a[i]>=k-i+1 then beseder:=0: fi: od: if beseder=1 then S12121(k,n,a): fi: od: else mu:=gu: a:=[]: for i from 1 to k do a:=[op(a),degree(gu,x[i])]: od: beseder:=1: for i from 1 to k do if not a[i]>=k-i+1 then beseder:=0: fi: od: if beseder=1 then S12121(k,n,a): fi: fi: end: S12122:=proc(k,n) local a,gu,i,gu1,j,mu,beseder,beseder1: #gu is the generating poly for all monomials in n>=a_1 >= ... a_k>=1 #and a[1]>=k, a[2]>=k-1, ... a[i]>=k-i+1 , a[k]>=1 if not n>=k then ERROR(`The input is not applicable to (sub)^3lemma 1.2.1.2`): fi: gu:=1: mu:=1: for i from 1 to k do mu:=mu*x[i]: gu:=gu*x[i]/(1-mu): od: for i from 1 to k do gu:=taylor(gu,x[i],n+1): gu1:=0: for j from 1 to n do gu1:=gu1+coeff(gu,x[i],j)*x[i]^j: od: gu:=gu1: od: gu:=expand(gu): if type(gu,`+`) then for j from 1 to nops(gu) do mu:=op(j,gu): a:=[]: for i from 1 to k do a:=[op(a),degree(mu,x[i])]: od: beseder:=1: for i from 1 to k do if not a[i]>=k-i then beseder:=0: fi: od: if beseder=1 then beseder1:=0: for i from 1 to k do if a[i]=k-i then beseder1:=1: fi: od: if beseder1=1 then print(`H(`,k,n,a,`)=`,H(k,n,a)): fi: fi: od: else mu:=gu: a:=[]: for i from 1 to k do a:=[op(a),degree(gu,x[i])]: od: beseder:=1: for i from 1 to k do if not a[i]>=k-i+1 then beseder:=0: fi: od: if beseder=1 then beseder1:=0: for i from 1 to k do if a[i]=k-i then beseder1:=1: fi: od: if beseder1=1 then print(`H(`,k,n,a,`)=`,H(k,n,a)): fi: fi: fi: end: S1521:=proc(k) local gu: if k<2 then ERROR(`k should be >=2`): fi: gu:=subs(x[1]=1/x[2],Omegak(k)): gu:=expand(gu): print(`The quantity in subsubsublemma 1.5.2.1, when k=`,k,`is:`): print(gu): print(`Its high-degree in x[2], which better be <=`,k-2,` is`): print(degree(gu,x[2])): print(`Its low-degree in x[2], which better be >=`,-(k-2),` is`): print(ldegree(gu,x[2])): end: S1522:=proc(k) local lu,j,gu: if k<3 then ERROR(`For k<3, subsubsublemma 1.5.2.2 is satisfied vacuously`): fi: gu:=x[2]^(k-2)*subs(x[1]=1/x[2],Omegak(k)): for j from 3 to k do lu:=normal(subs(x[2]=1-1/x[j],gu)): print(`When`, x[2]=1-1/x[j],` is substituted into the expression of`): print(` subsubsublemma 1.5.2.2, then the result is:`): print(lu): od: end: S15221:=proc() local r,sigma, gu,lis,i1,i2,i3,eps: gu:=(1-x[1]*(1-x[2]))*(1-(1-x[1])*(1-x[2]))* (1-x[1]*(1-x[3]))*(1-(1-x[1])*(1-x[3]))* (1-x[2]*(1-x[3]))*(1-(1-x[2])*(1-x[3])): lis:=permute(3): for r from 1 to nops(lis) do sigma:=op(r,lis): lu1:=actpi(gu,sigma): print(`When the permutation sigma is`,sigma); for i1 from 0 to 1 do for i2 from 0 to 1 do for i3 from 0 to 1 do eps:=[(-1)^i1,(-1)^i2,(-1)^i3]: print(`When the signed-permutation epsilon is`,eps,`Then the result`): print(`of plugging in `,x[1]=1/x[2], x[3]=1/(1-x[2]),`is:`): lu2:=acteps(lu1,eps): lu2:=normal(subs({x[1]=1/x[2],x[3]=1/(1-x[2])},lu2)): print(lu2): od: od: od: od: end: S1523:=proc(k) local lu,j,gu,gu1: if k<1 then ERROR(`k must be >=1`): fi: gu:=Omegak(k): gu1:=subs({x[k]=0},gu): lu:=Omegak(k-1): print(`The left side of identity (Walt) of subsubsublemma 1.5.2.3 is`): print(gu1): print(`The right side of identity (Walt) of subsubsublemma 1.5.2.3 is`): print(lu): print(`The difference is`,expand(gu1-lu)): gu1:=subs({x[k]=1},gu): print(`The left side of identity (\bar Leon) of subsubsublemma 1.5.2.3 is`): print(gu1): print(`The right side of identity (\bar Leon) of subsubsublemma 1.5.2.3 is`): print(lu): print(`The difference is`,expand(gu1-lu)): end: S1:=proc(k,n): print(`When k=`,k,`and n=`,n,`The number of n by k Magog trapezoids are`): print(b(k,n)): print(`and the number of n by k Gog trapezoids are`): print(m(k,n)): end: Deltaz:=proc(k) local gu,i,j: gu:=1: for i from 1 to k do gu:=gu*(1-2*z[i]): od: for i from 1 to k do for j from i+1 to k do gu:=gu*(z[j]-z[i])*(z[j]+z[i]-1): od: od: gu: end: S1311:=proc(k,R) local gu,i,gu1: if not (R>=1 and R<=k) then ERROR(`R must be in [1,k]`): fi: gu:=Deltaz(k): gu:=subs(z[R]=x[R],gu): for i from 1 to R-1 do gu:=gu/(1-z[i]*x[R]): od: for i from R+1 to k do gu:=gu/(1-z[i]*x[R]): od: gu:=convert(gu,parfrac,x[R]): gu1:=0: for i from 1 to nops(gu) do gu1:=gu1+factor(op(i,gu)): od: print(`The partial fraction decomposition of the left side of (Tamar)`): print(`in Subsubsublemma 1.3.1.1 is`): print(gu1): gu1: end: S1311inter:=proc(k,R) local gu,i,gu1: if not (R>=1 and R<=k) then ERROR(`R must be in [1,k]`): fi: gu:=Deltaz(k): gu:=subs(z[R]=x[R],gu): for i from 1 to R-1 do gu:=gu/(1-z[i]*x[R]): od: for i from R+1 to k do gu:=gu/(1-z[i]*x[R]): od: gu:=convert(gu,parfrac,x[R]): gu1:=0: for i from 1 to nops(gu) do gu1:=gu1+factor(op(i,gu)): od: gu1: end: S13111:=proc(k,R,i) local gu1,gu2,j: if not (k>=1 and R>=1 and R<=k and i>=1 and i<=k and R<>i ) then ERROR(`Unacceptable input`): fi: print(`Empricial verification of (Sub)^4lemma 1.3.1.1.1. When k=`,k,`R=`,R): print(`and i=`,i): gu1:=Delta(k): gu1:=normal(subs(x[R]=1/x[i],gu1)): gu2:=Deltaz(k-2): if iR then for j from 1 to R-1 do gu2:=subs(z[j]=x[j],gu2): od: for j from R to i-2 do gu2:=subs(z[j]=x[j+1],gu2): od: for j from i-1 to k-2 do gu2:=subs(z[j]=x[j+2],gu2): od: gu2:=gu2*(x[i]-2)*(1-2*x[i])*(1-x[i]^2)*(1-x[i]*(1-x[i]))/x[i]^(2*k-1): fi: for j from 1 to k do if j<>i and j<>R then gu2:=gu2*(1-x[i]*x[j])*(1-x[i]*(1-x[j]))*(x[j]-x[i])*(x[j]+x[i]-1): fi: od: print(`By W(B_k) anti-symmetry, we can take z[i]=x[i]`): print(`The left side of Eq. (1.3.1.1.1) in Subsubsubsublemma 1.3.1.1.1 is:`): print(factor(gu1)): print(`The right side of Eq. (1.3.1.1.1) in Subsubsubsublemma 1.3.1.1.1 is:`): print(factor(gu2)): print(`Their ratio is`): print(normal(gu1/gu2)): end: S1312:=proc(k,n,eps,R) local gu1,gu,i,r,s,ma,kak: print(`Empirical verification of subsubsublemma 1.3.1.2 when eps=`,eps): print(`and when k=`,k,`,n=`,n,`and R=`,R): print(`The following is Eq. (Celia) but with "place-holders" ma[i]`): if op(R,eps)=-1 then ERROR(`eps[`,R,`] must be +1`): fi: gu1:=S1311inter(k,R): gu:=0: kak:=nops(gu1): for i from 1 to nops(gu1) do gu:=gu+ma[i]*factor(op(i,gu1)): od: gu:=gu/x[R]^(n+k-R)/(1-x[R])^(n+k+1): for j from 1 to k do if j<>R then gu:=gu/z[j]^(n+k-j)/(1-z[j])^(n+k+1): fi: od: for r from 1 to k do for s from r+1 to k do if r<>R and s<>R then gu:=gu/(1-z[r]*z[s]): fi: od: od: for i from 1 to k do if i<>R and op(i,eps)=1 then gu:=subs(z[i]=x[i],gu): elif i<>R and op(i,eps)=-1 then gu:=subs(z[i]=1-x[i],gu): fi: od: gu:=expand(gu): gu1:=0: for i from 1 to kak do gu1:=gu1+ma[i]*factor(coeff(gu,ma[i],1)): od: gu1: end: S1312inter:=proc(k,n,eps,R) local gu1,gu,i,r,s,ma,kak: gu1:=S1311inter(k,R): gu:=0: kak:=nops(gu1): for i from 1 to nops(gu1) do gu:=gu+ma[i]*factor(op(i,gu1)): od: gu:=gu/x[R]^(n+k-R)/(1-x[R])^(n+k+1): for j from 1 to k do if j<>R then gu:=gu/z[j]^(n+k-j)/(1-z[j])^(n+k+1): fi: od: for r from 1 to k do for s from r+1 to k do if r<>R and s<>R then gu:=gu/(1-z[r]*z[s]): fi: od: od: for i from 1 to k do if i<>R and op(i,eps)=1 then gu:=subs(z[i]=x[i],gu): elif i<>R and op(i,eps)=-1 then gu:=subs(z[i]=1-x[i],gu): fi: od: gu:=expand(gu): gu1:=0: for i from 1 to kak do gu1:=gu1+ma[i]*factor(coeff(gu,ma[i],1)): od: gu1: end: S1313S1314:=proc(k,n) local reshsign,reshper,pi,eps,i,j,i1,eps1,R,DAVE,DAVE1: print(`This procedure, S1313S1314, simultaneoulsy verifies subsubsublemmas`): print(`S1313 and S1314, by taking the parts of Eq. (Celia), "marking them"`): print(`and otherwise doing the same as in S131`): print(`For k=`,k,`and n=`,n): reshper:=permute(k): reshsign:=allsigns(k): for i from 1 to nops(reshper) do pi:=op(i,reshper): mu:=[seq(x[op(i1,pi)],i1=1..k)]: print(`When pi is`,pi): for j from 1 to nops(reshsign) do eps:=op(j,reshsign): print(`and when eps is`,eps): for i1 from 1 to k while op(op(i1,pi),eps)=1 do od: R:=i1: if R<=k then DAVE:=S1312inter(k,n,eps,R): print(`The left side of the identity of subsubsublemmas 1.3.1.3`): print(`and 1.3.1.4 combined, with the markers ma[i] is`): print(IterRes(DAVE,mu)): DAVE1:=subs(x[R]=1-x[R],DAVE): print(`while its right side of is`): print(IterRes(DAVE1,mu)): fi: od: od: end: S1313:=proc(k,n): S1313S1314(k,n): end: S1314:=proc(k,n): S1313S1314(k,n): end: S141:=proc(k,n) local reshsign,reshper,pi,eps,i,j,i1,eps1: reshper:=permute(k): reshsign:=allsigns(k): for i from 1 to nops(reshper) do pi:=op(i,reshper): mu:=[seq(x[op(i1,pi)],i1=1..k)]: print(`When pi is`,pi): for j from 1 to nops(reshsign) do eps:=op(j,reshsign): print(`and when eps is`,eps): for i1 from 1 to k while op(op(i1,pi),eps)=1 do od: print(`then the altered eps, featuring on the left of S1.4.1 is`): if i1<=k then eps1:=[op(1..i1-1,eps),1,op(i1+1..k,eps)]: print(eps1): print(`The left side of the identity of subsublemma 1.4.1 is`): print(IterRes(acteps(Fnk(k,n),eps1),mu)): print(`while its right side of is`): print(IterRes(acteps(Fnk(k,n),eps),mu)): fi: od: od: end: Phiz:=proc(k) local gu,i: gu:=Phi(k): for i from 1 to k do gu:=subs(x[i]=z[i],gu): od: gu: end: S1411:=proc(k,R) local gu,i,gu1: if not (R>=1 and R<=k) then ERROR(`R must be in [1,k]`): fi: gu:=Phiz(k): gu:=subs(z[R]=x[R],gu): for i from 1 to R-1 do gu:=gu/(1-z[i]*x[R])/(1-(1-z[i])*x[R]): od: for i from R+1 to k do gu:=gu/(1-z[i]*x[R])/(1-z[i]*(1-x[R])): od: gu:=convert(gu,parfrac,x[R]): gu1:=0: for i from 1 to nops(gu) do gu1:=gu1+factor(op(i,gu)): od: print(`The partial fraction decomposition of the left side of (Tamar)`): print(`in Subsubsublemma 1.4.1.1 is`): print(gu1): gu1: end: S1411inter:=proc(k,R) local gu,i,gu1: if not (R>=1 and R<=k) then ERROR(`R must be in [1,k]`): fi: gu:=Phiz(k): gu:=subs(z[R]=x[R],gu): for i from 1 to R-1 do gu:=gu/(1-z[i]*x[R])/(1-(1-z[i])*x[R]): od: for i from R+1 to k do gu:=gu/(1-z[i]*x[R])/(1-z[i]*(1-x[R])): od: gu:=convert(gu,parfrac,x[R]): gu1:=0: for i from 1 to nops(gu) do gu1:=gu1+factor(op(i,gu)): od: gu1: end: S14111:=proc(k,R,i) local gu1,gu2,j: if not (k>=1 and R>=1 and R<=k and i>=1 and i<=k and R<>i ) then ERROR(`Unacceptable input`): fi: print(`Empricial verification of (Sub)^4lemma 1.4.1.1.1. When k=`,k,`R=`,R): print(`and i=`,i): gu1:=Phi(k): gu1:=normal(subs(x[R]=1/x[i],gu1)): gu2:=Phiz(k-2): if iR then for j from 1 to R-1 do gu2:=subs(z[j]=x[j],gu2): od: for j from R to i-2 do gu2:=subs(z[j]=x[j+1],gu2): od: for j from i-1 to k-2 do gu2:=subs(z[j]=x[j+2],gu2): od: gu2:=gu2*(x[i]-2)*(1-2*x[i])*(1-x[i]^2)*(1-x[i]*(1-x[i]))/x[i]^(3*k-3): fi: for j from 1 to k do if j<>i and j<>R then gu2:=gu2*(1-x[i]*x[j])* (1-(1-x[i])*x[j])*(1-x[i]*(1-x[j]))*(1-(1-x[i])*(1-x[j]))* (x[j]-x[i])*(x[j]+x[i]-1): fi: od: print(`By W(B_k) anti-symmetry, we can take z[i]=x[i]`): print(`The left side of Eq. (1.4.1.1.1) in Subsubsubsublemma 1.4.1.1.1 is:`): print(factor(gu1)): print(`The right side of Eq. (1.4.1.1.1) in Subsubsubsublemma 1.4.1.1.1 is:`): print(factor(gu2)): print(`Their ratio is`): print(normal(gu1/gu2)): end: S1412:=proc(k,n,eps,R) local gu1,gu,i,r,s,ma,kak: print(`Empirical verification of subsubsublemma 1.4.1.2 when eps=`,eps): print(`and when k=`,k,`,n=`,n,`and R=`,R): print(`The following is Eq. (Celia) but with "place-holders" ma[i]`): if op(R,eps)=-1 then ERROR(`eps[`,R,`] must be +1`): fi: gu1:=S1411inter(k,R): gu:=0: kak:=nops(gu1): for i from 1 to nops(gu1) do gu:=gu+ma[i]*factor(op(i,gu1)): od: gu:=gu/x[R]^(n+1)/(1-x[R])^(n+R+1): for j from 1 to k do if j<>R then gu:=gu/z[j]^(n+1)/(1-z[j])^(n+j+1): fi: od: for r from 1 to k do for s from r+1 to k do if r<>R and s<>R then gu:=gu/(1-z[r]*z[s])/(1-(1-z[r])*z[s]): fi: od: od: for i from 1 to k do if i<>R and op(i,eps)=1 then gu:=subs(z[i]=x[i],gu): elif i<>R and op(i,eps)=-1 then gu:=subs(z[i]=1-x[i],gu): fi: od: gu:=expand(gu): gu1:=0: for i from 1 to kak do gu1:=gu1+ma[i]*factor(coeff(gu,ma[i],1)): od: gu1: end: S1412inter:=proc(k,n,eps,R) local gu1,gu,i,r,s,ma,kak: gu1:=S1411inter(k,R): gu:=0: kak:=nops(gu1): for i from 1 to nops(gu1) do gu:=gu+ma[i]*factor(op(i,gu1)): od: gu:=gu/x[R]^(n+1)/(1-x[R])^(n+R+1): for j from 1 to k do if j<>R then gu:=gu/z[j]^(n+1)/(1-z[j])^(n+j+1): fi: od: for r from 1 to k do for s from r+1 to k do if r<>R and s<>R then gu:=gu/(1-z[r]*z[s])/(1-(1-z[r])*z[s]): fi: od: od: for i from 1 to k do if i<>R and op(i,eps)=1 then gu:=subs(z[i]=x[i],gu): elif i<>R and op(i,eps)=-1 then gu:=subs(z[i]=1-x[i],gu): fi: od: gu:=expand(gu): gu1:=0: for i from 1 to kak do gu1:=gu1+ma[i]*factor(coeff(gu,ma[i],1)): od: gu1: end: S1413to6:=proc(k,n) local reshsign,reshper,pi,eps,i,j,i1,eps1,R,DAVE,DAVE1: print(`This procedure, S1413to6, simultaneoulsy verifies subsubsublemmas`): print(`1.4.1.[3,4,5,6] by taking the parts of Eq. (Celia), "marking them"`): print(`and otherwise doing the same as in S141`): print(`For k=`,k,`and n=`,n): reshper:=permute(k): reshsign:=allsigns(k): for i from 1 to nops(reshper) do pi:=op(i,reshper): mu:=[seq(x[op(i1,pi)],i1=1..k)]: print(`When pi is`,pi): for j from 1 to nops(reshsign) do eps:=op(j,reshsign): print(`and when eps is`,eps): for i1 from 1 to k while op(op(i1,pi),eps)=1 do od: R:=i1: if R<=k then DAVE:=S1412inter(k,n,eps,R): print(`The left side of the identity of subsubsublemmas 1.4.1.[3-6]`): print(` with the markers ma[i] is`): print(IterRes(DAVE,mu)): DAVE1:=subs(x[R]=1-x[R],DAVE): print(`while its right side of is`): print(IterRes(DAVE1,mu)): fi: od: od: end: S1413:=proc(k,n): S1413to6(k,n): end: S1414:=proc(k,n): S1413to6(k,n): end: S1415:=proc(k,n): S1413to6(k,n): end: S1416:=proc(k,n): S1413to6(k,n): end: yafe:=proc(li) local i: for i from 1 to nops(li) do lprint(op(i,li)): od: end: DECSEQ:=proc(k,n) local gu,gu1,i1: option remember: if n=1 and k=1 then RETURN({[1]}): fi: if k=0 and n>=1 then RETURN({[]}): fi: if n<1 or k<1 then RETURN({}): fi: gu:=DECSEQ(k,n-1): gu1:=DECSEQ(k-1,n): for i1 from 1 to nops(gu1) do gu:=gu union {[n,op(op(i1,gu1))]}: od: gu: end: DECSEQ0:=proc(k,n) local gu,gu1,i1: option remember: if n=0 and k=1 then RETURN({[0]}): fi: if k=0 and n>=1 then RETURN({[]}): fi: if n<0 or k<1 then RETURN({}): fi: gu:=DECSEQ0(k,n-1): gu1:=DECSEQ0(k-1,n): for i1 from 1 to nops(gu1) do gu:=gu union {[n,op(op(i1,gu1))]}: od: gu: end: LOGOG:=proc(k,n) local gu,gu1,i,i1,vec,nakh: if not k>=1 or not n>=k then RETURN({}): fi: gu1:=DECSEQ(k,n): gu:={}: for i from 1 to nops(gu1) do vec:=op(i,gu1): nakh:=1: for i1 from 1 to k do if not op(i1,vec)>=k-i1+1 then nakh:=0: exit: fi: od: if nakh=1 then gu:=gu union {vec}: fi: od: gu: end: ELOGOG:=proc(k,n) local gu,gu1,i,i1,vec,nakh: if not k>=1 or not n>=k then RETURN({}): fi: gu1:=DECSEQ0(k,n+1): gu:={}: for i from 1 to nops(gu1) do vec:=op(i,gu1): nakh:=1: if op(1,vec)=n+1 and op(2,vec)>n then nakh:=0: fi: if op(1,vec)=n and n=k and op(2,vec)=k then nakh:=0: fi: for i1 from 1 to k do if not op(i1,vec)>=k-i1 then nakh:=0: exit: fi: od: if nakh=1 then gu:=gu union {vec}: fi: od: gu: end: #Tkn gives the set T_k(n;a), where a=[a_1, ..., a_k] defined in the #proof of 1.2.1.1 Tkn:=proc(k,n,a) local nakh,i1,b,i,gu,mu: mu:=DECSEQ(k,n-1): gu:={}: for i from 1 to nops(mu) do b:=op(i,mu): nakh:=1: for i1 from 1 to 1 do if not ( k-i1+1<=op(i1,b) and op(i1,b)<=op(i1,a) ) then nakh:=0: fi: od: for i1 from 2 to k do if not ( k-i1+1<=op(i1,b) and op(i1,b)<=min( op(i1,a),op(i1-1,a)-1 ) ) then nakh:=0: fi: od: if nakh=1 then gu:=gu union {b}: fi: od: gu: end: #GOGa(k,n,a) gives the set of k by n Gog-trapezoids such that #the rightmost border is the vector a GOGa:=proc(k,n,a) local pip,kvu,firow,b,mu,gu,i,j,l,trap,trap1: if not k>=1 or not n>=k or not nops(a)=k then ERROR(`Improper intput`): fi: if n=k and k=1 then if not op(1,a)=1 then RETURN({}): else RETURN({[[1]]}): fi: fi: if n=k then if not op(1,a)=k then ERROR(`Wrong input`): fi: mu:=GOGa(k-1,k,[op(2..k,a)]): gu:={}: for i from 1 to nops(mu) do trap1:=op(i,mu): firow:=op(1,trap1): gu:=gu union {[[op(firow),k],op(2..k,trap1)]}: od: RETURN(gu): fi: gu:={}: kvu:=Tkn(k,n,a): for pip from 1 to nops(kvu) do b:=op(pip,kvu): mu:=GOGa(k,n-1,b): for j from 1 to nops(mu) do trap:=op(j,mu): trap1:=[op(1..n-k,trap)]: for l from n-k+1 to n-1 do trap1:=[op(trap1),[op(op(l,trap)),op(l-(n-k),a)]]: od: trap1:=[op(trap1),[op(k,a)]]: gu:=gu union {trap1}: od: od: gu: end: GOG:=proc(k,n) local i,gu,lu: lu:=LOGOG(k,n): gu:={}: for i from 1 to nops(lu) do gu:=gu union GOGa(k,n,op(i,lu)): od: gu: print(`The number of Gog Trapezoids with k=`,k,`and n=`,n,`equals`,nops(gu)): print(`Here they all are`): for i from 1 to nops(gu) do yafe(op(i,gu)): lprint(``): od: gu: end: GOGset:=proc(k,n) local i,gu,lu: lu:=LOGOG(k,n): gu:={}: for i from 1 to nops(lu) do gu:=gu union GOGa(k,n,op(i,lu)): od: gu: gu: end: GOGTOASM:=proc(mt) local k,mat,mat1,ro,i,j: k:=nops(mt): mat:=array(1..k,1..k): mat1:=array(1..k,1..k): for i from 1 to k do for j from 1 to k do mat[i,j]:=0: od: od: for i from 1 to k do ro:=op(i,mt): for j from 1 to nops(ro) do mat[i,op(j,ro)]:=1: od: od: for i from 1 to k-1 do for j from 1 to k do mat1[i,j]:=mat[i,j]-mat[i+1,j]: od: for j from 1 to k do mat1[k,j]:=mat[k,j]: od: od: mat1: end: ASM:=proc(k) local i,gu,asm: gu:=GOGset(k,k): print(`There are`, nops(gu),`Alternating Sign Matrices of size`,k): print(`Here they all are:`): for i from 1 to nops(gu) do asm:=GOGTOASM(op(i,gu)): print(op(asm)): od: end: ASMs:=proc(k) local i,gu,asm: gu:=GOGset(k,k): {seq(op(GOGTOASM(op(i,gu))),i=1..nops(gu))}: end: LOMA:=proc(k,n) local gu,gu1,i,i1,vec,nakh: if not k>=1 or not n>=k then RETURN({}): fi: gu1:=DECSEQ(k,n): gu:={}: for i from 1 to nops(gu1) do vec:=op(i,gu1): nakh:=1: for i1 from 1 to k do if op(i1,vec)> n-i1+1 then nakh:=0: exit: fi: od: if nakh=1 then gu:=gu union {vec}: fi: od: gu: end: #MAGOG(k,n,a) gives the set of k by n Magog-trapezoids such that #the rightmost border is the vector a MAGOGa:=proc(k,n,a) local b,evar,mu,gu,i,i1,j,l,trap,trap1,bit: if not k>=1 or not n>=k or not nops(a)=k then ERROR(`Improper intput`): fi: if n=k and k=1 then if not op(1,a)=1 then RETURN({}): else RETURN({[[1]]}): fi: fi: if n=k then if not op(k,a)=1 then ERROR(`Wrong input`): fi: mu:=MAGOGa(k-1,k,[op(1..k-1,a)]): gu:={}: for i from 1 to nops(mu) do gu:=gu union {[op(op(i,mu)),[1]]}: od: RETURN(gu): fi: bit:=1: for i from 1 to k-1 do bit:=bit*x[i]^op(i+1,a)*normal((1-x[i]^(min(op(i,a),n-i)+1-op(i+1,a))) /(1-x[i])): od: bit:=bit*x[k]*normal((1-x[k]^(min(op(k,a),n-k)))/(1-x[k])): bit:=expand(bit): gu:={}: if not type(bit,`+`) then bit:=[bit]: fi: for i1 from 1 to nops(bit) do evar:=op(i1,bit): b:=[]: for i from 1 to k do b:=[op(b),degree(evar,x[i])]: od: mu:=MAGOGa(k,n-1,b): for j from 1 to nops(mu) do trap:=op(j,mu): trap1:=[]: for l from 1 to k do trap1:=[op(trap1),[op(op(l,trap)),op(l,a)]]: od: gu:=gu union {trap1}: od: od: gu: end: MAGOG:=proc(k,n) local i,gu,lu: lu:=LOMA(k,n): gu:={}: for i from 1 to nops(lu) do gu:=gu union MAGOGa(k,n,op(i,lu)): od: gu: print(`The number of Magog Trapezoids with k=`,k,`and n=`,n,`equals`,nops(gu)): print(`Here they all are`): for i from 1 to nops(gu) do yafe(op(i,gu)): lprint(``): od: gu: end: