#OK to post homework
#Kent Mei, 11/8/20, Assignment 17

#---------------------------------
#Part 1

#coeff(taylor(KingToursGF(3,50,t), t = 0,51),t,50)
#3145849036836987795351683029577878807030 ways a king can travel on a 3x50 chessboard, visiting each square exactly once and able to return to the starting square. 
#Note this assumes that the forwards and backwards path for any given circuit are the same. Otherwise, the number of ways would be doubled.

#---------------------------------
#Part 2

#A:={[1,0],[0,1],[1,1],[1,2],[2,1]}:
#S:=SeqGW(A,50):

#ope:=Findrec(S,n,N,5);
#-2*(2*n+3)/(n+5)-(11*n+23)*N/(n+5)-(13*n+41)*N^2/(n+5)-5*(n+3)*N^3/(n+5)+N^4

#Order is 4.

#SeqFromRec(ope,n,N,SeqGW(A,4),3000)[3000];
#Number of ways is:

#95169091361304497661016734197678134770349822930308569276916914467565347871540683291808752282824707570651985872820372363152563131551499362536825304711559361666563103386330829999710178259606336618359856705840905896307823039694186915923739801088785552537207794661641719063082723104319582945468736368770654686751378287041101572685985713084393957598627298986861938927166053927103431921104126027579703091359302890708953724730599070838409654723308763002613165079306548111632722909218562889533100675786353470112016022196477554880490589499289089162582632715079250461763612854611196880347954440249628671174622179674903282050871247325146410790010719334253540172397663997792921830518354359522669329363082614972729965686428855219511297199827548476675004412199720715365099792501311123143368483881397876775712439421054798831717981977936622337062303624546576898187959341646575490702549296915200857634048143923818701102393144599106994024665053648913638391157955194662231996921003344586526221812096107389514125990119451880185515845934698037055104486896573666844857573880742852639391722910231692794433520126339340352663869698430014805776170895308465157999383126154136534892638175457579256315002808693778321645459807540062485196275478961352224073937381392596094278147716000344452101216213718218846995422403246683326563202994807095282839244324106363086847480478463730345215985413064515655006280716371594297868314185041474747026816679035293127055797403755491278529530018110422188400807126145601136460544996907253108026710738133221241693706980842171873604900269856459541793234702167937163679886476596787643003424261664266808615823066346661804622908642236679528725542671747404314012249795021732170691008575336656050986306648593100164229972842611760785390415331373519508784472911981975537222743422312589751576257948909815276363791495173342977855094118355700016556226919615428250897733703209967582718607928464069524222159738340806195626241390924709235357374015016254839959209084054394569432471432576684522506998779788376200443126782132255047582891261666245361634285199523372050333572627938881441014457739772722775254541205569963083330946306737155223437987340685548656285567503838100825537658312256841838804244651258118811651131924827871017999511708744102921789247462817980894438730298698541980861879749020341945718568693083738317799328488585909649259726166330681988951268751122991503360075439622584181083778123619416313964846558075294830227299727374990124401764015434769152111199549890678059731046462531157554362228562028418125254044367001279506736510680059995930940034.


#---------------------------------
#Part 3

#A:={[1,0,0],[0,1,0],[0,0,1],[1,1,1]}:
#S:=SeqGW(A,50):

#ope:=Findrec(S,n,N,10);
#-(n-1)*(n-3)*(3*n+8)/((3*n+5)*(n+5)*(n+4))+(n+3)*(9*n^2-3*n-16)*N/((3*n+5)*(n+5)*(n+4))-2*(3*n+7)*(15*n^2+65*n+62)*N^2/((3*n+5)*(n+5)*(n+4))+N^3

#Order is 3.

#SeqFromRec(ope,n,N,SeqGW(A,3),3000)[3000];
#Number of ways is:

