#Do not post homework
#William Wang, 10/9/2020, Assignment 9

#1.
#My RUID: 193006310

#i. What is the coefficient of x^50*y^50 in (the bi - Taylor expansion around (0, 0) of the rational function/(-6*x^3 + 3*y^3 + x*y - x - 9*y + 1))

DiagSeq2(1/(-6*x^3 + 3*y^3 + x*y - x - 9*y + 1), x, y, 51)[51];
6646408999541076652068080610900325347546057864783935108826382170748881069481582951531

#ii. In how many ways can you walk from [0,0,0] to [30,30,30] if the fundamental ("atomic") steps are {[1,3,1],[9,1,1],[1,3,3]}?

DiagWalks3D({[1, 3, 1], [1, 3, 3], [9, 1, 1]}, 31)[31];
                               0





#2.

#3.

#4.
L1 := DiagWalks2D({[0, 1], [1, 0]}, 40);
L1 := [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]



#Yes, this sequence is in the OEIS. The OEIS number is A000984, and it represents the sequence of Central binomial coefficients.

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

  ]



L2 := DiagWalks2D({[0, 1], [1, 0], [1, 1]}, 40);
L2 := [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]



#Yes, this sequence is in the OEIS. The OEIS number is A001850, and it represents the sequence of Central Delannoy numbers.

gfun[listtorec](L2, f(n));
[{(-n - 3) f(n + 3) + (15 + 6 n) f(n + 2) + (-n - 2) f(n + 1), 

  f(0) = 1, f(1) = 3, f(2) = 13}, ogf]



L3 := DiagWalks2D({[0, 1], [0, 2], [1, 0], [2, 0]}, 40);
L3 := [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]



#Yes, this sequence is in the OEIS. The OEIS number is A036692.

gfun[listtorec](L3, f(n));
   [ //     3         2                \         
   [{ \352 n  + 2768 n  + 7088 n + 5920/ f(n + 1)
   [ \                                           

        /      3         2                  \         
      + \-484 n  - 4048 n  - 11184 n - 10204/ f(n + 2)

        /      3         2                \         
      + \-352 n  - 3120 n  - 9114 n - 8766/ f(n + 3)

        /    3        2                \                     
      + \55 n  + 515 n  + 1570 n + 1560/ f(n + 4), f(0) = 1, 

                                   \      ]
     f(1) = 2, f(2) = 14, f(3) = 84 }, ogf]
                                   /      ]



L4 := DiagWalks2D({[0, 1], [0, 2], [1, 0], [1, 1], [2, 0], [2, 2]}, 40);
L4 := [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]



#Yes, this sequence is in the OEIS. The OEIS number is A192365, and it represents the sequence of the number of lattice paths from (0,0) to (n,n).

gfun[listtorec](L4, f(n));
                              FAIL





#5.
L5 := DiagWalks3D({[0, 0, 1], [0, 1, 0], [1, 0, 0]}, 50);
L5 := [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

  ]



#Yes, this sequence is in the OEIS. The OEIS number is A006480.

gfun[listtorec](L5, f(n));
  [ //     2            \            / 2          \           
  [{ \-27 n  - 81 n - 60/ f(n + 1) + \n  + 4 n + 4/ f(n + 2), 
  [ \                                                         

                      \      ]
    f(0) = 1, f(1) = 6 }, ogf]
                      /      ]



L6 := DiagWalks3D({[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0]}, 50);
L6 := [1, 12, 366, 13800, 574650, 25335072, 1159174464, 

  54435558672, 2606102756730, 126634810078920, 6226427808402516, 

  309095505195676992, 15466884541698962736, 

  779158533743408851200, 39476348002042199114400, 

  2010009672816216740255520, 102786433923004507970614170, 

  5276251022208604662925459800, 271756933860993711724366208700, 

  14039277998343011628711905746800, 

  727252315696238557022534984870700, 

  37764880751121887313039958575379200, 

  1965422563808449412890295430818054400, 

  102495227281909699381783463162047132800, 

  5354970041086897812761458297700599417200, 

  280253445967795985374949681046491826228672, 

  14690203414442414488804435616003677125005664, 

  771145758055206185325123270375803815927594752, 

  40535111393558888204549814860087623044969451200, 

  2133396988805979421417749876652628015282264851200, 

  112414075475758921606964259480877886434070797013184, 

  5929871729841714045458911166849171019533021624697408, 

  313123390289637714002627008362148098260174168972675034, 

  16550232193253531985714855999704051055377963467520432760, 

  875560635260454356489361942807789613305081077980596270540, 

  46359554199069579288463172809754082827284084984898838030672, 

  2456644961038869801706615073425895021980932864902200262112564, 

  130279653108517639976758354437170962852596376876100805447410112, 

  6913919066654832963744519531958637434492466263682006729078707200, 367171782086071587467458355531097720216412429282114727440845564000, 19511768827254938354113862739108880763246752330825265262014793578220, 1037510398929516627148966207033858419555762487373981426443796377042800, 55200610029099959623515807356596976767210885771070967355433602508504280, 2938589569286212536590486262630110283025990019411230498644550657532659200, 156518789370105675267896440004274249687575888415847223295652244226422620800, 8340961607976571962127390483510811460971576022470901260753377982808697221120, 444711278738616413784836919962426295146210620570084837655782083914966928042240, 23721571393413819647977066296156715645024247640133445655593884520836999184113920, 1265912051310064280635840917314855243224946187946831139154971743379966813931366000, 67585010854648750921878833581024894922639793828847145262624184909933561603141224000, 3609744827592924661413187772242486099040834023425162454262836032182786302022845715616

  ]



