#its ok to post
#TaerimKim,10/11/2020,Assignment 9

#1.given that my RUID is 197005262 & a[i] is the i-th digit.
#(i). 
f:=1/(1-1*x-9*y+1*x*y-5*x^3+2*y^3)
DiagSeq2(f,x,y,51)
[1, 17, 433, 26809, 1272971, 53910551, 2521183985, 122296586433, 5837309025373, 279850658297317, 13582954750950455, 662098978459164511, 32343953804742090979, 1585640277971295944987, 77979932484387043371233, 3843673556529219902425985, 189840875891047534644212373, 9394141961842783094442746117, 465634662414404103587814087341, 23113599318168870168366344069509, 1148854141911668561476236630890657, 57172134340262219063905814478462713, 2848243286568997550838034204858778775, 142036959824386605337020628338871300599, 7089598223027022088609592099099086869171, 354165390527816564959015840912968609264915, 17706252930820949580245978560785776691094807, 885846185903601101123578103257086257388093183, 44348490403956745614331656994536341125748663819, 2221612229073529050591445184665429458915636136291, 111354711632922337273161004859431123244360911658209, 5584491597145564661251389398125476504261443289060161, 280206813796735138062579081454129243976771322536528387, 14066316537867617261577093892625932193330249645142103175, 706442054842542297859098663631125356497507128237548014065, 35494089063197176870114968584509443194860007133277478079721, 1784056690579028214984952094340716692600696211723423562450979, 89706728050183150823956853132883493177377905110837271180884415, 4512284753552056220816867383547428321761936181361751381472265197, 227046665113246645731238453995345890332618159616829028117590250093, 11428086853588518619118285270319549882332788007227664654162761839581, 575393409685369067420317576534114722882755395225430051611747481771141, 28978962881463165658976050857310955499517668428187054982416030848727749, 1459894591054937193794870680134233590833487473751664231219438280954072477, 73565699749576164554874798955174798822802041523837613661924376255614261373, 3707996556161197659442517932112715104772811112707202299149632913740621263469, 186942721618067403738750956357795283588407832012851195581699060660532754565591, 9427110546115932118028721396801314938725836115874309453285633076125495884426455, 475494208604485350774794254126187148005723275114977242543738773952653310426326373, 23988578197988572973735465651038610125633797990628407573272375869494325712861680017, 1210466340875187873389516997149664601556162628929893052290331530182253399149084026091, 61092284771013268207116929167445180173381131460337005926656098597359691198779936213747]
#The last coefficient is the coeff of x^(i-1)y^(i-1) when i =51 -> so x^50y^50
#so the answer is 61092284771013268207116929167445180173381131460337005926656098597359691198779936213747


#(ii).given the set {[1,7,2],[9,1,1],[1,7,7]} & question asks for 3-demensional walk
DiagWalks3D({[1, 7, 2], [1, 7, 7], [9, 1, 1]}, 30);
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 

  0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

#gives us that there is 0 way to achieve that walk
#we will verify by breaking down with simple step

g := 1/(1-x*y^7*z^7 - x^9*y*z - x*y^7*z^2);
coeff(taylor(coeff(taylor(coeff(taylor(g, x = 0, 31), x, 30), y = 0, 31), y, 30), z = 0, 31), z, 30);
                               0
#Same, so we can see that there is 0 way.

#################################################################

#2. 

WordsMod:=proc(a,S,x) local s;

factor(1/(1-add(x^s, s in S)/(1-x^a)));
end:

WordsMod(5, {1, 2, 3, 4, 5}, x);
coeff(taylor((x - 1)/(2*x - 1), x = 0, 101), x, 100);
                 633825300114114700748351602688


####################################################################

#3.

ResComps:=proc(S,x) local s;

####################################################################

#4.
#From given condition,

#(i).
DiagWalks2D({[0,1],[1,0]},40)
[1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, 705432, 
  2704156, 10400600, 40116600, 155117520, 601080390, 2333606220, 
  9075135300, 35345263800, 137846528820, 538257874440, 
  2104098963720, 8233430727600, 32247603683100, 126410606437752, 
  495918532948104, 1946939425648112, 7648690600760440, 
  30067266499541040, 118264581564861424, 465428353255261088, 
  1832624140942590534, 7219428434016265740, 28453041475240576740, 
  112186277816662845432, 442512540276836779204, 
  1746130564335626209832, 6892620648693261354600, 
  27217014869199032015600, 107507208733336176461620]
