Algebraic Equations satisfied by walks with one positive and one negative st\ ep each of size between 1 and, 5 that start and end at the x-axis and never go above the x-axis By Shalosh B. Ekhad In this book we will present algebraic equations satisfied by the ordinary g\ enerating function of the sequences enumerating ALL families of walks consisting of at one negative and one positive step where the size of each step is between 1 and, 5 and that start and end at the x-axis, but never go above the x-axis We also supply the first, 30, terms of the enumerating sequence ---------------------------- Prop. No. , 1 Let a(m) be the number of sequences of length, 5 m, in the alphabet, {-2, 3}, that add-up to zero and such that their partial sums are NEVER positive. Then the first, 30, terms are [2, 23, 377, 7229, 151491, 3361598, 77635093, 1846620581, 44930294909, 1113015378438, 27976770344941, 711771461238122, 18293652115906958, 474274581883631615, 12388371266483017545, 325714829431573496525, 8613086428709348334675, 228925936056388155632081, 6112355595348903438948155, 163869604996054172670563730, 4409530805291138147009940577, 119053554405655805081339777916, 3224183996664038053758382236200, 87561359887231436502479212567970, 2384085494382142705840768924534711, 65066994871847852574373263376452916, 1779721375844162673264781567864062809, 48778310711916131693983042017623427225, 1339440127229098961724679335624540335066, 36845651741358843132371645279597764145919] The ordinary generating function, f=f(t) infinity ----- \ m f(t) = ) a(m) t / ----- m = 0 satisfies the algebraic equation 10 2 7 6 5 f t + f t - f t + 2 f t - f + 1 = 0 and in Maple notation f^10*t^2+f^7*t-f^6*t+2*f^5*t-f+1 = 0 ---------------------------------------- This ends Prop., 1, that took , 0.275, seconds to generate. ---------------------------- Prop. No. , 2 Let a(m) be the number of sequences of length, 7 m, in the alphabet, {-2, 5}, that add-up to zero and such that their partial sums are NEVER positive. Then the first, 30, terms are [3, 76, 2803, 121637, 5782513, 291437249, 15297882929, 827402061954, 45790180469312, 2580588279994441, 147592910517101281, 8544927937132306600, 499811636639428519226, 29491983283370728013309, 1753398440591481772556798, 104933899400256659634374549, 6316334518803437568442071134, 382157894402929888870502301422, 23227867059873378295000835711897, 1417626021933575573690480062573957, 86841335288654276627784306088376579, 5337703991119630400867518436365901430, 329091133138293837644741627024856762971, 20346914629793261198471539429714087455949, 1261253541170025826081983672206908041769463, 78368238337961270215187805156530040517653795, 4880158146656704277707955417370236584894808458, 304519114336255386051309592492886745921342588610, 19037944696024295638921223215273141675851253284790, 1192325081048380267824624452954260532860853011311094] The ordinary generating function, f=f(t) infinity ----- \ m f(t) = ) a(m) t / ----- m = 0 satisfies the algebraic equation 21 3 16 2 15 2 14 2 11 10 9 8 f t + 2 f t - f t + 3 f t + f t - f t + 2 f t - 2 f t 7 + 3 f t - f + 1 = 0 and in Maple notation f^21*t^3+2*f^16*t^2-f^15*t^2+3*f^14*t^2+f^11*t-f^10*t+2*f^9*t-2*f^8*t+3*f^7*t-f +1 = 0 ---------------------------------------- This ends Prop., 2, that took , 1.075, seconds to generate. ---------------------------- Prop. No. , 3 Let a(m) be the number of sequences of length, 7 m, in the alphabet, {-3, 4}, that add-up to zero and such that their partial sums are NEVER positive. Then the first, 30, terms are [5, 227, 15090, 1182187, 101527596, 9247179818, 877362665128, 85783306955099, 8582893111512001, 874542924575207352, 90437361732467946334, 9467275300762187682554, 1001309098267187214993056, 106836493655355495755649544, 11485688815900189437990930096, 1242964338344397490958154292155, 135294163560516394214244049693547, 14802386593672915358103823856915731, 1626958525109139734774927715918218672, 179560107576192929210029836580628234040, 19891067655976720771724498635720956196452, 2210912607893524622765424058253058782769990, 246502063369558281502815364695754079893446736, 27560798966536669949656624489057599283778866010, 3089483559429429698036468167660236517959818560678, 347148306792125191804983135400320697609339102573244, 39093218980356982643240380289607142470275410581244370, 4411391873089411275228337557266673535322459461801972040, 498741562008590845805410864237023381327023182399428530336, 56486593799030289371750854015935460223463413333016415972912] The ordinary generating function, f=f(t) infinity ----- \ m f(t) = ) a(m) t / ----- m = 0 satisfies the algebraic equation 35 5 31 4 30 4 29 4 28 4 25 3 24 3 23 3 f t - f t + f t - f t + 5 f t - f t + f t + 3 f t 22 3 21 3 19 2 18 2 17 2 16 2 15 2 - 4 f t + 10 f t + f t - f t + 5 f t + 3 f t - 6 f t 14 2 13 12 10 9 8 7 + 10 f t + f t - f t + 3 f t + f t - 4 f t + 5 f t - f + 1 = 0 and in Maple notation f^35*t^5-f^31*t^4+f^30*t^4-f^29*t^4+5*f^28*t^4-f^25*t^3+f^24*t^3+3*f^23*t^3-4*f ^22*t^3+10*f^21*t^3+f^19*t^2-f^18*t^2+5*f^17*t^2+3*f^16*t^2-6*f^15*t^2+10*f^14* t^2+f^13*t-f^12*t+3*f^10*t+f^9*t-4*f^8*t+5*f^7*t-f+1 = 0 ---------------------------------------- This ends Prop., 3, that took , 2.525, seconds to generate. ---------------------------- Prop. No. , 4 Let a(m) be the number of sequences of length, 8 m, in the alphabet, {-3, 5}, that add-up to zero and such that their partial sums are NEVER positive. Then the first, 30, terms are [7, 525, 58040, 7574994, 1084532963, 164734116407, 26070940600055, 4252443527211637, 709846349042619913, 120679177855928146859, 20822762876863605793639, 3637213213067542990001936, 641912742432770594132245835 , 114287840570892852593437353124, 20502971288127330644273350110698, 3702570208952583655019682802997983, 672532254932908563141660483607892405, 122788872081951688284011943771535283927, 22521647274404155444930377651363981888609, 4147941699622771075000003992530419494184133, 766800387134061216482320025909653184030552921, 142232635188109104705825683965953973833993117472, 26463875059802945975078404597473760366912931790522, 4937776281963660271976513336467553127439703168792081, 923705580732071027966091450862926607792520810928009054, 173209614000542548827169215936888121699576157630433856342, 32551326898617478879296315323239017028955263215391910486304, 6129911011171870371923259817902143926140014998339271186854371, 1156554775596959673099699203791556477581134593795757346174981314, 218599371430881496639570094146693699868497254932723833300602282125] The ordinary generating function, f=f(t) infinity ----- \ m f(t) = ) a(m) t / ----- m = 0 satisfies the algebraic equation 3 30 3 28 3 27 3 26 3 25 3 24 1 - f + 2 t f - 9 t f + 22 t f + 10 t f - 20 t f + 35 t f 2 22 2 21 2 20 2 19 2 18 2 17 + 3 t f + 5 t f - 9 t f + 18 t f + 5 t f - 15 t f 15 13 12 11 9 8 7 56 6 50 - t f + 3 t f - 3 t f + 5 t f - 6 t f + 7 t f + t f + t f 5 46 2 16 10 6 51 6 49 6 48 5 45 + t f + (21 t + t) f + t f - 2 t f - t f + 7 t f - t f 5 43 5 42 5 41 5 40 4 37 4 36 - 3 t f + 5 t f - 6 t f + 21 t f - 3 t f - 3 t f 4 35 4 34 4 33 4 32 3 31 + 8 t f + 10 t f - 15 t f + 35 t f - 2 t f = 0 and in Maple notation 1-f+2*t^3*f^30-9*t^3*f^28+22*t^3*f^27+10*t^3*f^26-20*t^3*f^25+35*t^3*f^24+3*t^2 *f^22+5*t^2*f^21-9*t^2*f^20+18*t^2*f^19+5*t^2*f^18-15*t^2*f^17-t*f^15+3*t*f^13-\ 3*t*f^12+5*t*f^11-6*t*f^9+7*t*f^8+t^7*f^56+t^6*f^50+t^5*f^46+(21*t^2+t)*f^16+t* f^10-2*t^6*f^51-t^6*f^49+7*t^6*f^48-t^5*f^45-3*t^5*f^43+5*t^5*f^42-6*t^5*f^41+ 21*t^5*f^40-3*t^4*f^37-3*t^4*f^36+8*t^4*f^35+10*t^4*f^34-15*t^4*f^33+35*t^4*f^ 32-2*t^3*f^31 = 0 ---------------------------------------- This ends Prop., 4, that took , 15.456, seconds to generate. ---------------------------- Prop. No. , 5 Let a(m) be the number of sequences of length, 9 m, in the alphabet, {-4, 5}, that add-up to zero and such that their partial sums are NEVER positive. Then the first, 30, terms are [14, 2529, 678338, 215205020, 74954297074, 27706901431307, 10673513460281995, 4238336602544646985, 1722532440479713492905, 713032912920984966665914, 299578160956737689390169226, 127423760336300467698086830007, 54761998197408482500643162670932, 23742924018375726263229745697113234, 10372639160995862858028814581769132028, 4561630228928173937942703373111379977087, 2017804841330203670735598373154752656772860, 897177656970083321768073667118946270564224913, 400752711842105711698489590738780696157143645906, 179749957957898273181768638889177302565608486108515, 80924653758099087193611642848590771414665085220443850, 36556309544907124424830117175556930151453007265988699667, 16564677903334456428003716709807760335580928291214833115606, 7527124558532594346536646943982231197215225418918819481554586, 3429263552961285648003166539047407716193143507178037104769111464, 1566066468328414529702748500989967536486318127577036893982829506888, 716768561186324096677810512889381831577143689734651074373928490318363, 328728612288833087716158981552700126236668367424974904178777273868860162, 151050981487842905575015897230290843691016552943563178561724675552959853422, 69531419296511660079027442856624450723039093889934179554973825253086323536882]