{"id":1080,"date":"2016-09-23T15:16:01","date_gmt":"2016-09-23T15:16:01","guid":{"rendered":"http:\/\/wordpress.rose-hulman.edu\/rickert\/?page_id=1080"},"modified":"2017-03-27T18:03:26","modified_gmt":"2017-03-27T18:03:26","slug":"ma315-discrete-and-combinatorial-algebra","status":"publish","type":"page","link":"https:\/\/wordpress.rose-hulman.edu\/rickert\/ma315-discrete-and-combinatorial-algebra\/","title":{"rendered":"MA315 Discrete and Combinatorial Algebra"},"content":{"rendered":"<p><span style=\"font-size: large\">MTRF 8 G222<br \/>\n<\/span> John Rickert, Associate Professor of Mathematics<br \/>\n<b>Office:<\/b> G-215A, Crapo Hall<br \/>\n<b>Phone:<\/b> (812) 877-8473<\/p>\n<p><b>e-mail:<\/b> <a href=\"mailto:john.rickert@rose-hulman.edu\"><u><span style=\"color: #000080\">john.rickert@rose-hulman.edu<\/span><\/u><\/a><\/p>\n<p>Office hours this week: MTR 7,9, or make an appointment, or drop in.<br \/>\nOn some Thursdays I might be proctoring IFYCSEM exams.<\/p>\n<p>The average score on the final exam was 74.7. You may come to my office and pick-up your exam.<\/p>\n<p>A sketch of the answers to <a href=\"http:\/\/wordpress.rose-hulman.edu\/rickert\/ma315-discrete-and-combinatorial-algebra-quiz-page\/\" target=\"_blank\"><u><span style=\"color: #000080\">Quiz #7<\/span><\/u><\/a> is online.<\/p>\n<p>Please <a href=\"mailto:john.rickert@rose-hulman.edu\"><u><span style=\"color: #000080\">let me know<\/span><\/u><\/a> if I&#8217;ve missed anything.<\/p>\n<hr \/>\n<p>The main goal in this class is to have you (the student) perform as an active learner. To do this you will need to do the exercises, raise questions about structures that you are studying, create hypotheses and test these hypotheses.<br \/>\nThe quizzes, examinations and homework done during the year will be worth 80% of the course grade. The final examination will be worth 20% of the grade.<\/p>\n<hr \/>\n<p>&nbsp;<\/p>\n<h4>Homework<\/h4>\n<p>To <span style=\"color: #000080\">Homework for our next class<\/span> &#8230;<br \/>\nFor Tuesday 12\/1: Read Section 4.0 and work the exercises in 4.0.1, 4.0.2.<br \/>\nFor Thursday 12\/2: Read through section 4.2.2 work the exercises. Think about exercise 4.0.2.1<br \/>\n<span style=\"color: #aa00aa\">The average score on Thursday&#8217;s quiz was 16.7 out of 20<\/span><br \/>\n<b>For Friday 12\/3<\/b>: Read Section 4.2.3<br \/>\nWork the exercises<br \/>\n<b>For Monday 12\/7<\/b>: Read Section 4.2.4<br \/>\nWork the exercises.<br \/>\nProve or disprove: <i>Rounding to the nearest 10<\/i> is an equivalence relation over the integers.<br \/>\nHow about : <i>Rounding<\/i> is an congruence relation?<br \/>\n<b>For Tuesday 12\/8<\/b>: It was observed that the breakdown into &#8220;even&#8221; and &#8220;odd&#8221; permutations is a congruence relation over S<sub><span style=\"font-size: small\">n<\/span><\/sub>. Can you prove this?<br \/>\nRead through exercise 4.3.2. Work exercises 4.3.1, 4.3.2. Be sure to be prepared to work exercise 4.3.2<br \/>\n<b>For Thursday 12\/10<\/b>: Quiz #3 on Thursday, Proving equivalence.<br \/>\nRead through exercise 4.3.2. Work exercises 4.3.1, 4.3.2. Be sure to be prepared to work exercise 4.3.2<br \/>\n<b>For Friday 12\/11<\/b>: Read through Exercise 4.3.3<br \/>\nWork exercise 4.3.3<br \/>\n<span style=\"color: #ff0000\">Hand in<\/span> exercise 4.3.2<br \/>\n<b>For Monday, 12\/14<\/b>: Read through exercise 4.3.6 (page 189)<br \/>\nWork through the work in the reading and do exercises 4.3.4,4.3.5 and 4.3.6<br \/>\n<b> For Tuesday, 12\/15<\/b>: Read through Fact 4.6<br \/>\n<b> For Thursday, 12\/17<\/b>: Read Through exercises 4.3.8<br \/>\nWork exercises 4.3.8.<br \/>\n<b> For Friday, 12\/18<\/b> Get a better understanding of cycle index polynomials.<br \/>\nHow many symmetries does a cube have? What is the group of rotational symmetries of a cube?<br \/>\nHand In Exercise 4.3.8.2<br \/>\n<b>For Monday, January 4<\/b>: Re-read Chapter 4 through exercises 4.3.8 to try to gain a better understanding of the concepts and notations used.<br \/>\nExam #1, Monday, January 11, 1999<br \/>\n<b> For Thursday, January 14<\/b>: Read section 5.0<br \/>\nDo exercises 5.0.1, 5.0.2<br \/>\n<b> For Friday, January 15<\/b>: <span style=\"color: #ff0000\">Hand In<\/span> Exam re-write.<br \/>\nRead through exercise 5.1.5. Do exercises 5.1.1 &#8211; 5.1.5, Especially 5.1.5.<br \/>\n<b>For Monday, January 18<\/b>: Read through exercise 5.1.8. Do exercises 5.1.6, 5.1.7, 5.1.8<br \/>\n<b>For Tuesday, January 19<\/b> Read Section 5.2. Do exercises 5.2.1 and 5.2.2<br \/>\n<b>For Thursday, January 21<\/b>: Read through exercise 5.3.3.<br \/>\nDo the exercises.<br \/>\n<b>For Monday, January 25<\/b>: Finish Section 5.3. <span style=\"color: #ff0000\">Hand in<\/span> exercises 5.3.2.4 and 5.3.3.1.<br \/>\n<b>For Tuesday, January 26<\/b>: Read through section 5.4.1.<br \/>\n<b>For Thursday, January 28<\/b>: Read through section 5.4.2<br \/>\nUnderstand how errors are detected and corrected using the code C<sub><span style=\"font-size: small\">N<\/span><\/sub>.<br \/>\n<b>For Tuesday, February 2<\/b> Work some of the exercises in 5.5.<br \/>\nCome to class with questions about the chapter 5 material.<br \/>\n<b>Thursday, February 4<\/b>: Chapter 5 Exam<br \/>\n<b>For Tuesday, February 9<\/b>: <span style=\"color: #ff0000\">Hand in<\/span> Exam re-write.<br \/>\n<b>For Monday, February 15<\/b>: Read through exercise 6.3.2.<br \/>\n<a href=\"http:\/\/wordpress.rose-hulman.edu\/rickert\/ma315-discrete-and-combinatorial-algebra-quiz-page\/\" target=\"_blank\"><u><span style=\"color: #000080\">Quiz #7 answers<\/span><\/u><\/a><\/p>\n<p>For Tuesday, February 16: Read through exercise 6.3.6<\/p>\n<hr \/>\n<p>&nbsp;<\/p>\n<h4>Questions from class<\/h4>\n<p>To <span style=\"color: #000080\">today&#8217;s questions &#8230;<\/span><a href=\"http:\/\/www.rose-hulman.edu\/~rickert\/Classes\/ma315\/index.html#top\"><br \/>\n<span style=\"color: #000000\"><b>Tuesday 12\/1<\/b>: Problem 4.0.2.1: Is 20 the correct number of equivalence classes? If so, why? If not, why not?<\/span><br \/>\n<span style=\"color: #000000\"><b>Thursday 12\/3<\/b>: <\/span><\/a><span style=\"color: #333399\">Equivalence relations used on the quiz:<\/span><a href=\"http:\/\/www.rose-hulman.edu\/~rickert\/Classes\/ma315\/index.html#top\"><span style=\"color: #000000\"> Two elements are equivalent if&#8230;<\/span><br \/>\n<\/a><\/p>\n<ul>\n<li>their FFPA factorizations correspond to the same partition of 4.<\/li>\n<li>the first term in the list form of the permutations are equal.<\/li>\n<li>they have the same order.<\/li>\n<li>The number of transpositions required to describe the permutations is the same for each element.<\/li>\n<\/ul>\n<p><a href=\"http:\/\/www.rose-hulman.edu\/~rickert\/Classes\/ma315\/index.html#top\"><br \/>\n<span style=\"color: #000000\"><b>Friday, 12\/4<\/b>: Is <i>Rounding to the nearest factor of 10<\/i> an equivalence relation on the integers?<\/span><br \/>\n<span style=\"color: #000000\"> Prove your assertion.<\/span><br \/>\n<span style=\"color: #000000\"> <b>Monday, 12\/7<\/b> Suppose G,+ and G\\0,* are groups and ~ is an equivalence relation over G,+ and G\\0,*.<\/span><br \/>\n<span style=\"color: #000000\"> Is it possible for ~ to be a congruence relation over one of these (either G,+ or G\\0,*) and not the other?<\/span><br \/>\n<span style=\"color: #2255aa\">Dennis Lin observes that a~b iff |a|=|b| is an equivalence relation over the integers (and rationals, reals, complex numbers, etc.) so that it is a congruence relation with respect to multiplication, but not addition.<\/span><br \/>\n<\/a><span style=\"color: #000000\">It was observed that the breakdown into &#8220;even&#8221; and &#8220;odd&#8221; permutations is a congruence relation over S<sub><span style=\"font-size: small\">n<\/span><\/sub>. Can you prove this?<\/span><\/p>\n<p><b>Tuesday, 12\/8<\/b> How many equivalence relations are there over S<sub><span style=\"font-size: small\">3<\/span><\/sub>?<br \/>\n<span style=\"color: #00ff00\"> How many congruence relations are there over S<sub><span style=\"font-size: small\">3<\/span><\/sub> with respect to composition of permutations?<br \/>\n<\/span> Peter Webb noticed that any function f(x) can be used to define an equivalence relation by: a~b &lt;-&gt; f(a)=f(b).<br \/>\nCan you prove that this is an equivalence relation?<br \/>\n<b> Thursday, 12\/10<\/b>: <span style=\"color: #2255aa\">Jonathan Webster and Dennis Lin came to the conclusion that there are 203 equivalence relations on S<sub><span style=\"font-size: small\">3<\/span><\/sub>.<\/span> Is this correct?<br \/>\nNathan Froyd observed that the sequence begins 1,1,2,5,15,52,203,&#8230; and 203=52*1+15*5+5*10+2*10+1*5+1*1.<br \/>\nThe number of congruence relations is still an open question.<br \/>\n<b> For Thursday, 12\/17<\/b> Get a better understanding of cycle index polynomials.<br \/>\nHow many symmetries does a cube have? What is the group of rotational symmetries of a cube?<br \/>\n<b> Monday, 1\/18<\/b>: We have devised a code of size 32 which corrects one error. We have seen that a code that corrects one error, consisting of 15 bits, has size no more than 270.<br \/>\nWhat is the largest error correcting code on 15 bits?<br \/>\n<b>Monday, 1\/25<\/b>: We now have a code of weight 5 &#8211; a code that can correct two errors. How do we perform such a correction efficiently?<br \/>\n<b>Tuesday, 1\/26<\/b>: Question: What do we get from the quadratic polynomial in step 4 if (s<sub><span style=\"font-size: small\">1<\/span><\/sub>)<sup><span style=\"font-size: small\">3<\/span><\/sup> = s<sub><span style=\"font-size: small\">2<\/span><\/sub>?<br \/>\nHere&#8217;s the (probably inefficient) code that I&#8217;m using to get <i>Maple<\/i> to do the error correction:<br \/>\n<tt><span style=\"font-family: Courier New\">c.0:=0: c.1:=1: c.2:=y: c.3:=y+1:<br \/>\nc.4:=y^2: c.5:=y^2+1: c.6:=y^2+y: c.7:=y^2+y+1:<br \/>\nfor k from 8 to 15 do c.k:=y^3+c.(k-8) od:<br \/>\nmd:=y^4+y^3+1;<br \/>\nreduce:= poly-&gt; modp(rem(expand(poly),md,y),2);<br \/>\nThe matrix, unfortunately, must be typed in. (OK. I admit, there's a sneaky way to do it, but I'd like to leave <i><span style=\"font-size: xx-small\">some<\/span><\/i> extra credit activities for you.)<br \/>\nIf the matrix is called <tt>en<\/tt> and the received message is called <tt>r<\/tt> then we look at <tt>evalf(en&amp;*r);<\/tt><br \/>\nand determine s<sub><span style=\"font-size: small\">1<\/span><\/sub> and s<sub><span style=\"font-size: small\">2<\/span><\/sub>. (Again, <i><span style=\"font-size: xx-small\">Maple<\/span><\/i> coding can be created ...) If there are at least two errors we determine the coefficients of the quadratic, call them c<sub><span style=\"font-size: small\">i<\/span><\/sub> and c<sub><span style=\"font-size: small\">j<\/span><\/sub> for now, and let <i>Maple<\/i> chug through the calculations: <tt>seq( [k,reduce(c.k*c.k+ c.3*c.k+ c.2)],k=1..15);<\/tt><br \/>\nPlease <\/span><\/tt><tt><a href=\"mailto:john.rickert@rose-hulman.edu%22\"><u><span style=\"color: #000080;font-family: Courier New\">inform me<\/span><\/u><\/a><span style=\"font-family: Courier New\"> if there are any typos that make the code fail to perform.<br \/>\n<b>Monday, February 8<\/b>: When building a field with eight elements, we must have 1+1=0. This produces a field with elements 0,1,a,a+1,a<sup><span style=\"font-size: small\">2<\/span><\/sup>,a<sup><span style=\"font-size: small\">2<\/span><\/sup>+1,a<sup><span style=\"font-size: small\">2<\/span><\/sup>+a,a<sup><span style=\"font-size: small\">2<\/span><\/sup>+a+1.<br \/>\nWe saw in class that a<sup><span style=\"font-size: small\">3<\/span><\/sup> cannot be equal to a, a<sup><span style=\"font-size: small\">2<\/span><\/sup> or a<sup><span style=\"font-size: small\">2<\/span><\/sup>+a. The remaining possibilities were 1,a+1,a<sup><span style=\"font-size: small\">2<\/span><\/sup>+1,a<sup><span style=\"font-size: small\">2<\/span><\/sup>+a+1. Which of these really do produce fields?<br \/>\n<b>Thursday, February 11<\/b>: Are there finite fields of size <i>p<sup><span style=\"font-size: small\">n<\/span><\/sup><\/i> for all natural numbers <i>n<\/i> and all primes <i>p<\/i>?<\/span><\/tt><\/p>\n<p><span style=\"color: #339966\"><strong>Friday, February 12<\/strong>: What is the value of <em><span style=\"font-size: large\">I<\/span><sub><span style=\"font-size: small\">n<\/span><\/sub><\/em>, the number of irreducible polynomials of degree <em><span style=\"font-size: large\">n<\/span><\/em> in <strong><span style=\"font-size: large\">Z<\/span><\/strong><sub><span style=\"font-size: small\">2<\/span><\/sub>[y]?<\/span><br \/>\n<tt><span style=\"font-family: Courier New\"><b>Monday, February 15<\/b>: <\/span><a href=\"http:\/\/wordpress.rose-hulman.edu\/rickert\/ma315-discrete-and-combinatorial-algebra-quiz-page\/\" target=\"_blank\"><u><span style=\"color: #000080;font-family: Courier New\">Quiz #7 answers<\/span><\/u><\/a><span style=\"font-family: Courier New\"> are available.<br \/>\nCan we further streamline the calculation of <i>I<sub><span style=\"font-size: small\">n<\/span><\/sub><\/i> through the use of generating functions?<br \/>\n<\/span><\/tt><\/p>\n<hr \/>\n<p><tt><\/tt><tt><span style=\"font-family: Courier New\">A question from class: <i>How do we know that the Maclaurin series expansion of s<sup><span style=\"font-size: small\">2<\/span><\/sup>\/((1-3s)(1-s-s<sup><span style=\"font-size: small\">2<\/span><\/sup>)) has integer coefficients?<\/i><br \/>\nExpanding the denominator gives (1-3s)(1-s-s<sup><span style=\"font-size: small\">2<\/span><\/sup>)=1-4s+2s<sup><span style=\"font-size: small\">2<\/span><\/sup>+3s<sup><span style=\"font-size: small\">3<\/span><\/sup>. We note that a sequence defined by <i>a<sub><span style=\"font-size: small\">n<\/span><\/sub>=4a<sub><span style=\"font-size: small\">n-1<\/span><\/sub>-2a<sub><span style=\"font-size: small\">n-2<\/span><\/sub>-3a<sub><span style=\"font-size: small\">n-3<\/span><\/sub><\/i> with integer values for <i>a<sub><span style=\"font-size: small\">0<\/span><\/sub><\/i>,<i>a<sub><span style=\"font-size: small\">1<\/span><\/sub><\/i> and <i>a<sub><span style=\"font-size: small\">2<\/span><\/sub><\/i> consists solely of integers and has generating function <i>A(s)<\/i>, where<br \/>\n<i>A(s)-sA(s)-s<sup><span style=\"font-size: small\">2<\/span><\/sup>A(a) = a<sub><span style=\"font-size: small\">0<\/span><\/sub>+(a<sub><span style=\"font-size: small\">1<\/span><\/sub>-4a<sub><span style=\"font-size: small\">0<\/span><\/sub>)s +(a<sub><span style=\"font-size: small\">2<\/span><\/sub>-4a<sub><span style=\"font-size: small\">1<\/span><\/sub>+a<sub><span style=\"font-size: small\">0<\/span><\/sub>)s<sup><span style=\"font-size: small\">2<\/span><\/sup> <\/i>. Thus, <i>(a<sub><span style=\"font-size: small\">0<\/span><\/sub>+(a<sub><span style=\"font-size: small\">1<\/span><\/sub>-4a<sub><span style=\"font-size: small\">0<\/span><\/sub>)s +(a<sub><span style=\"font-size: small\">2<\/span><\/sub>-4a<sub><span style=\"font-size: small\">1<\/span><\/sub>+a<sub><span style=\"font-size: small\">0<\/span><\/sub>)s<sup><span style=\"font-size: small\">2<\/span><\/sup>) \/ (1-s-s<sup><span style=\"font-size: small\">2<\/span><\/sup>)<\/i> is the generating function for such a sequence.<br \/>\n<i>s<sup><span style=\"font-size: small\">2<\/span><\/sup>\/((1-3s)(1-s-s<sup><span style=\"font-size: small\">2<\/span><\/sup>))=s<sup><span style=\"font-size: small\">2<\/span><\/sup>* 1\/((1-3s)(1-s-s<sup><span style=\"font-size: small\">2<\/span><\/sup>))<\/i>. <i>1\/((1-3s)(1-s-s<sup><span style=\"font-size: small\">2<\/span><\/sup>))<\/i> is the generating function for the sequence <i>a<sub><span style=\"font-size: small\">n<\/span><\/sub>=4a<sub><span style=\"font-size: small\">n-1<\/span><\/sub>-2a<sub><span style=\"font-size: small\">n-2<\/span><\/sub>-3a<sub><span style=\"font-size: small\">n-3<\/span><\/sub><\/i> with <i>a<sub><span style=\"font-size: small\">0<\/span><\/sub><\/i>=1, <i>a<sub><span style=\"font-size: small\">1<\/span><\/sub>-4a<sub><span style=\"font-size: small\">0<\/span><\/sub><\/i>=0, and <i>a<sub><span style=\"font-size: small\">2<\/span><\/sub>-4a<sub><span style=\"font-size: small\">1<\/span><\/sub>+2a<sub><span style=\"font-size: small\">0<\/span><\/sub><\/i>=0. Therefore, all of the coefficients of <i>s<sup><span style=\"font-size: small\">n<\/span><\/sup><\/i> will be integers.<\/span><\/tt><\/p>\n<hr \/>\n<p><tt><\/tt><tt><span style=\"font-family: Courier New\">Go to <\/span><\/tt><\/p>\n<ul>\n<li>the <a href=\"http:\/\/www.rose-hulman.edu\/academics\/academic-departments\/mathematics.aspx\" target=\"_blank\"><u><span style=\"color: #000080\">Mathematics Department Home Page. <\/span><\/u><\/a><\/li>\n<li>my <a href=\"http:\/\/wordpress.rose-hulman.edu\/rickert\/ma215-discrete-and-combinatorial-algebra\/\" target=\"_blank\"><u><span style=\"color: #000080\">MA215 page<\/span><\/u><\/a><\/li>\n<li>my <a href=\"http:\/\/wordpress.rose-hulman.edu\/rickert\/jhrs-class-pages-list\/\" target=\"_blank\"><u><span style=\"color: #000080\">classes page<\/span><\/u><\/a><\/li>\n<li>my <a href=\"http:\/\/wordpress.rose-hulman.edu\/rickert\/\" target=\"_blank\"><u><span style=\"color: #000080\">home page<\/span><\/u><\/a><\/li>\n<\/ul>\n<p><a href=\"http:\/\/www.rose-hulman.edu\/~rickert\/Classes\/ma315\/index.html#top\"><tt>\u00a0<\/tt><\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p class=\"excerpt\">MTRF 8 G222 John Rickert, Associate Professor of Mathematics Office: G-215A, Crapo Hall Phone: (812) 877-8473 e-mail: john.rickert@rose-hulman.edu Office hours this week: MTR 7,9, or make an appointment, or drop in. On some Thursdays I might be proctoring IFYCSEM exams. The average score on the final exam was 74.7. You may come to my office and pick-up your exam. A&hellip;<\/p>\n<p class=\"more-link-p\"><a class=\"btn btn-default\" href=\"https:\/\/wordpress.rose-hulman.edu\/rickert\/ma315-discrete-and-combinatorial-algebra\/\">Read more<\/a><\/p>\n","protected":false},"author":812,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1080","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/wordpress.rose-hulman.edu\/rickert\/wp-json\/wp\/v2\/pages\/1080","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.rose-hulman.edu\/rickert\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/wordpress.rose-hulman.edu\/rickert\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.rose-hulman.edu\/rickert\/wp-json\/wp\/v2\/users\/812"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.rose-hulman.edu\/rickert\/wp-json\/wp\/v2\/comments?post=1080"}],"version-history":[{"count":9,"href":"https:\/\/wordpress.rose-hulman.edu\/rickert\/wp-json\/wp\/v2\/pages\/1080\/revisions"}],"predecessor-version":[{"id":3665,"href":"https:\/\/wordpress.rose-hulman.edu\/rickert\/wp-json\/wp\/v2\/pages\/1080\/revisions\/3665"}],"wp:attachment":[{"href":"https:\/\/wordpress.rose-hulman.edu\/rickert\/wp-json\/wp\/v2\/media?parent=1080"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}