#1055961597172638192205714533827955182069330710185887123715638338751912356623868934358954829265893265497184019516455497946501358614406592180916562995571435822638011864699948413518735379729837425167828197932773091617214603560704076763403058008870590210530506834889187670236069663000563403909291518139471141193933668569097230791592378327765453206880338367141465884774689273332974613327790670133864770839786907616252716172612810392322684357026318977543761631185892041752872792707472523339315464878092600122776510487117547611700101814824458512731561188677556925181977017823995965449343853533549328389007002003812727585993220294254740294866113923151479672429490481644088528411109634826771309376893827003349243068183476873533935594331988585675337762038394870883132602159173883922347999944078821728163370937052619155590568391069063317592509955598788483466418234408407388202299036233322379192615075021698393212868787733569268229184628289565589549741584574327892919908881010751517221722381012834556556824848577221227684137830816101020327876526681725444453682864636555747673248741474708131366459673977930419195224272687150280798146593067544755578201466060570093254935347120068461604351415848203621522648676607169207523056123186434484713066312780810175397901692245443312244602960976968454897460424230265560584944905249327347768975517831568652679595607920084575082584347314212810007985240690964634053969181170611215275387792197501045392327155456594027530404389193373166529959026406585893677752993907919001817631111686530612365744087948657981705511840245825626621270255357615436919191022104201504251202188647227781935143967146969540653262038857149021960306229530963054026491708200678862903006329234012195611754127295080517138419193838585920213543419469950079348946755215094694137847178186210286204470627994554250221170678469119109643939053546724329890548255475005106738694859949241621137720195040487766275618591781040165985869235563695957345264145252201054929162788252799455694036338904769031986390960043941243280986491172713827805499916660157385659508981509849147715973547457229029295526584351410281813731593170470817309110789876049747009019009949757200409333866914797127029381219525171081649367682900079983068290393154404118264018185364905606965589045505005572066630122121150375280811289992817027578011638093603433244372443437925332947876282657417807723726415290604403918202072098770116006990175350820492314867796387685661273702215556922453698175420527665425961486623775069041082819614980223231440570232620689816525157996858630797825675874156474646732065652602821773250214911095523839301872173514572945534777185829446594458412939559790823335335988943249612096741437113159733496107309438749517155816113611466181606413786593079760286476932502122540382520346014562754440684858961033148757521944516188781560550967342223679376726927253300939809903760523174681426976332580145397706760699651938934492314536611971407185558853691943983900622101911869433034988901671398749303046154807811343347079647262775389547959397251809798861843882195477113660504281821150366169039324164617598327207275003383926645719618807107118775499837007692943421107557066566151632494226460059669482223627000755320102291265532871104516620408021503469564960744840527318501733587855812003819890890023893498130260498951286347694871337136866334557342356711006118238958427510975755322669497692071461010165591733674071285408880586240632956831541705216908849696753484260512346231146506771015879263648500135313751979294236700008885800509693120930841769817301480352739004267277612475636269175159040483895116762728473969354479429135527425822803355504559236868842150825399906121046596018792183036698610028246005663710973350043476200695248674446173296357513573521498183102888985070332615743303290931992949087204064596760980551855974772314932770996526784911225488608910212901539625649853695492476183650987182998517921557222998098782725632700696246594120460326038060483755479352197136229776118789296545919836632814452748621216052104394615335775039904853067848468754958862041044060581067912446471855014833235066207766370613368257308071954943653479180111042281881188887660434936081241799850788470218012237849400298660425782403148718872653901005280466525095291577169601084339235634955604898374949141660578599870423680499360451073008559080164788699736386609233499025062855391709957273487073386537359165683384170380942428413622358059424469862102618894310733782269292492850029973291.

#---------------------------------
#Part 4

#F:=binomial(n,k)^2*binomial(n+k,k)^2
#ope := Z(F,k,n,N)
(n+1)^3-(17*n^2+51*n+39)*N*(2*n+3)+(n+2)^3*N^2

#order = 2