#OEIS:A000984, Central binomial coefficients: binomial(2*n,n) = (2*n)!/(n!)^2.

gfun[listtorec](%, a(n));
[{(-n - 2) a(n + 2) + (6 + 4 n) a(n + 1), a(0) = 1, a(1) = 2}, ogf]

#(ii)
DiagWalks2D({[0, 1], [1, 0], [1, 1]}, 40);
[1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, 1462563, 8097453, 
  45046719, 251595969, 1409933619, 7923848253, 44642381823, 
  252055236609, 1425834724419, 8079317057869, 45849429914943, 
  260543813797441, 1482376214227923, 8443414161166173, 
  48141245001931263, 274738209148561921, 1569245074591690083, 
  8970232353223635949, 51313576749006450879, 
  293733710358893793729, 1682471873186160624243, 
  9642641465118083682429, 55294491352291112747007, 
  317241780630136241094657, 1820991621200098527441027, 
  10457362855894862001750669, 60078868458555230983696959, 
  345299757825442889707393857, 1985346154034162284608274707, 
  11419126147845924397833900957, 65701922725618214591910684159, 
  378150244155138145169182750209]
#OEIS:A001850,Central Delannoy numbers: a(n) = Sum_{k=0..n} C(n,k)*C(n+k,k).

gfun[listtorec](%, a(n));
[{(-n - 3)*a(n + 3) + (15 + 6*n)*a(n + 2) + (-n - 2)*a(n + 1), a(0) = 1, a(1) = 3, a(2) = 13}, ogf]

#(iii)
DiagWalks2D({[0, 1], [0, 2], [1, 0], [2, 0]}, 40);
[1, 2, 14, 84, 556, 3736, 25612, 177688, 1244398, 8777612, 
  62271384, 443847648, 3175924636, 22799963576, 164142004184, 
  1184574592592, 8567000931404, 62073936511496, 450518481039956, 
  3274628801768744, 23833760489660324, 173679413875623368, 
  1267013689048017584, 9252299435205985664, 67626504432024377756, 
  494710324956646794296, 3621791112234327295592, 
  26534383313499716907504, 194529413506239838951024, 
  1427026630616364232856416, 10474450985957996054150576, 
  76924819005707350396260192, 565226994478396276874021358, 
  4155153128570549776415060268, 30559526512591226909700271992, 
  224848729555165636463415722784, 1655038891063501813947452278468, 
  12186822164518997043970184661512, 89769447797439589097829820560392, 
  661476500151656115107632518838128, 4875741284021393250978952096137064]
#OEIS:A036692,T(2n,n) with T as in A036355

gfun[listtorec](%, a(n));
[{(352*n^3 + 2768*n^2 + 7088*n + 5920)*a(n + 1) + (-484*n^3 - 4048*n^2 - 11184*n - 10204)*a(n + 2) + (-352*n^3 - 3120*n^2 - 9114*n - 8766)*a(n + 3) + (55*n^3 + 515*n^2 + 1570*n + 1560)*a(n + 4), a(0) = 1, a(1) = 2, a(2) = 14, a(3) = 84}, ogf]

#(iv)
DiagWalks2D({[0, 1], [0, 2], [1, 0], [1, 1], [2, 0], [2, 2]}, 40);
[1, 3, 22, 165, 1327, 10950, 92045, 783579, 6733966, 58294401, 
  507579829, 4440544722, 39000863629, 343677908223, 
  3037104558574, 26904952725061, 238854984979423, 
  2124492829796598, 18927927904130617, 168888613467092895, 
  1508973226894216106, 13498652154574126523, 
  120886709687492946083, 1083687170568092836350, 
  9723660300694365146989, 87322023363899721467343, 
  784797155029928933462614, 7058384549327774062817985, 
  63525027490219905080597647, 572078727948766828614679830, 
  5154896021503193637126695629, 46475144470335949808346622587, 
  419221380265186873217492981134, 3783331574173309950816296187025, 
  34158702327707968075053323650645, 308541107632605100591602320772210, 
  2788040608584603973862476702488265, 25202873888846971990310549726981859, 
  227906767043212151853904258820045110, 2061638450059846741700344736532466833, 
  18655567955631232569396589476504942877]
