{"id":947,"date":"2016-09-20T19:18:47","date_gmt":"2016-09-20T19:18:47","guid":{"rendered":"http:\/\/wordpress.rose-hulman.edu\/rickert\/?page_id=947"},"modified":"2017-03-27T17:32:12","modified_gmt":"2017-03-27T17:32:12","slug":"ma215-discrete-and-combinatorial-algebra","status":"publish","type":"page","link":"https:\/\/wordpress.rose-hulman.edu\/rickert\/ma215-discrete-and-combinatorial-algebra\/","title":{"rendered":"MA215 Discrete and Combinatorial Algebra"},"content":{"rendered":"

MTRF 7 G310
\n<\/span> John Rickert, Associate Professor of Mathematics
\nOffice:<\/b> G-215A, Crapo Hall
\nPhone:<\/b> (812) 877-8473<\/p>\n

e-mail:<\/b> john.rickert@rose-hulman.edu<\/span><\/u><\/a><\/p>\n

Office hours this week: MTRF 8, or make an appointment, or drop in.
\nThe factorizations of elements in S5<\/span><\/sub><\/span><\/u><\/a> are now online.<\/p>\n

Exam #3, Tuesday, November 6<\/span><\/h3>\n

The book is closed book\/notes. You are encouraged to bring your computer to aid your calculations.
\nYou may use one page of notes or stored Maple\/Magma<\/i> commands, just not notes from class or the book.<\/p>\n

 <\/p>\n

In the “Questions” section, I’ll color the active questions green<\/span> so that they are easier (in theory) to find as you scan through the page. Please let me know<\/span><\/u><\/a> if I’ve missed anything.<\/p>\n

\n

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.
\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

\n

Homework<\/strong><\/h3>\n

For Friday, 8\/31: Read the introduction and section 1.1.1, do exercise 1.0.1 and hand in your definition of shuffled deck.
\nYour definitions of a shuffled dec<\/u>k<\/span><\/span><\/a> have been compiled for your perusal.
\nFor Monday, September 3: <\/i> Read section 1.1.2. Do exercises 1.1.1 and 1.1.2. Turn in<\/span> these exercises on Tuesday.<\/p>\n

Try to download Magma. Instructions for downloading magma are below.<\/p>\n

 <\/p>\n

For Tuesday, September 4:<\/i> Turn in exercises 1.1.1, 1.1.2.
\nRead Section 1.2. Do exercises 1.1.3 and 1.2.1 Turn in<\/span> these exercises on Friday, September 7.
\nFind a convincing explanation for the fact that the number of elements in S3<\/span><\/sub> is 6.
\nYou will find it useful to bring some sort of calculating device (calculator, computer, abacus) to class on Tuesday.<\/p>\n

 <\/p>\n

For Thursday, September 6: <\/i> Do exercises 1.1.3 and 1.2.1, read Section 1.3.1 (Perfect riffle shuffles), do exercises 1.3.1 and 1.3.2. Turn in 1.3.1 on Monday, September 10<\/span>
\nI know that you’re all disappointed, but there’s nothing to turn in for Thursday’s class. We will continue the discussion of exercises 1.1.3 and 1.2.1.
\nFor Friday, September 7: <\/i> Turn in exercises 1.1.3 and 1.2.1. Do your best on 1.1.3.3, make some sort of reasonable guess, explore a few more Sn<\/span><\/sub>, and explain your reasoning as well as possible.
\nReread Section 1.3.1 covering perfect riffle shuffles. Experiment a little and see what you can discover.
\nWhat is the mathematics behind the card trick?
\nFor Monday, September 10:<\/i> Turn in<\/span> Exercise 1.3.1
\nReread Section 1.3.1, read Section 1.3.2. Work exercises 1.3.2 and 1.3.3.
\nTry to see if you can prove that the average number of adjacencies in Sn<\/span><\/sub> is (2n-2)\/n.<\/p>\n

 <\/p>\n

For Tuesday, September 11:<\/i> Read Through Exercise 1.4.3. Be sure to work exercises 1.4.1, 1.4.2 and 1.4.3 and come to class with any questions that you have about the reeading or the exercises.<\/p>\n

Turn in exercises 1.3.2 and 1.3.3. We will have a quiz<\/span> covering PRS and TIAR. <\/span>
\nFor Thursday, September 13:<\/i> Turn in<\/span> exercise 1.4.2
\nRead through exercise 1.4.6.2. Be sure to work exercises 1.4.4, 1.4.5, 1.4.6.1 and 1.4.6.2.
\nReread section 1.4 and work enough examples so that you feel comfortable with composition of permutations and the fact that this composition is associative, i.e. (ab)c=a(bc), but not commutative, i.e. ab might not = ba.
\nFor Friday, September 14:<\/i> Read through exercise 1.4.6.2. Be sure to work exercises 1.4.4, 1.4.5, 1.4.6.1 and 1.4.6.2.
\nLook again at those association schemes and see if you can find a way of determining how many association schemes there are on n<\/i> permutations.<\/p>\n

For Monday, September 17:<\/i> Turn in<\/span> Exercise 1.4.4.3 (the S3<\/span><\/sub> commutativity table) and the commutativity experiment for S10<\/span><\/sub>:
\nRun 100,000,000 random trials using the magma code below<\/span>. How many times did the pair of elements commute?
\nRead through exercise 1.4.6.11 and come to class with questions.<\/p>\n

 <\/p>\n

For Tuesday, September 18:<\/i> Continue working the exercises 1.4.6. Read through Exercise 1.5.1 (as always, this includes working exercise 1.5.1)
\nFor Thursday, September 20:<\/i> Turn in exercises 1.4.6.2,1.4.6.8,1.4.6.10<\/span>. If you have completed the representation of your permutations as transpositions, you may turn those in seprately, though the representations as transpositions will not be due until Friday.<\/p>\n

If you did not pick up your permutations in class Tuesday, contact me<\/span><\/u><\/a> to get your permutations
\nRead through exercise 1.5.3 – you never know when there might be a pop quiz…
\nFor Friday, September 21<\/i>: Turn in<\/span> the representations of your permutations as products of transpositions. Read through exercise 1.5.5 (page 34)<\/p>\n

For Monday, September 24:<\/i> Read through exercise 1.5.5 (page 34). Think about how to express your permutations from S5<\/span><\/sub> as products of adjacent transpositions.<\/p>\n

 <\/p>\n

For Tuesday, September 25:<\/i> Read through exercise 1.6.1 (page 36). factorize the permutations of five elements that you have custody of into
\n2. Adjacent Trranspositions
\n3. {tau,rho}- factorization<\/p>\n

For Thursday, September 27:<\/i> Read through exercise 1.6.3 (page 40).
\nExam #1, Friday, September 28<\/span>. The average score on the exam was 79.4 out of 120.<\/p>\n

For Monday, October 1:<\/i> Read through exercise 1.8.1.<\/p>\n

 <\/p>\n

For Tuesday, October 2:<\/i> Turn in<\/span> the homework (redo of the exam). Read through exercise 1.8.2.<\/p>\n

For Thursday, October 4:<\/i> Turn in<\/span> exercises 1.8.1.3, 1.8.1.6, 1.8.2.1, 1.8.2.2
\nRead through exercise 1.9.3<\/p>\n

For Friday, October 5:<\/i> Read through the end of Section 1.9 (page 54).<\/p>\n

For Monday, October 8:<\/i> Read section 1.10 (through to top of page 61) and work the exercises.<\/p>\n

For Tuesday, October 9:<\/i> Read Section 1.11 and work the exercises.<\/p>\n

For Monday, October 15:<\/i> Turn in Exercise 1.11.2. Work exercises from Section 1.12 and come to class with questions and constructive comments about these exercises.<\/p>\n

For Tuesday, October 16:<\/i> Turn in<\/span> exercise 1.12.2. Read through the end of Section 2.2 (page 78).<\/p>\n

For Thursday, October 18:<\/i> Turn in<\/span> exercises 2.1.1.4 and 2.1.2.4. Read through the end of Section 2.4 (page 86).<\/p>\n

For Friday, October 19:<\/i> Read through the end of Section 2.5 (page 91)<\/p>\n

For Monday, October 22:<\/i> Turn in<\/span> Exercises 2.5.1.1, 2.5.3, 2.5.4.3. Read through exercise 2.7.2 (page 99).<\/p>\n

For Tuesday, October 23:<\/i> Read through the end of Chapter 2 (page 106). It wouldn’t hurt you to look at the exercises in Section 2.8, through they will not be assigned until later.<\/p>\n

Come to class with questions regarding the material for Thursday’s exam.<\/p>\n

For Thursday, October 25:<\/i> Exam #2. The average score on the exam was 87.2 out of 130.<\/p>\n

For Monday, October 29:<\/i> turn in<\/span> the exam make-up. Work some of the exercises in Section 2.8, Read through Exercise 3.1.1 (page 115)<\/p>\n

 <\/p>\n

For Tuesday, October 30: <\/i> Read through exercise 3.2.1.3 (page 120).<\/p>\n

For Thursday, November 1:<\/i> Turn in<\/span> Exercises 2.8.5, 3.0.1.1. Read through the end of page 125.<\/p>\n

For Friday, November 2:<\/i> Read through exercise 3.3.2, page 128.<\/p>\n

For Monday, November 5:<\/i> Read Section 3.4 through 3.4.2, (pages 140-149).<\/p>\n

For Thursday, November 8:<\/i> Read from Section 3.4.3 to the end of chapter 3.(page 149-152) As always, work the exercises along the way.
\n<\/span><\/p>\n

\n

 <\/p>\n

Questions from class<\/h4>\n

Thursday, August 30<\/i>: We had several possible definitions of a “shuffled” deck, some using an idea of probability, some referring to adjacent cards, some referring to construction of models. We also discussed the possibility that it’s not possible to shuffle a deck of cards. Our first goal is to make these statements precise.<\/span>
\n Is it possible to determine if a deck is shuffled?<\/span>
\n If so, how? If not, why not?<\/span>
\n How small can a deck be and still be shuffled?<\/span>
\n Good enough for play <–> shuffled <–> random \u00a0 \u00a0 \u00a0 \u00a0 What, precisely, do these words and phrases mean?<\/span>
\n Friday, August 31<\/i>: We saw that the order of a permutation is the least common multiple of the lengths of the cycles.<\/span>
\n The number of ways to write a permutation using disjoint cycle notation can get rather large. How large?<\/span>
\n Monday, September 3<\/i>: Why are there exactly 6 elements in the group of permutation of three elements, S3<\/span><\/sub>?<\/span>
\n What does it mean for a structure to be a group<\/i>?<\/span>
\n Tuesday, September 4: We looked at the “birthday problem” and saw that it was very likely that two people would have the same birthday. There was also 99.998% probability that two people would draw the same card.<\/span>
\n We looked at the exercises 1.2.1 and had solved 1.2.1.3 for k<\/i>=1 and k<\/i>=2. What’s the general answer?<\/span>
\nHow many identities are there in S<\/b>n<\/i><\/sub>? How many 2-cycles are there in S<\/b>n<\/i><\/sub>? How many 3-cycles are there in S<\/b>n<\/i><\/sub>?
\nThursday, September 6: What is the mathematics behind the card trick?
\nWhat is the average number of adjacencies in permutations of n<\/i> elements? { A(sn<\/span><\/sub>) }
\nWe saw that A(s0<\/span><\/sub>)=0 , \u00a0 A(s1<\/span><\/sub>)=0 , \u00a0 A(s2<\/span><\/sub>)=1 , \u00a0 A(s3<\/span><\/sub>)=4\/3 , \u00a0 A(s4<\/span><\/sub>)=3\/2 , \u00a0 A(s5<\/span><\/sub>)=8\/5
\nWe also observed that
\nin S2<\/span><\/sub>, both permutations have 1 adjacency.
\nin S3<\/span><\/sub>, 1 adjacency: 4 permutations, \u00a0 2 adjacencies: 2 permutations
\nin S4<\/span><\/sub>, 0 adj: 2 \u00a0 \u00a0 1 adj: 10 \u00a0 \u00a0 2 adj: 10 \u00a0 \u00a0 3 adj: 2
\nWhat sort of patterns exist here?
\nThe Magma<\/i> code that we used in class to count adjacencies;
\n s5:=SymmetricGroup(5);
\nc5:=0;
\nfor pi in s5 do
\nfor j in [1..4] do
\nif (Abs(j^pi-(j+1)^pi)eq 1) then
\nc5:=c5+1;
\nend if;
\nend for;
\nend for;
\nc5;
\n<\/span><\/tt> Remember, the instructions for loading Magma<\/span> through Tibia are down below.
\nAn explanation of the lines of code:
\ns5:=SymmetricGroup(5);<\/span><\/tt> gives us a shorthand way of referring to S5<\/span><\/sub>.
\nc5:=0; <\/span><\/tt> sets the counter variable, here named c5<\/span><\/tt> equal to zero. c5<\/span><\/tt> counts the number of adjacencies.
\nfor pi in s5 do <\/span><\/tt> sets up a do loop telling Magma<\/i> to perform these steps for all permutations, pi<\/span><\/tt>, in S5<\/span><\/sub>.
\n for j in [1..4] do <\/span><\/tt> sets up a sub-loop. j will be set equal to 1,2,3,4, in order and the ensuing steps will be performed.
\n if (Abs(j^pi-(j+1)^pi)eq 1) then <\/span><\/tt> The test for adjacency. j^pi<\/span><\/tt> is Magma<\/i>‘s notation for the position that is occupied by j<\/span><\/tt> after pi<\/span><\/tt> is applied. You should try this for several values on your own. Some examples: If pi=(1,3,5,4), then 1^pi=3, 2^pi=2, 3^pi=5, 4^pi=1, and 5^pi=4.
\nj^pi- (j+1)^pi looks at the difference between the new positions of j,j+1. If they are adjancent, then the difference will be +1 or -1, so we take the absolute value (Abs) and test to see if that absolute value is equal to 1 (eq 1<\/span><\/tt>). If they are adjacent, then proceed to the next step.
\n c5:=c5+1;<\/span><\/tt> We have found an adjacency, so add 1 to the adjacency counter.
\n end if; end for; end for; <\/span><\/tt> end the conditional and the loops.
\n c5;<\/span><\/tt> prints out the value of c5<\/span><\/tt> (number of adjacencies) found by Magma<\/i>.
\nFriday, September 7:<\/i> We have a conjecture that A(Sn<\/span><\/sub>)=(2n-2)\/n. It works for n=1,2,3,4,5,6. Can we prove that it is true for all n?
\nSo far we have two ideas for trying to attack this: 1. Try to come up with a systemic way to count the adjancencies and 2. Use mathematical induction and relate the number of adjacencies in sn+1<\/span><\/sub> to the adjacencies in sn<\/span><\/sub>.
\nWe looked at the cycle structre of rho4,6,o<\/span><\/sub> , rho4,6,i<\/span><\/sub> and rho2,8,o<\/span><\/sub> and made some observations. Why do those structures appear? Try some other permutations and see what happens.
\nSome Magma<\/i> code; s10:=SymmetricGroup(10); <\/span><\/tt> Let s10 be shorthand for the group of permutations on 10 elements.
\n rho46o:=(1,3,7,4,9,8,6,2,5,); <\/span><\/tt> defines the 4,6 out shuffle
\n 4^rho46o; <\/span><\/tt> gives an output of 9, this means that the element that was in the 4-th slot moves to the 9-th slot.
\n rho460o*rho46o; <\/span><\/tt> apply the shuffle twice.
\n rho46o^3; <\/span><\/tt> apply the shuffle three times.
\n for j in [1..6] do <\/span><\/tt> start a loop, letting j run from 1 to 6.
\n rho46o^j; <\/span><\/tt> compute the permuation applied j times.
\n end for; <\/span><\/tt> end the loop, printing the results.
\nTuesday, September 11:<\/i> Is there an “easy” way to determine the inverse of a permutation?
\nThursday, September 13: The number of association schemes for n<\/i> permutations is as follows:<\/p>\n

n <\/i>       1   2   3   4   5   6   7  ... n<\/i>\r\n#schema  ?   1   2   5  14  ??  ??  ... ???<\/pre>\n
Is there a systematic way to count these?
\nFriday, September 14:<\/i> We calculated the probability that two randomly selected elements in Sn<\/span><\/sub> commute for some small values of n<\/i>:<\/p>\n
n<\/i>        2   3    4     5       6\r\nProb.    1  1\/2  5\/24  7\/120  11\/720<\/pre>\n
Here is the Magma code for running the random commutativity trials in S10<\/span><\/sub>:
\n?  s10:=SymmetricGroup(10);
\nctr:=0;
\nfor j in [1..10000] do
\npi:=Random(s10);
\nfor k in [1..10000] do
\nmu:=random(s10);
\nif (pi*mu eq mu*pi) then
\nctr:=ctr+1;
\nend if;
\nend for;
\nend for;
\nctr;
\n<\/span><\/tt> Tuesday, September 17:<\/i> We observed that the permutation (1,7,4,3)(2,5,8,6) may be written as a product of six transpositions, (5,6)(6,8)(4,7)(2,5)(3,7)(1,7). Is it possible to write this permutation as a product of fewer than six transpositions?
\nWe observed that every 3-cycle may be written as a product of two transpositions.
\nThursday, September 20:<\/i> For a permutation alpha<\/i>, if T(alpha<\/i>) is the smallest number of transpositions that can be used to express alpha<\/i>. Then what is T(alpha<\/i>)? What are the smallest and largest values for T(alpha<\/i>), for alpha<\/i> in Sn<\/span><\/sub>? What is the average value of T(alpha<\/i>)?
\nAsk the same questions for AT(alpha<\/i>), the smallest number of adjacent transpositions that can be used to represent alpha<\/i>.
\nFriday, September 21:<\/i> We found the average number of adjacent transpositions needed to factor a random element of Sn<\/span><\/sub> for some small n<\/i>: n=2-> 1\/2 \u00a0 \u00a0 n=3 -> 3\/2 \u00a0 \u00a0 n=4 -> 3
\nMonday, September 24:<\/i> The average number of adjacent transpositions needed to factor a random element of Sn<\/span><\/sub> seems to follow the rule sn<\/span><\/sub>=sn-1<\/span><\/sub>+(n-1)\/2. Does this hold for larger n<\/i>?
\nThe number of adjacent transpositions in the factorization of the transposition (a,b) seems to be 2|b-a|-1.
\nThe number of adjacent transpositions in the factorization of the 3-cycle (a,b,c) seems to be 2[|b-a|+|c-b|] -2.
\nThe 4-cycles seem to be trickier.
\nThe factorizations of elements in S5<\/span><\/sub><\/span><\/u><\/a> are now online.
\nTuesday, September 25:<\/i> How many adjacent transpositions does it take to write any particular permutation? What is the average number of AT’s in the adjacent transposition factorization of permutations in Sn<\/span><\/sub>?
\nFor a permutation pi<\/i> in Sn<\/span><\/sub>, what is the largest possible order? We saw that if n>2 then the order is less than n!. For small n the largest possible orders are;<\/p>\n
n          2  3  4  5  6  7  8  9   10  ...  17 .... 28\r\nMax order  2  3  4  6  ?  ?  ?  ?  >=30 ... >=210  >=2310<\/pre>\n
Thursday, October 4:<\/i> The Maple<\/i> code to set up the distance function described in Section 1.9:
\n with(linalg);
\nd:=matrix(6,6,[ 0,0,0,.5,.5,0, 0,0,0,0,.5,.5, 0,0,0,.5,0,.5, .5,0,.5,0,0,0, .5,.5,0,0,0,0, 0,.5,.5,0,0,0] );<\/span><\/tt><\/p>\n
Delta := mtx -> sqrt( sum(sum( (mtx[i,j]-1\/6)^2 ,j=1..6), i=1..6) );<\/p>\n
plot( [ seq([k, Delta(evalm(d^k))],k=1..10) ] );
\nOr, you could set up a for loop:
\n for k from 1 to 10 do [k,Delta(evalm(d^k))]; od; <\/span><\/tt><\/span>
\nThe example matrix (d<\/span><\/tt>) used here is the transition matrix for S3<\/span><\/sub> induced by the adjacent transpositions. You will need to build the appropriate matrix for each of the other sets used to attempt to shuffle the deck.
\n<\/a>Tuesday, October 16:<\/i> Regarding the 4-by-4 array of exercise 1.12.2:<\/span><\/p>\n