#When n = 1, Sum(binomial(1,k)^2*binomial(1+k,k)^2, k =0..1) = 5.
#When n = 2, Sum(binomial(2,k)^2*binomial(2+k),k)^2, k = 0..2) = 73.
#Ini := [5,73]
#SeqFromRec(ope,n,N,Ini,3000)[3000]

#Answer:
#2722642711747329013359227913572710537967104475547733421085159876139384634676850735063904093083359261956322867579665053314255370804763722281790779093835410541511418166634290758716725111753006762131305688572559381260548003772062557250247721466614238663770743892364807576993084081558462700576614278862788208721645954806465583065602187715682814106704612402275506072291084112985500212686023858801381107120776811844560415857377786813263183969424052055617010857380794491890410944056310769521029459173036679240877867005236908394866701677059219684348204361332249910003037286944272333375631146873345814821227104852534785843936368959818832478077725569644407075253374474052536921206608748270422879828826902301431186696953710590225944340115857919619264384561183994505485335091537086380740281406939094772106076302723386171314597542050563475843366320030625742826929858889660364007666293245817270911428111950635447140358988139094082725691042841889646560561477476935832742178296234660221420178120796234990088001434096318656530218092868032853550310196018237804258196742181910877012887545502054637095527797501861523170553575129142169451693437328675832112432476314461203235515352839573366750418165557810656435894627035571601255806895946536455222957039160750615848202975761787255060029732779525265442036490393317128901846356097241773156867344507855494093752391994381023128371628704715908210575484185716975619449463442583395278257540772193206348580592937855537248628620466470539288556541661832873814056468481987420957701100857860523572540967385266920053861677914291188280944877401747551661089877083317797604110557551364701929748366772149258996673447675005123086550113703764217176758195860435990867795170869395903124727142163594801381529246860929640950159772000100631413790792212965344708548770354323901339612899027847649119198063039365893013538457551513411093345561536822366986265917412904840360563624377109175770777665445155239221619611485299625852134559025659912095119338611886550297595740548307375649565634948493253019969871927649283571254688763936033373264896857823896269127788026425507808470356775700467388060895653270527152866893161963931776506652204657885942928746306431235273664875073034043145202244923808794388369380516219822837239194142849797804822593665338939337302309434901793013173302083269369688516505935783551307848007738581224037372934917042689578935550744752847955956163759006312379601494705557456183072265285209531539735942356563341299018671880996309304048086427048684614070266687579163017366103655516350454661153144028679506553320905507592580797070875042927687201669656031079427557267199902205653847758693057124170008328495526932223772121412856986436069056164599085457437778224321688404623428273288070377344343062119999908434118162432922591090562805467595894646780641622439563187365668307111538077025471158764808381561868629015682670140130948774568270992597249266794011361238119206856341415052185892084189107926139916710579316845611503499017305367756723113374621149791283762657110141332311373814567195029994995335416720094450079337831204846209912409327969012834126743860958648202563413578393747882976846339593511107268832078612120589074952807980914622311502138139528554616889602010191489537304591668379595191050931795962234516897033052931690850209805931083355558716380741263181548085215805281399035131706171628221919923270321741376286430739463746610276665672321579351016072824579635306469668031505594726147116797367118182389074444542530394917557769277531202968428229091372933410304928268327492597665606985779187052947832886995670607597328576672367590871239494332163346732354372049724012157706525094234713863888393732416338376292816636359143592277115651039460138234618018361589663036767340765411992955916668465373578134122931164300533407609504598223240071841820394282382394636232106660461317758721890332621373505053829647336732853080397664858184207815285507311631874658090623913947693223906601820863601996025547747003927254483371568119099500867273209270201947583522543040635862034744741324369025898450282401574641710510749342774620516505124008520070877996367769485909407472852144748999599243998191452958792623810638284969941075414587768028791082230583281372498133282761967970219890139139185713350468473313804128136345874570217526217067321217059159810181119543712592946078273054819769406301487344528299653280807766212354937941130077970045725796941083616149212251016526450296058431426689174647746337834990255401174923064843884802590847115146950517668328110904709213864024261091267210552034153798003542992734480500041363214110149539201741903501339475545184258347426576368029282689454411666791001

