The umbral transfer-matrix method IV. Counting self
Contents
1. APU LLER C C L 1 R 1 1 2 0 1 2 3 3 4 4 51 0 0 1 0 THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 10 is the pre Umbra car cae POPs Xo Pas 9X0 1 422 3 q 4 Poo q tt Pa q 21 922 3 q At the end we also set x9 1 and z4 1 Keeping Track of the Emerged Letter Each of the many Followers induces a clear cut SAP letter to the right so to keep track of it we will use yet another indexed variable Z EmergedLetter and write for example the Atomic Pre Umbra given above as at 23923 ZILLRR gt q 4 Pa q 1 922 3 q Z LLRR in this randomly chosen example the initial and final SAP letters coincided both being LLRR of course this is not generally the case At Long Last The Preumbra To get the action of the evolution Umbra on a generic monomial oft ga x37 Z LETTER we first find all the Followers of LETTER and for each and every one of them we compute the Atomic Pre Umbra and finally add all these atomic pre Umbras up Calling It Quits How to End a SAP We need one more letter END We can only end a SAP if the current letter is either LR or LLRR or LLRLRR and in general L LR R for s gt 1 Then we close all the odd numbered intervals and call it a sap Of course the function corresponding to END has 0 arguments and the q credit that it gets is g41 43 42 1_ When this is the case we add q41 43 42s 1 ZIEN D to2. 91 2000 451 463 Rota memorial issue Z2 Doron Zeilberger The Umbral Transfer Matrix Method II Counting Plane Partitions Personal Journal of Ekhad and Zeilberger http www math temple edu zeilberg pj html Z3 Doron Zeilberger The Umbral Transfer Matriz Method III Counting Ani mals submitted Available from http www math temple edu zeilberg papers1 html ZA Doron Zeilberger The Umbral Transfer Matriz Method IV Counting Self Avoiding Polygons and Walks this article Z5 Doron Zeilberger The Umbral Transfer Matriz Method V The Goulden Jackson Cluster Method for Infinitely Many Mistakes in preparation THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 17
3. closed up former L s and R s There are three legal moves i JoinLL obtained by joining two adjacent L s making them both C s and chang ing the R mate of the upper L into an L thereby preserving the balance of L s and R s For example there is only one way to apply a JoinLL operation to the SAP Umbral letter LLRR turning it into CCLR For LLLRRR there are two legal JoinLL operations THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 4 one obtained by joining the first 2 L s turning LLLRRR into CCLRLR and the other obtained by joining the second and third L getting LCCLRR We may apply as many JoinLL operations as we want as long as they don t interfere with each other ii JoinRR obtained by joining two adjacent R s making them both C s and changing the L mate of the lower R into an R hence preserving the balance of L s and R s For example there is only one way to apply a JoinRR operation to the SAP Umbral letter LLRR turning it into LRCC For LLLRRR there are two legal JoinRR operations one obtained by joining the first 2 R s turning LLLRRR into LLRCCR and the other obtained by joining the second and third R getting LRLRCC We may apply as many JoinRR operations as we want as long as they don t interfere with each other iii JoinRL obtained by joining an R to an L immediately above it and changing them both to C s This does not change any of the other L s or R s but th
4. families of convex polyominoes according to area width and perimeter 2 Use the methodology of Z3 and Z4 this paper to study toy models for the Ising model with magnetic field Percolation and other venerable models of statistical physics 3 One of the applications of an Umbral Scheme is to actually crank out numbers obtaining series expansions for the toy model that give lower bounds for the real thing For that application it seems wasteful to have the full Umbral Scheme since we only need to know the first prescribed terms of the Taylor expansions of the coefficients that feature in the scheme Adapt procedures SAPUmSc of USAP and SAWUmSc of USAW to find approximate schemes that will take advantage of the above observation and produce many more terms before running out memory 4 Translate everything to Fortran or C hopefully getting much more impressive output 5 Physicists are most interested in critical exponents Find an algorithm that inputs an Umbral Scheme and outputs the critical exponent for the desired generating function Appendix The Umbral Scheme For Saps With At Most 2 Horizontal Edges Per Vertical Cross Section The desired quantity is F3 AiQe s Hi e a Fo z e s q 1 7 1 Sa oe Ser Se a ND ARDS 1 qz xt q x q 1 qz Aala ea 2 1 x q 1 gz F3 Fo q F x pi THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 1
5. remaining open slots as long as the total number does not exceed the maximal allowed number r Of course these new pairs behave like the ones at the very beginning they come in adjacent LR pairs Also they may only be inserted in the open space intervals which consists of the complement of the second component of the PreFollower with respect to the set of all available intervals 0 1 1 2 2s 1 2s Bs 2841 Recall that a PreFollower is a list of length two A Follower will be a list of length four To construct the set of Followers stemming from a given PreFollower we retain the two components of the PreFollower To this we append a third component the list of available open intervals listed in the natural increasing order followed by another list that codes our decision where to insert new LR pairs as described below Consider for example the following PreFollower of LLRR C C L 1 LR 1 tf 213 obtained by performing a JoinLL operation The totality of intervals of the source SAP letter LLRR is the set 0 1 1 2 2 3 3 4 4 5 gt and removing the closed for traffic interval 1 2 gives us as the set of available intervals 0 1 2 3 3 4 4 51 but we store it as a list rather than a set so that we can refer to its entries conveniently THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 6 Since we are doing the language of SAP r i e saps
6. 6 The corresponding much larger output for at most 4 horizontal edges can be seen on the home page of Zeilberger http www math temple edu zeilberg REFERENCES B Mireille Bousquet M lou Rapport Scientifique pour obtenir l Habilation diriger des Recherches available from http dept info labri u bordeaux fr bousquet BGE R Brak A J Guttmann and I G Enting Exact solutions of the row conver polygon perimeter generating function J Phys A Math Gen 23 1990 2319 2326 DV M P Delest and G Viennot Algebraic languages and polyomino enumera tion Theoretical Computer Science 34 1984 169 206 SP N J A Sloane and S Plouffe The Encyclopedia of Integer Sequences Academic Press 1995 T H N V Temperley Combinatorial problems suggested by the statistical me chanics of domains and rubber like molecules Physical Review 103 1956 1 16 Wa M S Waterman Secondary structures of single stranded nucleic acids in Studies in the Foundation of Combinatorics v 1 167 212 1978 Wi Lauren K Williams Enumerating up side self avoiding walks on integer lat tices 10pp Electronic J Combinatorics 3 1996 R31 Z0 Doron Zeilberger Symbol Crunching with the Transfer Matriz Method in Order to Count Skinny Physical Creatures INTEGERS http www integers ejcnt org 0 A9 29 pages 2000 Z1 Doron Zeilberger The Umbral Transfer Matrix Method I Foundations J Comb Theory Ser A
7. 71 79 tv Summarizing the atomic pre Umbra in this no vertical dawdling case is 2s 1 Ga terre I Page es GPi Eip Monster i 0 Here we set Ap Ags41 00 Also later we will remove zo from the argument of Pa remove 2m from the argument of Pa and then set zo and z m to 1 since they contribute to the bottom and top infinite intervals that do not have x weight contribution For example APU LLIRR C C L 0 R O 1 2 0 1 2 3 3 4 4 51 0 0 1 0 is the pre Umbra regrei q tt Pa 20 Pa 20 Pa 0 Pag 21 482 3 Pa 24 Now we are ready to treat the Atomic Pre Umbra coming from the case where some or all the L s and R s of the PreFollower decide to wonder up or down on x k before venturing into x gt k Suppose that the horizontal edge consisting of the bottom of the interval whose length is A is an L or R that goes down denoted by L 1 or R 1 in the first component of the PreFollower This means that the interval of the source LETTER immediately below it of length A _1 gets to overlap A s bottom interfaced successor SAP letter interval 7 In other words A is generous and shares its bottom THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 9 interfaced interval with its neighbor below Not only that A _ gets q credit So if this is the case in Monster we have to replace Qi 1 p _4 1 f Gi 1 1 gt Pai 8g 59 s sn Dini
8. K C C L 1 R 1 11 21 0 1 2 3 3 4 4 5 0 0 0 0 as is C C L 1 R 1 11 21 0 1 2 3 3 4 4 5 0 0 1 0 where we inserted only one new LR pair between the L and the R of the PreFollower The total number of Followers stemming from the above PreFollower still with r 3 is the number of vectors of non negative integers a1 a2 a3 a4 with a a2 a3 a4 lt 2 The Emerged Letter It soon becomes very clear that there are lots of ways to continue a given SAP letter from one vertical cross section to the next but many different continuations will produce the same SAP letter in the next vertical cross section To find the induced letter simply ignore the C s and take note of the newly inserted LR pairs Hence the following Follower of LLRR C C L 1 R 11 tft 21 10 1 2 3 3 4 4 51 0 0 1 0 THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 7 gives rise to the letter LLRR while IC C Z 1 R 11 1 21 10 1 2 3 3 4 4 51 0 0 0 2 gives rise to LRLRLR etc A Very Important Polynomial In This Algorithm Let A be a symbol denoting an integer and let 21 z2 Zm be variables we let 41 12 Palai esestm Zi Zg tt 5 where the sum extends over all m tuples of positive integers i1 im satisfying i im A Note that Pa z1 2 m 21 2mha m 21 m where h is the usual complete homoge
9. R or LRER up to DR ie LR for s 1 r Since for the leftmost vertical cross section 0 lt x lt 1 the only way that two paired edges can reach each other from the left is via the vertical line x 0 hence every such LR pair must be adjacent Now these leftmost letters can be of arbitrary size If the immediate follower of START is LR then its generic x weight is 2 aes But the first L is connected on x 0 to the first R contributing a stretch of A to the perimeter the second L is connected to the second R contributing As to the perimeter etc In addition the 2s horizontal edges joining x 0 and x 1 contribute 2s to the perimeter Hence we have that the pre umbra acting on START is Z START Pel Fig se Rak 1 qv 1 qzv 1 2 21 q 3 2r q T2 qT3 L2r 2 Gv 2r 1 ae Z LR 1 qz 1 z2 1 qz3 1 Zz r 2 1 qhar 1 i There Are Many Ways to Continue to the Next Vertical Cross Section The continuation from one vertical cross section say k 1 lt x lt k to the next k lt a lt k 1 takes place in three phases Phase I The PrePreFollowers Suppose that the pattern of the horizontal edges in the vertical cross section k 1 lt x lt kis a certain legal L R word It may be continued in many ways The first phase is to decide how to unite some of L s and R s by joining them on x k thereby creating new vertical edges We will denote by C these
10. S3 SAPUmSc 3 x q is still feasible but frankly I doubt whether it is worth the effort The most important point is that there exists a program that can generate at least in principle a polynomial time in n scheme for enumerating saps with at most 2r horizontal edges per vertical cross section with perimeter lt n for any fixed given r So what if the polynomial is so big as to make it impractical I will be very impressed if you can just write a program for Satisfiability that takes O n1000000000000000 time and memory I am not asking for sample output Self Avoiding Walks A self avoiding walk henceforth saw on the square lattice is a finite connected induced subgraph of the square lattice with two vertices of degree 1 and all the other vertices of degree 2 Of course we identify two saws that are translations of each other Note that except for the length 0 saw every one of our saws gives rise to two usual saws since it can be walked in two opposite directions and here we identify them making a saw a static object The analogous program US AW for self avoiding walks is much more complicated but goes along the same lines Just as in Z0 the SAW alphabet consists in addition to the SAP alphabet letters obtained from them by inserting one or two A s denoting the open ends The three phases of following PrePreFollower PreFollower and Follower still hold but there are many more possibilities because o
11. The umbral transfer matrix method IV Counting self avoiding polygons and walks Doron ZEILBERGER lt zeilberg math temple edu gt Submitted March 13 2001 Accepted July 26 2001 MR Subject Classifications 05A To think in a computerized way is an important matter to go with it to the end of the limit of possibilities and there to develop new unpredictable ones David Avidan Free translation of an excerpt from the Hebrew original of Avidan s poem lakhshov betsura memukhshevet To Think In a Computerized Way Abstract This is the fourth installment of the five part saga on the Umbral Transfer Matrix method based on Gian Carlo Rota s seminal notion of the umbra In this article we describe the Maple packages USAP USAW and MAYLIS USAP automati cally constructs for any specific r an Umbral Scheme for enumerating according to perimeter the number of self avoiding polygons with lt 2r horizontal edges per ver tical cross section The much more complicated USAW does the analogous thing for self avoiding walks Such Umbral Schemes enable counting these classes of self avoiding polygons and walks in polynomial time as opposed to the exponential time that is re quired by naive counting Finally MAYLIS is targeted to the special case of enumerating classes of saps with at most two horizontal edges per vertical cross section equivalently column convex polyominoes by perimeter and related classes In this computationally t
12. US1 q 20 x 1 and ApplyUmSc SAPUS2 q 20 x 1 x 2 x 3 Typing ApplyUmSc SAPUS2 q 44 x 1 x 2 x 3 and waiting for a few days computes the sequence of self avoiding polygons with at most 4 horizontal edges per vertical cross section to 21 terms i e the number of such saps with perimeter up to 44 This sequence was not in Neil Sloane and Simon Plouffe s Encyclopedia SP and we reported it for inclusion in Sloane s database The sequence starts with THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 12 1 2 7 28 124 588 2938 15266 81770 448698 2510813 14277838 82286365 479610362 2822332127 16745262798 100058822258 601588809890 3636591773529 22088370875438 134733261281038 It fits between M1779 the sequence for ApplyUmSc SAPUS1 q n x 1 first introduced by Temperley T and M1780 the exponentially difficult enumerating se quence for all saps It s Not My Fault That It is Sooo COMPLICATED Even For a Com puter USAP can in principle find an Umbral Scheme for the class of saps with at most 2r horizontal edges per vertical cross section for any fixed but arbitrary r But the number of interfaces grows so fast with r that Maple ran out of memory even for the case r 3 In other words it refused to perform the command SAPUS3 SAPUmSc 3 x q I am almost sure that with a more careful implementation and or by transport ing to numeric programming languages such as C SAPU
13. What makes this third way of using Maple so hard at present is that Maple is really geared to be used interactively We need higher and higher level program ming languages that would make the Maple packages described in this article look like assembly language code Hence perhaps the most important potential impact of this modest effort is as a guide for these future super Maple designers THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 2 Required Reading The reader is expected to be familiar with Z1 It would also help to read the parts of Z0 concerned with finding generating functions for counting self avoiding polygons and walks with vertical cross sections of bounded width The present treatment is inspired by the finite case described in detail in Z0 but with the Umbral twist getting matrices whose entries are operators rather than mere polynomials as transfer matrices The Alphabet For Self Avoiding Polygons A self avoiding polygon henceforth sap on the square lattice is a finite connected induced subgraph of the square lattice with every vertex having degree 2 Of course we identify two saps that are translations of each other From now on we will take the smallest x coordinate of any of the lattice points participating in the sap to be 0 We may also take the smallest y coordinate to be 0 but this is irrelevant to our approach We can read a sap from left to right by considering for k 0 1 2 the ed
14. e the so called vertically convex animals according to perimeter Unlike Z0 where we also restricted the width of the cross sections and hence always obtained rational generating functions because of the finite Markovity now we allow arbitrary width and the transfer matrices will contain Rota operators rather than mere polynomials The size of the alphabet for saps with at most r L R pairs is C1 C2 Cr where C 2 2i 1 are the Catalan numbers For example where r 1 we only have one letter LR while when r 2 the alphabet is LR LRLR LLURR when r 3 it is LR LRLR LURR LRLRLR LRLLRR LLRRLR LLRLRR LLLRRR etc THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 3 The Umbral Letters for SAPs However each of these letters is really a parameterized family of letters For a letter with s L R pairs 1 lt s lt r there are 2s 1 gaps between the edges and we will denote the generic lengths of these gaps by A1 2 A9s 1 The corresponding zx weight of such a letter is the generic monomial x23 a Note that the x s are but catalytic variables and we will soon also introduce q to keep track of the perimeter The Leftmost Letters For SAPs In addition to the above introduced genuine letters it will be convenient to intro duce two extra letters START and END depending on no z variables i e they only depend on q The first letter right after the fictitious START may be L
15. e widowers of the deceased R and L now are married to each other For example there is only one way to perform a JoinRL operation to the SAP letter LRLR resulting in LCCR while for LRLRLR we may get LCCRLR and LRLCCR If we operate on both adjacent RL pairs we get LCCCCR To get all the PrePreFollowers of a given SAP letter we apply JoinLL JoinRR and JoinRL in any conceivable order except that right now we want to leave at least one LR pair and not turn them all to C s For example the set of PrePreFollowers of LRLLRR is LRCCLR LRLRCC LCCLRR For future reference we also need to record those portions of x k that have been closed to traffic because of the above joining operations If the input SAP letter i e the one whose continuations we are investigating has s LR pairs and hence 2s L s and R s combined let s number them by the integers 1 through 2s and denote the resulting consecutive intervals by 0 1 1 2 2 3 2s 1 2s 2s 2s 1 Here 0 1 and 2s 2s 1 are the infinite intervals below the bottom L and above the top R respectively Now some of these intervals are currently closed for business because of the joining operation and we need to record it The full PrePreFollower also records this information Hence the set of PrePreFollowers of LRLLRR are LRCC LR 8 4 LRLIRCC 5 6 LCCLRR 2 3 I apologize for the redundant information but
16. edges per vertical cross section It does not require the Maple package ROTA described in Z1 since all the necessary procedures of the latter were transported The main procedures of USAP are SAPUmSc and ApplyUmSc If you want to get the Umbral Scheme for enumerating SAPs with lt 2r horizontal edges on each ver tical cross section type SAPUSr SAPUmSc r x q Here r is a specific positive in teger r 1 2 while x is an indexed variable name that will carry the lengths of the intervals between consecutive horizontal edges and q is the variable of in terest that carries the perimeter For example SAPUS1 SAPUmSc 1 x q and SA PUS2 SAPUmSc 2 x q give the Umbral Schemes for r 1 and r 2 respectively Unfortunately the case r 3 would have to wait for a bigger computer and or a more efficient implementation since our computers ran out of memory Since comput ing SAPUS2 SAPUmSc 2 x q takes awhile I decided to include the pre computed SAPUS2 Thus typing SAPUS2 would display it So see it in humanese type YafeUmSc SAPUS2 F D For the sake of completeness I also included SAPUS1 even though it is instantaneous Once Maple gave you the Umbral Scheme SAPUS1 and SAPUS2 to get the first n 2 1 terms in the enumerating sequence what physicists call series expansions type ApplyUmSc SAPUSr g n var where var is the set of catalytic variables x 1 x 2 2 2 r 1 For example try ApplyUmSc SAP
17. f the open ends We urge the reader to carefully study the source code of USAW We omit the hu manese narrative since the readers should be able to figure everything out by them selves Note that USAW is an adaptation of USAP and all the main procedures of the latter except for the principal SAWUmSc have the name of their USAP counterparts with a W attached For example FollowersW is the SAW adaptation of USAP s Followers THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 13 A User s Manual For The Maple package USAW The main procedure of USAW is SAWUmSc If you want to get the Umbral Scheme for enumerating SAWs with lt r L R pairs on each vertical cross section and zero one or two A s for the open ends type SAWUSr SAWUmSc r x q Here r is a specific non negative integer r 0 1 2 while x is an indexed variable name that will carry the lengths of the intervals between consecutive horizontal edges and q is the variable of interest that carries the length For example SAWUSO SAWUmSc 0 x q gives the Umbral Scheme for enumerating initially East bound saws with at most one U turn in the East West direction This is a superset of the up side saws enumerated by Lauren Williams Wi Typing ApplyUmSc SAWUSO q 20 x 1 would give the first 20 terms and mul tiplying all the terms except the first by 2 gives the first 20 terms of the enumerating sequence for self avoiding walks whose initial fir
18. ges that belong to the vertical cross sections k lt x lt k 1 There are two kinds of edges vertical and horizontal Consider the horizontal edges i e edges joining k y and k 1 y for some y It is immediate that there are always an even number of such horizontal edges Here we will undertake the task of enumerating saps with at most 2r such horizontal edges per vertical cross section where r is prescribed in advance In particular the case r 1 is the much studied case of column convex polyominoes according to perimeter Note that these horizontal edges arrange naturally into pairs that are reachable from one side i e one of the two portions of the sap that are between them is entirely to the left of x k and hence the other portion is entirely to the right of x k For each such pair of edges we will assign the letter L to the bottom one and the letter R to the top one It is immediate that the resulting word is a legal parentheses a k a Dyck word where L stands for and R stands for Recall that a legal parentheses is a word in L R with as many as L s as R s and such that any prefix has at least as many L s as R s Conversely every such Dyck word may show up eventually in some sap As we said above we are interested in enumerating according to the perimeter for any fixed r the subfamily of saps that have at most r L R pairs in every vertical cross section When r 1 we hav
19. hen weakly upwards with allowed in terfaces 0 0 0 1 1 0 1 1 or weakly downwards with the negative of the above then weakly inwards with allowed interfaces 0 0 0 1 1 0 1 1 The gen erating function enumerating the weakly upwards convex polyominoes where you are also allowed to quit in the middle is gotten by typing Delest 1 0 1 1 0 0 0 1 10 0 0 1 1 0 1 1 0 0 0 1 1 0 1 UF a and the generating function for convex polyominoes by perimeter is roughly twice that To get the exact count we have to account for some trivial over counting This is done THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 15 in ProveDelestViennot that as we already boasted above proves the Delest Viennot formula in about 10 seconds of CPU time Multi Parameter Counting MAYLIS also contains procedures to find Umbral Schemes for counting saps for arbitrary r not just r 1 according to area and width as well as perimeter It is procedure SAPUmScg whose syntax is SAPUmScg r q x t w It can also handle restricted interfaces with SAPUmScgR See the on line help by typing ezra SAPUmScgR To Do List 1 Extend MAYLIS s procedure SSUE to solve more general equations that also involve the q dilation operation f x f qa thereby finding computer generated proofs to the amazing results summarized in B for enumerating various
20. ipi ly haa pei by ici imk BAT ps1 Pa is Oe kG j Se 4 ane Ds ire eae hy A LT of course ji ji 1 pi_ 1 1 Similarly suppose that the entry corresponding to the horizontal edge consisting of the top of the source letter interval whose length is A is an L or R that goes up denoted by L 1 or R 1 in the PreFollower This means that the interval right below it of length A _1 is willing to share its top successor letter interval j 1 pj 1 In other words A _ is generous and shares its top interfaced interval with its neighbor above Not only that A gets q credit So if this is the case in Monster we have to replace Pa Zj qt Ej sey Lji p by Pa 92 j _1 pi 1 sji q Eji or Lis p We do these adjustments for each and every time an L or R is not attached to 0 It is easy to see that these adjustments are disjoint i e do not interfere with each other and can be carried in any order The final outcome is the Atomic Pre Umbra corresponding to this particular SAP letter and particular Follower For example APU LLIRR C C L 0 R 1 1 2 0 1 2 3 3 4 4 5 0 0 1 0 is the pre Umbra sfer q 1t4 P Pa 0 Pa 0 Pas 21 922 23 Poo qzs while APU LIRR C C L 0 R 1 1 2 0 1 2 3 3 4 4 5 0 0 1 0 is the pre Umbra apagtas gy 4P Pa 0 Pay 0 Pag 1 922 3 404 Poo 4 Py 21 922 03 9 and
21. mple the computer generated set of equations for enumerating saps with at most 4 horizontal edges per vertical cross section occupies seven pages see the appendix and it probably can t be solved in any reasonable way but as was pointed out by Herb Wilf an answer is just an algorithm and it is a good answer if the algorithm is fast or at least polynomial time and from this perspective the set of equations says it all Granted even computers have their limits and for example my computer Shalosh B Ekhad ran out of memory when it tried to find the set of equations for the next in line case of finding an Umbral Scheme for enumerating self avoiding polygons with at most six horizontal edges per vertical cross section But who cares about output It would not be humanly readable in any case since it would probably occupy more than a hundred pages The program to find the equations can be enjoyed for its own sake so an even more enlightened definition of answer is the computer program that would find the answer if you had a sufficiently large and fast computer I believe that most of us humans would do well to retire from proving and take up programming Of course we still need a handful of humans of the caliber of prophets like Gian Carlo Rota to invent new concepts that could be turned into computer programs but the day to day activity of proving even computer assisted should and would be come pass
22. neous symmetric polynomial of degree i If Z z m is a set of variables we will sometimes write the above as P 4 Z which is legitimate since P4 is a symmetric function of its arguments We have of course PA z1 2m s P lli s mizi Zm Since P4 z1 z we can repeatedly use this inductive formula to get P4 z1 Zm for any m All that is involved is summing geometric series that Maple does very well For example z za Dies Pa 41 22 21 2 Note the evaluated expression of P4 z1 2m is a linear combination of zit z z4 with coefficients that are rational functions of 21 22 Zm The Umbral Evolution Each SAP letter with s L s and s R s 1 lt s lt r is associated with the generic monomial rhs Ae pe a where the generic positive integers A1 Ao A2 1 denote the lengths of the intervals between consecutive horizontal edges corresponding to the entries of the SAP letter For any of the many Followers of a letter it is possible to predict the totality i e the generating function of the contribution to the q x weight coming from the transition under discussion For any given SAP letter LET and any given Follower PreLET we denote by APU LET PreLET this generating function APU stands for Atomic Pre Umbra How to find it First we treat the special case where all the second components of the L s and R s of the first component are 0 i e all the L s and R s tha
23. ons implied by the Umbral scheme that turn out to have the form A x q F x q B x 9q F q q Cla ee Fa q D z q 0 Doron THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 14 for some polynomials A B C D in x q In the fortunate case plugging in x q and then differentiating with respect to x and then plugging x q produces two linear equations for the two unknowns F q q and or q q that must be rational functions in this lucky case F q q is the desired generating function In the unfortunate case plugging x q produces the tautology 0 0 In this case we can solve the algebraic equation A x q q 0 pick those x q that define a formal power series and plug into Doron and its derivative w r t x We obtain linear equations for the two unknowns F q q and E q q that can be solved yielding this time algebraic generating functions Because of what Gregory Chaitin calls programmer s fatigue I only treated the cases where A x q is either linear quadratic or a product of these but two more hours of programming would have done the general case Xavier can do many more cases just as fast and often faster The first argument to procedure Xavier is a set of allowed interfaces between one vertical cross section to the next We use the same conventions as in PreFollowers 1 means up 0 means straight ahead and 1 means down For example the interface 1 1 means both the
24. rivial case we can actually automatically solve the equations that were automatically generated by USAP As an example we give the first fully computer generated proof of the celebrated Delest Viennot result that the number of convex polyominoes with perimeter 2n 8 equals 2n 11 4 4 2n 1 n The Third and Ultimately Most EFFICIENT Way of Using MAPLE The great combinatorial enumerator Mireille Bousquet M lou in her fascinating Rapport B p 20 writes about the two ways she uses Maple The first more tradi tional one is en aval downstream i e after the research which consists of verifying or correcting an already proven identity The second beaucoup plus enthousiasmante is en amont upstream i e during the research And indeed Bousquet M lou and the other members of the celebrated cole bordelaise Xavier Viennot Maylis Delest and their academic descendants are real whizzes in this interactive mode of research But there is yet another way of using Maple which is my own personal favorite and that is exemplified in the project described in this article This third way of using 1 Department of Mathematics Temple University Philadelphia PA 19122 USA lt http www math temple edu zeilberg gt Accompanied by the Maple packages USAP USAW and MAYLIS all of which are available either from the above home page of Zeilberger or from lt http www math temple edu zeilberg utm html gt Supported in par
25. sole L and the sole R go up 0 0 means they both continue horizontally etc there turned out to be 271 inequivalent cases to consider about half of 2 the number of subsets of all the nine possible interfaces For example try Xavier 0 0 q for the trivial case of enumerating rectangles and Xavier 0 0 1 0 q for enumerat ing Ferrers diagrams by perimeter Surprisingly the generating function for strictly upwards convex polygons gotten by typing Xavier 1 1 q gives the generating function for Generalized Catalan Numbers M1141 of Sloane Plouffe SP that enumer ates secondary structures of RNA Wa To see all the successful outputs of Xavier type DoThemAll q With the current version of SSUE Ekhad succeeded in doing 81 cases and failed in the remaining 190 but I am sure that an improved version of SSUE would give a 100 success rate Variety is the spice of life An r 1 sap may first follow one set of interfaces then another then yet another and so on So every word in the alphabet whose letters are all the 511 non empty subsets of the set of nine interfaces 0 1 1 introduces yet another combinatorial family This is computed automatically of course by procedure Delest1 if you are not allowed to quit or Delest if you are allowed to quit It is easy to see that a convex polygon has three parts first weakly outwards with allowed interfaces 1 0 1 1 0 0 0 1 t
26. st horizontal edge is East bound and whose projection on the x axis performs at most one U turn 1 4 12 34 90 238 614 1584 4028 10246 25818 65076 162940 408074 1016962 2534848 6294268 15631572 38703172 95838918 You are welcome to try SAWUS1 SAWUmSc 1 x q on your computer but on my computer it ran out of memory So it seems that SAWUS2 SAWUmSc 2 x q would be really hopeless but so what Once again the program is the message not the output For any given r I have an effective program that finds a polynomial time scheme for enumerating saws with up to r LR pairs And sometimes having the program is our only substitute to seeing the output I would be very impressed if you can write a program that in finite time and memory is guaranteed to output true or false depending on whether the Riemann Hypothesis is true or false I am not asking you to show me the output MAYLIS a Targeted Package for Generalizing the case r 1 of USAP The case r 1 of SAPUmSc corresponds to enumerating column convex polyominoes lattice animals by perimeter solved implicitly by Temperley and completed by Brak Guttmann and Enting BGE MAYLIS is capable of not only doing the Temperley part that is already done in USAP but also the part done in BGE All you have to do is type X avier 1 1 1 0 1 1 0 1 0 0 0 1 1 1 1 0 1 1 q SSUE automatically tries to solve the equati
27. t by the NSF THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 1 Maple is to let the computer do everything all by itself The human s role in such an endeavor is two fold First one has to invent a fruitful concept that may be turned into an algorithm This part was done in the present case by Gian Carlo Rota see Z1 who invented the umbra Then the task remains to design an algorithm and write a program implementing it that will guide the computer to do research Of course once the computer knows what to do it can go much further than any human So this is neither down nor up stream but above stream We take a general problem say of enumerating certain classes of self avoiding polygons and use Maple not just to solve the humanly derived equations that we cleverly found by doing combinatorial reasoning but let the computer do everything except at this time of writing the programming This consists of having the computer first derive the equations and then whenever possible solve them To take a dramatic example the Delest Viennot DV result mentioned in the abstract can now be proved in less than 15 seconds of CPU time Just type in MAYLIS ProveDelestViennot Moreover for the same effort of writing a program to find a specific generating function we can write a much more general program and get thousands of new results Also our much faster machine colleagues can easily surpass us For exa
28. t survived the joining process THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 8 of phase I decide not to dawdle by wondering vertically on x k but rather walk the inevitable horizontal edge straight away Then we insert the new LR pairs as prescribed by the fourth component of the Follower Now we number the resulting new intervals of the emerged SAP letter by 0 1 2m 1 2m assuming that there are m L s and m R s in the emerging successor SAP letter Next we look how the 2s 1 intervals of the original SAP letter interface with the 2m 1 intervals of its successor Some of the intervals of the successor SAP letter are those coming from newly inserted LR pairs hence contribute also to the q weight If the it interval of length A of the originating letter overlaps with intervals j through ji tpi for some p gt 0 of the successor letter and we set ais 1 or a 0 according to whether the interval j s is due to a newly inserted LR pair s 0 1 pi or not respectively then the new contribution to the weight only stemming from that A is Pa q2 Tj HQ Ejip QPF Tji pi Note that ai o and ai p must always be zero In addition to take care of the q part of the weight that keeps track of the perimeter our primary concern we multiply this by q for the 2m horizontal edges of the successor SAP letter and by q t1 t4iz t Aiv if the closed for traffic intervals were the intervals
29. the above total The Pre Umbral Matrix Now we form a square matrix whose dimension is the size of the SAP alphabet ie Cy C2 Cr both of whose rows and columns are labelled by letters legal parentheses with lt r LR pairs The entry corresponding to the row labelled by LETTER and column labelled by LETTER is the coefficient of Z ILETTER in the pre umbra constructed above which is our umbra applied to the generic monomial ot Ae 062 Z LETTER where s is the number of LR pairs of LETTER The Umbral Matrix We now convert as described in Z1 each of the entries of the pre Umbral matrix into a full fledged umbra this is accomplished by procedure ToUmbra in ROTA that has been transported to USAP THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 11 The Umbral Scheme Recall that Z1 in addition to the Umbral matrix an Umbral Scheme also needs a subset of starting letters ending letters and the initial generating functions for the starting letters In this case things are easy There is only one starting letter START one ending letter END and the initial vector consists of the unit vector with all 0 s except for the component corresponding to START that has a 1 A User s Manual For The Maple package USAP The reader is urged to study the source code of the Maple package USAP that for any fixed but arbitrary positive integer r automatically finds Umbral Schemes for SAPS with lt 2r horizontal
30. when one programs it is often convenient to have data structures with redundancy Phase II The PreFollowers The next decision is how to continue the surviving L s and R s from x lt k into k lt x lt k 41 Each of the L s and R s that survived Phase I has to decide independently whether to cross the x k road straight away we will call this option 0 or to walk THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R28 5 some distance up x k before crossing option 1 or to walk some distance down x k before crossing to x gt k option 1 If a PrePreFollower has t LR pairs left all the other L s and R s having turned into C s then there are 3 possibilities altogether We will denote each PreFollower by a list each of whose elements is either C or L 1 or L O or L 1 or R 1 or R 0 or R 1 For example the PrePreFollower CCLR 1 2 of LLRR gives rise to the following 9 3 PreFollowers C C L 1 R 1 1 21 IC C L 1 R 0 1 215 C C L 1 R Wtf 205 IC C L 0 R 1 1 2141 1G C L0 LR Of 1 21 IC C 12 0 R 1 1 21 IC C L 1 R UU tH 21 1G C 1 LR Of tH 2051 IC C LZ 1 R UD 0 21 Phase III The Followers Every vertical cross section k lt x lt k 1 is allowed up to r LR pairs If the examined PreFollower has less then the sap may decide to insert new LR pairs in the
31. with at most r LR pairs for each vertical cross section and the PreFollower in question has t LR pairs this means that we may insert up to r t adjacent LR pairs in the open intervals We denote this choice by a list of integers a1 a2 m where m is the number of intervals open to traffic the length of the above mentioned third component of the current Follower and the meaning is that we inserted a new adjacent LR pairs in the first available open interval az in the second and so on Of course we must have aj a2 dm lt r t Thus if r 3 the PreFollower C C L 1 R 11 01 213 of LLRR gives rise to the following Followers among many others C C L 1 R UW 14 21 0 1 2 3 B 4 4 51 2 0 0 0 where we decided to place two new adjacent LR pairs at the semi infinite bottom inter val or C C 2 1 R 1 tft 21 10 1 2 3 3 4 4 5 1 1 0 0 where we decided to put one new adjacent LR pair at the semi infinite bottom interval and one in the interval between the second C and the L or C C L 1 R 11 1 21 10 1 2 3 3 4 4 5 0 0 0 2 where we decided to place two new adjacent LR pairs at the semi infinite top interval and so on We may also choose not to insert any new LR pairs since we are allowing a vertical cross section to have less than the maximum allotment of horizontal edges hence the following PreFollower is also O
Download Pdf Manuals
Related Search
The umbral transfer matrix method IV. Counting self