#TaerimKim,10/23/2020,Assignment 13 #1. Let A be the set of letters in your name e.g. in my case it is {b,d,e,i,g, o,l, r,n,z}. #(i) How many 100-letter "words" (i.e. sequences) in this alphabet are there where no two consonants can be adjacent? #Given condition, A:={t,a,e,r,i,m,k} #A:={t=1,a=2,e=3,r=4,i=5,m=6,k=7} #G:=[{a,e,i},{...}.{...},{a,ei},...,{a,e,i}] #also same as G:=[{2,3,5},{seq(i,i=1..7)},{seq(i,i=1..7)},{2,3,5},{seq(i,i=1..7)},{2,3,5},{2,3,5}] G:=[{2,3,5},{seq(i,i=1..7)},{seq(i,i=1..7)},{2,3,5},{seq(i,i=1..7)},{2,3,5},{2,3,5}] G := [{2, 3, 5}, {seq(i, i = 1 .. 7)}, {seq(i, i = 1 .. 7)}, {2, 3, 5}, {seq(i, i = 1 .. 7)}, {2, 3, 5}, {2, 3, 5}]; G := [{2, 3, 5}, {1, 2, 3, 4, 5, 6, 7}, {1, 2, 3, 4, 5, 6, 7}, {2, 3, 5}, {1, 2, 3, 4, 5, 6, 7}, {2, 3, 5}, {2, 3, 5}] GFt(G, 1, t); [ 2 [9 t + 3 t - 1 t t [---------------, - ---------------, - ---------------, [ 2 2 2 [12 t + 3 t - 1 12 t + 3 t - 1 12 t + 3 t - 1 2 2 3 t t 3 t - ---------------, - ---------------, - ---------------, 2 2 2 12 t + 3 t - 1 12 t + 3 t - 1 12 t + 3 t - 1 2 ] 3 t ] - ---------------] 2 ] 12 t + 3 t - 1] normal(add(convert(GFt(G, i, t), `+`), i = 1 .. 7)); 12 t + 7 - --------------- 2 12 t + 3 t - 1 f := %; 12 t + 7 f := - --------------- 2 12 t + 3 t - 1 coeff(taylor(f, t = 0, 101), t, 100); 10793271486991884823304570242538321538250649076573463016746759446695102631 #answer is 10793271486991884823304570242538321538250649076573463016746759446695102631 #(ii) #when no two vowels are adjacent #A:={t=1,a=2,e=3,r=4,i=5,m=6,k=7} H:=[{seq(i,i=1..7)},{1,4,6,7},{1,4,6,7},{seq(i,i=1..7)},{1,4,6,7},{seq(i,i=1..7)},{seq(i,i=1..7)}] H := [{1, 2, 3, 4, 5, 6, 7}, {1, 4, 6, 7}, {1, 4, 6, 7}, {1, 2, 3, 4, 5, 6, 7}, {1, 4, 6, 7}, {1, 2, 3, 4, 5, 6, 7}, {1, 2, 3, 4, 5, 6, 7}] normal(add(convert(GFt(H, i, t), `+`), i = 1 .. 7)) -(12*t + 7)/((2*t + 1)*(6*t - 1)) h := % h := -(12*t + 7)/((2*t + 1)*(6*t - 1)) coeff(taylor(h, t = 0, 101), t, 100) 4409900708625478616152659303316890288625720045692762295565792830344479880773632 #answer is 4409900708625478616152659303316890288625720045692762295565792830344479880773632 #(iii) when no vowels and no consonants can be adjacent #A:={t=1,a=2,e=3,r=4,i=5,m=6,k=7} J:=[{2,3,5},{1, 4, 6, 7},{1, 4, 6, 7},{2,3,5},{1, 4, 6, 7},{2,3,5},{2,3,5}] normal(add(convert(GFt(J, i, t), `+`), i = 1 .. 7)) -(24*t + 7)/(12*t^2 - 1) j := % j := -(24*t + 7)/(12*t^2 - 1) coeff(taylor(j, t = 0, 101), t, 100) 6370306705001504841329309692739796427449006822279610368 #the answer is 6370306705001504841329309692739796427449006822279610368 #(iv) #plot a as a function similar to above a := proc(n) local G, g; G := [{2, 3, 5}, {1, 4, 6, 7}, {1, 4, 6, 7}, {2, 3, 5}, {1, 4, 6, 7}, {2, 3, 5}, {2, 3, 5}]; g := normal(add(convert(GFt(G, i, t), `+`), i = 1 .. 7)); coeff(taylor(g, t = 0, n + 1), t, n); end proc f := proc(t) local i; add(a(i)*t^i, i = 0 .. 200); end proc #we go till 200 first 5797258216541018518088589651701579486112859682977261048249413048722784435310848561264391983078006135699013632*t^200 + 1656359490440291005168168471914736996032245623707788870928403728206509838660242446075540566593716038771146752*t^199 + 483104851378418209840715804308464957176071640248105087354117754060232036275904046772032665256500511308251136*t^198 + 138029957536690917097347372659561416336020468642315739244033644017209153221686870506295047216143003230928896*t^197 + 40258737614868184153392983692372079764672636687342090612843146171686003022992003897669388771375042609020928*t^196 + 11502496461390909758112281054963451361335039053526311603669470334767429435140572542191253934678583602577408*t^195 + 3354894801239015346116081974364339980389386390611840884403595514307166918582666991472449064281253550751744*t^194 + 958541371782575813176023421246954280111253254460525966972455861230619119595047711849271161223215300214784*t^193 + 279574566769917945509673497863694998365782199217653407033632959525597243215222249289370755356771129229312*t^192 + 79878447648547984431335285103912856675937771205043830581037988435884926632920642654105930101934608351232*t^191 + 23297880564159828792472791488641249863815183268137783919469413293799770267935187440780896279730927435776*t^190 + 6656537304045665369277940425326071389661480933753652548419832369657077219410053554508827508494550695936*t^189 + 1941490047013319066039399290720104155317931939011481993289117774483314188994598953398408023310910619648*t^188 + 554711442003805447439828368777172615805123411146137712368319364138089768284171129542402292374545891328*t^187 + 161790837251109922169949940893342012943160994917623499440759814540276182416216579449867335275909218304*t^186 + 46225953500317120619985697398097717983760284262178142697359947011507480690347594128533524364545490944*t^185 + 13482569770925826847495828407778501078596749576468624953396651211689681868018048287488944606325768192*t^184 + 3852162791693093384998808116508143165313357021848178558113328917625623390862299510711127030378790912*t^183 + 1123547480910485570624652367314875089883062464705718746116387600974140155668170690624078717193814016*t^182 + 321013565974424448749900676375678597109446418487348213176110743135468615905191625892593919198232576*t^181 + 93628956742540464218721030609572924156921872058809895509698966747845012972347557552006559766151168*t^180 + 26751130497868704062491723031306549759120534873945684431342561927955717992099302157716159933186048*t^179 + 7802413061878372018226752550797743679743489338234157959141580562320417747695629796000546647179264*t^178 + 2229260874822392005207643585942212479926711239495473702611880160662976499341608513143013327765504*t^177 + 650201088489864334852229379233145306645290778186179829928465046860034812307969149666712220598272*t^176 + 185771739568532667100636965495184373327225936624622808550990013388581374945134042761917777313792*t^175 + 54183424040822027904352448269428775553774231515514985827372087238336234358997429138892685049856*t^174 + 15480978297377722258386413791265364443935494718718567379249167782381781245427836896826481442816*t^173 + 4515285336735168992029370689119064629481185959626248818947673936528019529916452428241057087488*t^172 + 1290081524781476854865534482605447036994624559893213948270763981865148437118986408068873453568*t^171 + 376273778061264082669114224093255385790098829968854068245639494710668294159704369020088090624*t^170 + 107506793731789737905461206883787253082885379991101162355896998488762369759915534005739454464*t^169 + 31356148171772006889092852007771282149174902497404505687136624559222357846642030751674007552*t^168 + 8958899477649144825455100573648937756907114999258430196324749874063530813326294500478287872*t^167 + 2613012347647667240757737667314273512431241874783708807261385379935196487220169229306167296*t^166 + 746574956470762068787925047804078146408926249938202516360395822838627567777191208373190656*t^165 + 217751028970638936729811472276189459369270156231975733938448781661266373935014102442180608*t^164 + 62214579705896839065660420650339845534077187494850209696699651903218963981432600697765888*t^163 + 18145919080886578060817622689682454947439179685997977828204065138438864494584508536848384*t^162 + 5184548308824736588805035054194987127839765624570850808058304325268246998452716724813824*t^161 + 1512159923407214838401468557473537912286598307166498152350338761536572041215375711404032*t^160 + 432045692402061382400419587849582260653313802047570900671525360439020583204393060401152*t^159 + 126013326950601236533455713122794826023883192263874846029194896794714336767947975950336*t^158 + 36003807700171781866701632320798521721109483503964241722627113369918381933699421700096*t^157 + 10501110579216769711121309426899568835323599355322903835766241399559528063995664662528*t^156 + 3000317308347648488891802693399876810092456958663686810218926114159865161141618475008*t^155 + 875092548268064142593442452241630736276966612943575319647186783296627338666305388544*t^154 + 250026442362304040740983557783323067507704746555307234184910509513322096761801539584*t^153 + 72924379022338678549453537686802561356413884411964609970598898608052278222192115712*t^152 + 20835536863525336728415296481943588958975395546275602848742542459443508063483461632*t^151 + 6077031585194889879121128140566880113034490367663717497549908217337689851849342976*t^150 + 1736294738627111394034608040161965746581282962189633570728545204953625671956955136*t^149 + 506419298766240823260094011713906676086207530638643124795825684778140820987445248*t^148 + 144691228218925949502884003346830478881773580182469464227378767079468805996412928*t^147 + 42201608230520068605007834309492223007183960886553593732985473731511735082287104*t^146 + 12057602351577162458573666945569206573481131681872455352281563923289067166367744*t^145 + 3516800685876672383750652859124351917265330073879466144415456144292644590190592*t^144 + 1004800195964763538214472245464100547790094306822704612690130326940755597197312*t^143 + 293066723823056031979221071593695993105444172823288845367954678691053715849216*t^142 + 83733349663730294851206020455341712315841192235225384390844193911729633099776*t^141 + 24422226985254669331601755966141332758787014401940737113996223224254476320768*t^140 + 6977779138644191237600501704611809359653432686268782032570349492644136091648*t^139 + 2035185582104555777633479663845111063232251200161728092833018602021206360064*t^138 + 581481594887015936466708475384317446637786057189065169380862457720344674304*t^137 + 169598798508712981469456638653759255269354266680144007736084883501767196672*t^136 + 48456799573917994705559039615359787219815504765755430781738538143362056192*t^135 + 14133233209059415122454719887813271272446188890012000644673740291813933056*t^134 + 4038066631159832892129919967946648934984625397146285898478211511946838016*t^133 + 1177769434088284593537893323984439272703849074167666720389478357651161088*t^132 + 336505552596652741010826663995554077915385449762190491539850959328903168*t^131 + 98147452840690382794824443665369939391987422847305560032456529804263424*t^130 + 28042129383054395084235555332962839826282120813515874294987579944075264*t^129 + 8178954403390865232902036972114161615998951903942130002704710817021952*t^128 + 2336844115254532923686296277746903318856843401126322857915631662006272*t^127 + 681579533615905436075169747676180134666579325328510833558725901418496*t^126 + 194737009604544410307191356478908609904736950093860238159635971833856*t^125 + 56798294467992119672930812306348344555548277110709236129893825118208*t^124 + 16228084133712034192265946373242384158728079174488353179969664319488*t^123 + 4733191205666009972744234358862362046295689759225769677491152093184*t^122 + 1352340344476002849355495531103532013227339931207362764997472026624*t^121 + 394432600472167497728686196571863503857974146602147473124262674432*t^120 + 112695028706333570779624627591961001102278327600613563749789335552*t^119 + 32869383372680624810723849714321958654831178883512289427021889536*t^118 + 9391252392194464231635385632663416758523193966717796979149111296*t^117 + 2739115281056718734226987476193496554569264906959357452251824128*t^116 + 782604366016205352636282136055284729876932830559816414929092608*t^115 + 228259606754726561185582289682791379547438742246613121020985344*t^114 + 65217030501350446053023511337940394156411069213318034577424384*t^113 + 19021633896227213432131857473565948295619895187217760085082112*t^112 + 5434752541779203837751959278161699513034255767776502881452032*t^111 + 1585136158018934452677654789463829024634991265601480007090176*t^110 + 452896045148266986479329939846808292752854647314708573454336*t^109 + 132094679834911204389804565788652418719582605466790000590848*t^108 + 37741337095688915539944161653900691062737887276225714454528*t^107 + 11007889986242600365817047149054368226631883788899166715904*t^106 + 3145111424640742961662013471158390921894823939685476204544*t^105 + 917324165520216697151420595754530685552656982408263892992*t^104 + 262092618720061913471834455929865910157901994973789683712*t^103 + 76443680460018058095951716312877557129388081867355324416*t^102 + 21841051560005159455986204660822159179825166247815806976*t^101 + 6370306705001504841329309692739796427449006822279610368*t^100 + 1820087630000429954665517055068513264985430520651317248*t^99 + 530858892083458736777442474394983035620750568523300864*t^98 + 151673969166702496222126421255709438748785876720943104*t^97 + 44238241006954894731453539532915252968395880710275072*t^96 + 12639497430558541351843868437975786562398823060078592*t^95 + 3686520083912907894287794961076271080699656725856256*t^94 + 1053291452546545112653655703164648880199901921673216*t^93 + 307210006992742324523982913423022590058304727154688*t^92 + 87774287712212092721137975263720740016658493472768*t^91 + 25600833916061860376998576118585215838192060596224*t^90 + 7314523976017674393428164605310061668054874456064*t^89 + 2133402826338488364749881343215434653182671716352*t^88 + 609543664668139532785680383775838472337906204672*t^87 + 177783568861540697062490111934619554431889309696*t^86 + 50795305389011627732140031981319872694825517056*t^85 + 14815297405128391421874175994551629535990775808*t^84 + 4232942115750968977678335998443322724568793088*t^83 + 1234608117094032618489514666212635794665897984*t^82 + 352745176312580748139861333203610227047399424*t^81 + 102884009757836051540792888851052982888824832*t^80 + 29395431359381729011655111100300852253949952*t^79 + 8573667479819670961732740737587748574068736*t^78 + 2449619279948477417637925925025071021162496*t^77 + 714472289984972580144395061465645714505728*t^76 + 204134939995706451469827160418755918430208*t^75 + 59539357498747715012032921788803809542144*t^74 + 17011244999642204289152263368229659869184*t^73 + 4961613124895642917669410149066984128512*t^72 + 1417603749970183690762688614019138322432*t^71 + 413467760407970243139117512422248677376*t^70 + 118133645830848640896890717834928193536*t^69 + 34455646700664186928259792701854056448*t^68 + 9844470485904053408074226486244016128*t^67 + 2871303891722015577354982725154504704*t^66 + 820372540492004450672852207187001344*t^65 + 239275324310167964779581893762875392*t^64 + 68364378374333704222737683932250112*t^63 + 19939610359180663731631824480239616*t^62 + 5697031531194475351894806994354176*t^61 + 1661634196598388644302652040019968*t^60 + 474752627599539612657900582862848*t^59 + 138469516383199053691887670001664*t^58 + 39562718966628301054825048571904*t^57 + 11539126365266587807657305833472*t^56 + 3296893247219025087902087380992*t^55 + 961593863772215650638108819456*t^54 + 274741103934918757325173948416*t^53 + 80132821981017970886509068288*t^52 + 22895091994576563110431162368*t^51 + 6677735165084830907209089024*t^50 + 1907924332881380259202596864*t^49 + 556477930423735908934090752*t^48 + 158993694406781688266883072*t^47 + 46373160868644659077840896*t^46 + 13249474533898474022240256*t^45 + 3864430072387054923153408*t^44 + 1104122877824872835186688*t^43 + 322035839365587910262784*t^42 + 92010239818739402932224*t^41 + 26836319947132325855232*t^40 + 7667519984894950244352*t^39 + 2236359995594360487936*t^38 + 638959998741245853696*t^37 + 186363332966196707328*t^36 + 53246666561770487808*t^35 + 15530277747183058944*t^34 + 4437222213480873984*t^33 + 1294189812265254912*t^32 + 369768517790072832*t^31 + 107849151022104576*t^30 + 30814043149172736*t^29 + 8987429251842048*t^28 + 2567836929097728*t^27 + 748952437653504*t^26 + 213986410758144*t^25 + 62412703137792*t^24 + 17832200896512*t^23 + 5201058594816*t^22 + 1486016741376*t^21 + 433421549568*t^20 + 123834728448*t^19 + 36118462464*t^18 + 10319560704*t^17 + 3009871872*t^16 + 859963392*t^15 + 250822656*t^14 + 71663616*t^13 + 20901888*t^12 + 5971968*t^11 + 1741824*t^10 + 497664*t^9 + 145152*t^8 + 41472*t^7 + 12096*t^6 + 3456*t^5 + 1008*t^4 + 288*t^3 + 84*t^2 + 24*t + 7 #if i goes to infinity, f(t) will go to infinity ################################################################################################# #2. lets construct the graph using the given information #I am going to use abbriviated notation for graphing #F=Farmer; W=Wolf; S=Sheep; C=Cabbage #This is the notation I will be using # # L / R # "FWSC/----" # #We will Start with "FWSC/" and end with "/FWSC" # # # 4)W/CFS -> 6)WSF/C #1)FWSC/ -> 2)WC/FS -> 3)WCF/S -> -> 8)S/FCW -> 9) FS/CW ->10)/FSCW # 5)C/WFS -> 7)CFS/W # #Now that we got the algorithm, lets plot this into graph #We have 10 elements with each element corresponding with edge of # #1 -> {2} #2 -> {3} #3 -> {4,5} #4 -> {6} #5 -> {7} #6 -> {8} #7 -> {8} #8 -> {9} #9 -> {10} #10 -> {} # #So we plot this into graph G:=[{2},{3},{4,5},{6},{7},{8},{8},{9},{10},{}] #using Paths fuction from vertices 1 to vertices 10 seq(Paths(G,1,10,k),k=1..10) {}, {}, {}, {}, {}, {}, {[1, 2, 3, 4, 6, 8, 9, 10], [1, 2, 3, 5, 7, 8, 9, 10]}, {}, {}, {} #Just like we found with algorithm, Paths function using graph showed exactly 2 way with 8 steps to complete the riddle. #We know that we got the right answer because it is consistent with algorithm. #################################################################################################### 3. #so lets do a different approach #Here we are given with as many elements(n) with a pair of two element that cant be left alone #So that means that our algorithm can start by moving either s1 or s2 first then comback to get the remaining n-2(except s2) in any order(permutation) then lastly move s2 to complete the riddle Riddle := proc (S, s) local s1, s2, k, L, l, R, a; #First of all, I am going to initiate the s1,s2 into the last element of L, equivalent to S. L := S; l := s; L := L minus l; s1 := l[1]; s2 := l[2]; L := [op(L), s1]; L := [op(L), s2]; #now, the last two elements are s1 and s2 #so initiate empty set of R then move either s2 first k := nops(L); R := {}; if L[k] = s2 then R:= [op(R), L[k]]; L := [op(1 .. k-1, L)]; printf("the first way of moving the elements are by moving %g first\n", s2); printf("then, we can move others except %g in any order\n",s1); printf("which gives us (%g-2)! way of moving the elements to other side\n", k); print(combinat:-permute({op(1..k-2, L)})); printf("the second way of moving the elements are by moving %g this time which also produce same number of ways \n", s1); printf("so the total number of ways is 2*(%a-2)!=%g \n", k, 2*(k - 2)!); end if; end proc #now we test with some examples #results Riddle({1, 2, 3, 4, 5}, {1, 3}); the first way of moving the elements are by moving 3 first then, we can move others except 1 in any order which gives us (5-2)! way of moving the elements to other side [[2, 4, 5], [2, 5, 4], [4, 2, 5], [4, 5, 2], [5, 2, 4], [5, 4, 2]] the second way of moving the elements are by moving 1 this time which also produce same number of ways so the total number of ways is 2*(5-2)!=12 ############################################################################################## 4. #we are using similar method that was used in 2. #M=missonary; C=cannibal; B=boat position #we will use the format # L / R # "M,C,B/M,C,B" #we start with "33B/000" and have to end with "000/33B" # # # 2)310/02B 12)02B/310 #1)33B/000 -> -> 4)32B/010 -> 5)300/03B -> 6)31B/020 -> 7)110/22B -> 8)220B/110 -> 9)020/31B -> 10)03B/300 -> 11)010/32B -> -> 14)000/33B # 3)220/11B 13)11B/220 # #By plotting the algorithm we have 14 elements with each element having edge of #1 -> {2,3} #2 -> {4} #3 -> {4} #4 -> {5} #5 -> {6} #6 -> {7} #7 -> {8} #8 -> {9} #9 -> {10} #10 -> {11} #11 -> {12,13} #12 -> {14} #13 -> {14} #14 -> {} #In the end, we get the graph G of G:=[{2,3},{4},{4},{5},{6},{7},{8},{9},{10},{11},{12,13},{14},{14},{}] #so we use Paths fuction from vertices 1 to vertices 14 seq(Paths(G,1,14,k),k=1..13) {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {[1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14], [1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14], [1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14], [1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14]}, {}, {} #The result shows that we have total of 4 ways with 12 steps to solve the riddle, which is equivalent to the above algorithm as well. So we know Paths function is consistent with the result. #################################################################################################