#---------------------------------
#Part 5

#101 = 2*50 + 1
#Sequence 2*k+1 starts with 3 so there's an offset 50-1=49.
#OddTTT3(49)[49]

#497489711804340577094 
#is the number of 3x101 TicTacToe boards that end in a tie.

#---------------------------------
#Part 6

#G:=Bn(9):
#SimuAvDegree(G[1],257,1000);
#[4507.587549, 4503.079963]

So the average degree is around 4508 (in this run through).

#---------------------------------
#Part 7

#f := 1/(1-4*x-5*y+11*x*y)
#S := DiagSeq2(f,x,y,50)

#ope := Findrec(S,n,N,10)
#121*(n+1)/(n+2)-29*(2*n+3)*N/(n+2)+N^2

#Order = 2
#Ini := DiagSeq2(f,x,y,2)

#SeqFromRec(ope,n,N,Ini,2000)[2000]
#Answer:
#773646859915755345080592880711987868114000067411267711089645465297302185782140437651737245647882206781438666359768916791715657797616253271074975816775510891610817784007689815061811713118793808132127169156531956632210202931839862195808509640930194072475736797648958419891588400228778302107480391146576468783927091978800730725381748927502387454205436928125198975511378423794707365823379926986188749731089986500669917397396616873971504095084806867185794148201994249569708224664939358898156705285766137705808523882246825460865055845849608101602554124421655543281954942869347763265534288898345102646980249705245750411149901021906533804652856542653764498677365214438615665150615517343477647558880827613427285885357921841100046634238461334120207717747344306854642161789096422806822477126080459383319139414084891874813390575035056820274820249163621592543772865926118882829787233403086035287238779765054941813725170004414582374135508817403257313682626312641850119576783617936793647393405068210227926377575854139336013624990425865640946215471320032948282468940324846914561138775497162509724260118084959559782824445762245632299836411179392775648099505004754289691484084437878335072556789083071128828642026102198988713371433916086729092810868873365284186949520302620916959510360154686720720849426575947536973822089840926819039524739154650307471233566116603524983355463110367522269735546877184343991825037545531189756117352626296189893351782094577197526461536355028695315424139758095138975823719895497596876668131934199439173229485368636994380428110961997982663512993479753274524564588897844411090731278082694716259642257912209226715162964982766205644375213279962095754671175676851278122336924210409928907451885674299545970520895098122438167730023956375082767841919536492659592553484758514186588962566254898054642148157529356160985269637101035563320027681988296575398258581899930433851537298396125459746563645498518344619371613618855757920153091128439831385651061713354178518359400614334182811551611306246590748272172228421650703852569210285063688014891546768428033707913809454151141697846121976041016161198422075270533277284589452027578075668399593831720510523495731158754673764413760975340577700256181793723268102737700377434630624790249458797868911788044600805508485574241229253198181585117115731176981772669466598392654721571804299532408697203358580912723946227908232155338588428127174145078183468669908828952557055163469676170155844087464068982383237074344331350973287832545815695040580098426592501971544206619030825683346801296280335524080438127590769794668939223630265567779224717497406424337680111319658968840828783394398066924082596974045522418906009355130535708234172204495769135348785825545908155547519817718720637411445747313149486470464529574488009448609563739552269119003138524190110775062801488158287029560619172943034584983763324488306289724561326554924726583458117754924933611552675041469797148844028192904120049411967702119285010310450399474899988993586144695013187426300062274614261232855180913589064620769172807279547595522263494030111333199971899957574277407800812548961437147806523394123808961636877041743608198426614043951238220331970986440053143097092028066307341624392350207383551740144663484185505423935912306650375320554777485131772136130297787225160458443358096735851606998995447761379827375728762226123218580834402190682606068437153306290925913239883594710884034531237609827555387947652206110770058576176763122989223205695856623992082656117211112586521163319820736781340880001