#OEIS:A192365,Number of lattice paths from (0,0) to (n,n) using steps (1,0),(2,0),(0,1),(0,2),(1,1),(2,2).

gfun[listtorec](%, a(n));
                              FAIL

##############################################################################

#5.
#(i).
DiagWalks3D({[0, 0, 1], [0, 1, 0], [1, 0, 0]}, 50);
[1, 6, 90, 1680, 34650, 756756, 17153136, 399072960, 9465511770, 
  227873431500, 5550996791340, 136526995463040, 3384731762521200, 
  84478098072866400, 2120572665910728000, 53494979785374631680, 
  1355345464406015082330, 34469858696831179429500, 
  879619727485803060256500, 22514366432046593564460000, 
  577831214478475823831865900, 14866378592908813372327325400, 
  383331414957648741501332688000, 9904298260191196595161087296000, 
  256376887255990870197659395110000, 6647750135792940867877229051444256, 
  172644824532516079698894427850821536, 4490186382903298862950669893074864640, 
  116939573426172903295569869740819625280, 3049327996713402817207903975524583094400, 
  79607789567531236214574346454361782651136, 2080571532547465690702652742505463614012416, 
  54432139997018169779222721652071650604875610, 1425432294246982705017331107505766145041177820, 
  37362109442632851178222433008152866950473778500, 980137754325264739153760087469388189649326812960, 
  25733153725826742295097099333513427886580242390260, 676129685550027699309454100092387144689767216053800, 
  17777902978506545489876283429576007693615707520173600, 467765731229343820187277358876812510123932028242832000, 
  12315686996104586105755778762527877375925475388598463020, 
  324457176864656573634444032288702901528992030374462542120, 
  8552867757486695393424970238902882608332272909530900345000, 
  225584778148789162220956705576428220142319245674420199040000, 
  5953061113440928872866052731353160003652422655736636347600000, 
  157178452094435902773657469301001507533471817141538271091744000, 
  4152006974608028932625878026488081410723506942789897542979264000, 109730270338441253547622797277670526373036819972871986672308480000, 2901279777984880331429724637396325141316257378084815835114447910000, 76743139816667950790962853694727450947519994203318056513168924100000, 2030807663084593981010775419611355697953653094605883738674081337103840]
#OEIS: A006480,De Bruijn's S(3,n): (3n)!/(n!)^3.

gfun[listtorec](%, a(n))
[{(-27*n^2 - 81*n - 60)*a(n + 1) + (n^2 + 4*n + 4)*a(n + 2), a(0) = 1, a(1) = 6}, ogf]

#(ii).
DiagWalks3D({[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0]}, 50);
[1, 4, 42, 520, 7090, 102144, 1525776, 23380368, 365130810, 

  5786380600, 92774019052, 1501646797248, 24498046138384, 

  402329384914240, 6645072333486720, 110293868867458080, 

  1838511122725436250, 30762545845461663240, 

  516457722792721132500, 8696582711157975572400, 

  146835895664138204448540, 2485266624268853914959360, 

  42157397527828247726954880, 716556351190046311597161600, 

  12201942968211237198350281200, 208134928903175159702319457344, 

  3555830679926229005075061257376, 

  60836819329493358733292740546048, 

  1042259677840638259492432048065280, 

  17878405805956405560805535960396160, 

  307035478496101645580861028622654336, 

  5278643189711854927868638533509575744, 

  90844825001410805657489064172778794842, 

  1564930724096710135146829959035675638440, 

  26982512386206869455023952107027146825700, 

  465628368604516908867820871730799473867408, 

  8041657743459510320462629847980612873329892, 

  138989457278403173476481541185549849571771136, 

  2403979582946502330471619673933968184168916960, 

  41607939250187986849488309498865757934964797280, 

  720614911745512461611918130596030003676289336300, 

  12488149132570126719418439010195646125397100011920, 

  216544860562054593134160906994219210611674235418920, 

  3756996029385637316936199664140175184307538677619200, 

  65217708880091867222809412770976203671887863352995200, 

  1132692240424335329461008559322860625660096843564044800, 

  19682044848299254204780187424606161624293922138158848000, 

  342161666360328010168145138304650840941581198111307680000, 

  5950957372613238042937365323128808212313545207994095090800, 

  103544899011058176270363371934019286365853202810957930168000, 

  1802392915688776002461574283464036323570366183012829246320352]
 #OEIS: A268542,The diagonal of the rational function 1/(1 - x - y - x y - x z - y z).