#Yes, this sequence is in the OEIS. The OEIS number is A268550.

gfun[listtorec](L6, f(n));
[ //     3        2              \         
[{ \-27 n  - 216 n  - 537 n - 420/ f(n + 1)
[ \                                        

     /      3        2                \         
   + \-108 n  - 972 n  - 2856 n - 2760/ f(n + 2)

     /      3         2                \         
   + \-107 n  - 1070 n  - 3555 n - 3924/ f(n + 3)

     /   3       2            \                                
   + \2 n  + 22 n  + 80 n + 96/ f(n + 4), f(0) = 1, f(1) = 12, 

                          \      ]
  f(2) = 366, f(3) = 13800 }, ogf]
                          /      ]



L7 := DiagWalks3D({[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, 50);
L7 := [1, 13, 409, 16081, 699121, 32193253, 1538743249, 

  75494983297, 3776339263873, 191731486403293, 9850349744182729, 

  510958871182549297, 26716694098174738321, 

  1406361374518034383189, 74456543501901550262689, 

  3961518532003397434536961, 211689479080817606497324033, 

  11355093839222763705129084589, 611152040584076639660629371001, 

  32992715293059931135426553471761, 

  1785928841771860542254045576118961, 

  96911172224569232194932824208108613, 

  5270467807704579414484682944700358769, 

  287213644676816665906680936645329819521, 

  15680766179623682461630661030297010798721, 

  857571893091756331641940140097355880163453, 

  46973963172944977202727910807060985881451689, 

  2576772652630832656275932605907086940111339377, 

  141540787641837639320136114121658200931179616593, 

  7784538258657508660652462031144008486512866604213, 

  428640413427631149041048770590112944322715506882369, 

  23628123606792986935851796030780003314462148459339777, 

  1303800679858356079774571553973796225536623375893422081, 

  72013142566684877315111994424132400771955343409862378829, 

  3981127457175113432462190860469457579455753631169401222489, 

  220278176073659484888912410313772287136817252987695827947857, 

  12197958522794076959789698815043009205993219014651383908722801, 

  675980301513991624096988157440757503360011196866059741602960293, 37488198585998861098813404715099477312260118443516221239937803537, 2080427293641056563434057728372222517657299124252827683548849323137, 115529521297476837197139501380633144217236002375161490308999040854913, 6419511621663385997831314796447366631860222267471107294144653468930589, 356916570963046110679534748729845983893908879459295236484878580659385737, 19855241239168536707555464295895760723505837893991201188594918336921613233, 1105137221760674748545661525319453000682088680885272712939848614828915389713, 61543107868084361361391676376031033850864213319951522127208706959739202888213, 3428902212934148870854081217641012908417259736305956511691926602218703319650529, 191132322967101896859564178652374219333444043196404236613172938379705771476990977, 10658792664850073672594602456972915291440175739307353568383011632727070588566766593, 594660003855519889071153736436944301451740242981149561947327575771459757271152755693, 33190115704065737247762606124173439405825498746361477382254328350183554493297245110329

  ]



#Yes, this sequence is in the OEIS. The OEIS number is A126086.

gfun[listtorec](L7, f(n));
[ //   3       2            \         
[{ \3 n  + 23 n  + 56 n + 44/ f(n + 1)
[ \                                   

     /    3       2              \         
   + \-9 n  - 78 n  - 221 n - 206/ f(n + 2)

     /     3         2                \         
   + \171 n  + 1653 n  + 5281 n + 5570/ f(n + 3)

     /    3       2              \                                
   + \-3 n  - 32 n  - 112 n - 128/ f(n + 4), f(0) = 1, f(1) = 13, 

                          \      ]
  f(2) = 409, f(3) = 16081 }, ogf]
                          /      ]



#6.
DiagSeq4 := proc(f, w, x, y, z, N) local i:
if subs({w = 0, x = 0, y = 0, z = 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, w = 0, N + 1), w, i), x = 0, N + 1), x, i), y = 0, N + 1), y, i), z = 0, N + 1), z, i), i = 0 .. N)]:
end:

DiagWalks4D := proc(S, N) local s, w, x, y, z:
if not (type(S, set) and type(N, integer) and 0 <= N) then
 print(`Bad input`):
 RETURN(FAIL):
fi:
DiagSeq4(1/(1 - add(w^s[1]*x^s[2]*y^s[3]*z^s[4], s in S)), w, x, y, z, N):
end:

DiagWalks4D({[0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]}, 15);
 [1, 24, 2520, 369600, 63063000, 11732745024, 2308743493056, 

   472518347558400, 99561092450391000, 21452752266265320000, 

   4705360871073570227520, 1047071828879079131681280, 

   235809301462142612780721600, 53644737765488792839237440000, 

   12309355935372581458927646400000, 

   2845616726065971560165538537369600]