gfun[listtorec](%, a(n))
[{(-567*n^3 - 4104*n^2 - 9549*n - 7140)*a(n + 1) + (-1281*n^3 - 10553*n^2 - 28546*n - 25400)*a(n + 2) + (-672*n^3 - 6208*n^2 - 18752*n - 18400)*a(n + 3) + (42*n^3 + 430*n^2 + 1424*n + 1504)*a(n + 4), a(0) = 1, a(1) = 4, a(2) = 42, a(3) = 520}, ogf]

#(iii).
DiagWalks3D({[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, 50);
[1, 5, 55, 749, 11251, 178835, 2949115, 49906925, 860905315, 

  15071939255, 266982872905, 4774722189275, 86070844191775, 

  1561948324845095, 28507384046515555, 522867506128197869, 

  9631571375362268515, 178094411589895650815, 

  3304192479145474141741, 61487420580006795749999, 

  1147310054439368264752621, 21460298038569915209597885, 

  402303281700710751346492045, 7557003072139605981578257499, 

  142216452439487217855645948751, 

  2680953577121013488247925591235, 

  50618646171303180157424116235125, 

  957111527948218432660657321864175, 

  18121739540270261728632231230077015, 

  343543557236065454833612395025716335, 

  6520361879189996271307536840076027315, 

  123890073917796829080870582463811238125, 

  2356385395407636535251297627384060933475, 

  44861516384576265010060080056738042597135, 

  854859275252481703527187912584359902505365, 

  16303683385055931306937559135507039289051575, 

  311190647408479503515035135447889843225653825, 

  5944262823858514467535608131557811648002762625, 

  113627280554332441572175257060408538344973808425, 

  2173522796137552287361594832873182554514084408175, 

  41603303651437038812509444164890710254979329256765, 

  796818898586340848384595439852318646653791885982025, 

  15270271969281638238724672178615586077051065833360775, 

  292804205106533694230148888112886916503795367402916085, 

  5617461573225955169248923401253208251816762860322509065, 

  107826322191169954469150116083770101402658959404009097505, 

  2070721317569227785240110965397887711335116126944031387125, 

  39785206672880588731577259303187378878045846931120125328475, 

  764744172323001796507565473412652088019110691985844385750095, 

  14706094191942557902358875596276810126406906869637116414501755, 

  282916070222353435645433592830184350982846989381549672223125905]
 #OEIS:A112019,a(n) = Sum_{k=0..n} binomial(n,k)*binomial(n+k,k)^2.

gfun[listtorec](%, a(n))
[{(-59*n^3 - 448*n^2 - 1084*n - 848)*a(n + 1) + (-295*n^3 - 2535*n^2 - 7185*n - 6740)*a(n + 2) + (-2301*n^3 - 22074*n^2 - 69941*n - 73044)*a(n + 3) + (118*n^3 + 1250*n^2 + 4336*n + 4896)*a(n + 4), a(0) = 1, a(1) = 5, a(2) = 55, a(3) = 749}, ogf]

##########################################################################################################

6.

DiagSeq4:=proc(f,x1,x2,x3,x4,N) local i;

if subs({x1=0,x2=0,x3=0,x4=0},denom(f))=0 then
 print(`The denominator of`, f, `should have a non-zero constant term `):
 RETURN(FAIL):
fi:

[seq(coeff(taylor(coeff(taylor(coeff(taylor(coeff(taylor(f,x1=0,N+1),x1,i),x2=0,N+1),x2,i),x3=0,N+1),x3,i),x4=0,N+1),x4,i),i=0..N)]:

end:

DiagWalks4D:=proc(S,N) local s,x1,x2,x3, x4:
if not (type(S, set) and type(N,integer) and N>=0) then
 print(`Bad input`):
 RETURN(FAIL):
fi:

DiagSeq4(1/(1-add(x^s[1]*y^s[2]*z^s[3]*q^s[4], s in S)),x,y,z,q,N) :
end:;

#########################################################################################################

7.