Foundations of Discrete Mathematics, Math 328, Fall 2008
This site was updated Nov. 21, 2008
(Recent updates will usually be above the first horizontal line. The syllabus is below.)

HW due Monday, Nov. 24:  Read through 7.4, page 386. First problem:  #1 Suppose we distribute r (indistinguishable) balls into n (distinguishable) cells. If the balls are indistinguishable, we can call the number of different ways to do this the number of selections. Theorem 7.8, page 382, applies, but uses s and t as the letters. Which letter is the r and which the n?  
There are 216 16-digit strings of 0's and 1's. #3:  How many of them have exactly four 1's, no two of which are together?   Include 0000010100100001, but not  0010000110001000.
#3:  Roll ten indistinguishable dice. How many results are distinguishable?

Later:  page 385, 3, 5, 8, 15, 18, 24.  We will do Section 7.5 shortly, and 7.6 and 7.7 are interesting, but we will not do computer programming.

Nov. 19
Counting is related to the concepts of one-to-one and onto. If you use the Multiplication Principle (The Fundamental Principle of Counting) to count, you must make sure
    1) every possibility corresponds to a sequence of tasks (onto)
    2) the sequence of tasks yields each possibility only once (one-to-one).
We have seen examples, such as counting flushes, in which it is easy to make errors by constructing a sequence of tasks that yields the same result in more than one way.
    For the number of hands that are flushes, task 1 is "pick a suit" and task 2 is "chose the 5 cards of that suit from the eligible 13" (and when you are done, subtract off the count of the straight flushes).  This yields all possible flushes and each is counted only once.
    Do not do
    task 1, pick any card first (52 ways) and task 2, pick four more of that suit from the eligible 12.  Why not? Because you can the same hand in different ways. The sequence-to-hands map is not one-to-one.  This yields all possible flushes, but that is only half the requirement. The hard part seems to be satisfying the requirement that each is counted only once.

HW due Friday, Nov. 21 (revised):  Consider a 7-card hand from a 52-card deck. Count the number which are:
xxxxyyy (4-of-a-kind plus three of another, a full house(?) in 7-card stuff), three-pair (xxyyzzw), two triples (xxxyyyz), two-pair, one-pair.
Also:  page 373, 33, 34, read through page 378, page 378: 14, 16, 18
Nov. 17
Wednesday, Nov. 19 HW revised:   #1 Count the three-of-a-kind hands. #2 Count two-pair hands. #3 Count one-pair hands.
    In class we began: For a flush:  task 1)  pick a suit.  task 2) choose 5 cards from that suit:  4 C(13, 5).  
    Then, subtract of the straight flushes already counted.
    #4  What, precisely, is wrong with counting flushes this way?  task 1)  Pick a card (52)  task 2) fill out the hand with four more cards of that suit from the remaining 12:  C(12, 4).  Get 52C(12,4) and subtract off the 36 straight flushes already counted.
    # 5-9 page 364, 32 (give a combinatoric argument), page 371ff: 4, 5, 7, 10

Note:  Some games allow straights to begin with an Ace as A-2-3-4-5.  We did not in our count. If you want to, we can.

 Nov. 14
HW due Monday, Nov. 17:  Hand in your original exam and with it separate solutions to the problems you missed, with comments in addition to the solutions that demonstrate (to yourself and to me) that you now understand them. For each, answer "What do you see now that you didn't see then?"

HW due Wednesday,  Nov. 19:  page 364, 32 (give a combinatoric argument), page 371ff: 4, 5, 7, 10, 23, 35 (3-D space)

HW due Friday, Nov. 21 (see above for a revision of this):   page 373, 33, 34, read through page 378, page 378: 14, 16, 18, 19, 24, 26, 28, 31

Nov. 6
    How is your list of advice to yourself about proofs coming along? Here is a list of "Thou Shalt Nots".

    Here is a list of proof guidelines.

HW due Friday, Nov. 14:  Combinatorics. page 364:  25, 28, 31, 37.  Read (7.2).

 There is an exam on Chapter 7, Group Theory, Wednesday, Nov. 12. Bring your cardboard triangle.
Nov. 5
 Wednesday, Nov. 5 I lectured on the value of "To show" as scratch work to decide what to do. Look at the definitions (again and again) to see what to do. If you want to show "f(G) is a group" (as in 7.3.3C) decide what that means. Refer to the definition of "group" with four parts. Then decide what each part means. Refer to the definitions to tell you what you are supposed to do.

    The chapter on "Counting Techniques" from Discrete Mathematicsby Dossey and Otto, et al., is now at Cards n' Copies at the SUB (basment floor, south end past the bookstore). You are required to have a copy for the reminder of the course. It costs $4.28. Please go buy one soon.  
    A scanned copy is available on line at the Library Reserve web site:

http://www.lib.montana.edu/reserves/math328/

but it is cheaper to buy a photocopy than to print copies from the web and you must have a hard copy.

HW due Friday, Nov. 7:  (7.2) B18 (again). Also, hand in old HW that you did not do well before. 

HW due Monday, Nov. 10:  Read the first section of the "Counting Techniques" chapter that you bought.  Do page 363-4, #2, 6, 8, 20, 24.

Wednesday, Nov. 12: Exam on Group Theory, Chapter 7.1-7.3.  No HW due.  The exam will not cover 7.4.  It will emphasize groups and subgroups.



The Final exam is 8:00-9:50 am, Tuesday, Dec. 16.
(You can final times for other classes at:  http://www.montana.edu/registrar/pdfs/RegistrationHandbook.pdf )

Oops!  In Section 6.3 there are two B13's!  I assigned "B13" and will accept whichever one you did. However, if you are just starting, try the second one.

HW due Wednesday, Nov. 5:  (7.3) B3, and this problem:  If G and G' are groups and f :G -> G' is a homomorphism, then {g in G | f(g) = e' in G'} is a group (with the operation from G).  
    [This day I lectured on the value of "To show" as scratch work to decide what to do. Look at the definitions (again and again) to see what to do.  If you want to show "f(G) is a group" (as in 7.3.3C) decide what that means. Refer to the definition of "group" with four parts. Then decide what each part means. Refer to the definitions.]

The typos in the text are listed here. Thank you for continuing to report them. They will be fixed in the next edition.
Oct. 30
HW due Monday, Nov. 3: (7.3)  B9, B13
    I am expanding office hours to include Thursday mornings, and I remind you that I am often available in the afternoons; just arrange a specific time.  GroupTheory is abstract and grasping the concepts requires serious concentration. I expect you will need 20 minutes of quiet concentration just to get in the flow. To do math at this high level, you need to set aside a big block of time in which you can work without interruption. Don't expect to create group-theory proofs during several short time periods. One long time period is better.
    I see many of you frequently. Good.  Keep it up. The rest of you are more than welcome to see me for help. If you are getting lost, you really should come by during my hours (I am in the office and available more hours than that states) or by appointment. Wilson Hall, 2-238, east wing, south wall, near the catwalk.
Oct. 29
HW due Friday, Oct. 31.  (7.2) B29 for Z6 (or, in general, but Z6 will do). B13, B17.


HW due Wednesday, Oct. 29:  (7.2) B27, 29.  Read (7.3) and hand in B1.

HW due Friday, Oct. 31 (postponed).  Boo!  (7.3)  B9, B13
I was very pleased with class Friday, especially because you created conjectures. You are thinking like mathematicians!

HW for Monday, Oct. 27:  (7.2) B16, 17, 18

HW due Friday, Oct. 24:  (7.1) B28a,b,c,d,e  (7.2) A8, 10,  B7, 15
Oct. 21
For Wednesday, Oct. 22, you may simplify A3 to answer for Z10 (and not Zn, which is more general).

HW due Wednesday Oct. 22:  (7.2) A1, 3, 4, 6
Oct. 17
Old printings of the text have a typo (since corrected) in the Friday, Oct 17, HW. There are two A9's in the old printing. Do the first "A9" (about Z20) and also do the second "A9" (which is the new A11 about U9) with part a) changed to 7*5 instead of 7*6.
HW due Monday, Oct. 20:  (7.1) B3, 4, 14, 18  (added Oct. 17)

    How is your list of advice to yourself about proofs coming along? Here is a list of "Thou Shalt Nots".

    Here is a list of proof guidelines.

Exam on Chapter 6, Monday Oct. 13.  The emphasis will be on proofs we have done in class or on the homework. The emphasis will be on things very similar to things we have done a lot. Study the main results, but not the most difficult ones, and the homework.
      Sections 6.1 through 6.5 (not 6.6) will be covered. Anything from 6.5 will be short and conceptual.

HW due Friday, Oct. 10:  No written HW due. Come prepared to ask questions about number theory.

We skip Section 6.6. Number theory is endlessly interesting (and Section 6.6 has some material teachers would like to know), but it is time to move on. The rest of the course has modern algebra (group theory) and combinatorics. It is time for group theory, Chapter 7.

HW due Wednesday, Oct. 15:  Read 7.1 through Example 8, page 304f.  Then do (7.1) A4

HW due Friday, Oct. 17:   (7.1)  A5, A9, A11  Old printings of the text have a typo (since corrected) in the Friday, Oct 17, HW. There are two A9's in the old printing. Do the first "A9" (about Z20) and also do the second "A9" (which is the new A11 about U9) with part a) changed to 7*5 instead of 7*6.

Typos discovered so far in the fourth printing are reported here. 
Monday, Oct. 6 HW:  You are not responsible for the proofs in 6.5. (6.5) A4.   Read (6.5), the rest.

HW due Wednesday, Oct. 8:  (6.5)  B11, B14
Assembled advice on how to do proofs is here.

HW due Friday, Sept. 19:  (6.2) B12, 17, and two of these three: B32, 34, 35.

HW due Monday, Sept. 22:  (6.2)  Read Section 6.3 through at least Theorem 6, "The Fundamental Theorem of Arithmetic," and note how Theorem 4 was used.  Then note how Theorem 4 depended upon the Diophantine material in Section 6.2. Note how Section 6.2 created the tools necessary to fix Conjecture 6.1.26, "a|bc => a|b or a|c", which was false.
    From 6.2, do B22 and B23. Show work!

HW due Wednesday, Sept. 24:  (6.3)  B4, 10, 11, 14  (analyze the given argument for "3|b => 3|b2 ")

HW due Friday, Sept 26:  Exam on 5.1, 5.2, 6.1 and 6.2 Friday. Due: (6.3)  B20 (this has something in common with Example 1 in Section 3.4 on Contradiction), and (6.4)  B8 and B9.

HW due Monday, Sept 29:  Read Section 6.4 up through Example 8: 324139 mod 713  [The 4th printing, new this Fall, finishes 6.4 after Example 8 . If you have an earlier edition, it may have material on The Chinese Remainder Theorem and Casting Out Nines that has been moved to Section 6.6.]   No HW due.

HW due Wednesday, Oct. 1:  No HW due. Exercises in modular arithmetic.

HW due Friday, Oct. 3:  Read 6.5. (6.5) A1, 5, B1a,b,c (there is no d), B7


HW due Wednesday, Sept. 17:  (6.2)  A9, B3, 4
HW due Friday, Sept. 12:  (6.1)  A5, B1, 5, 18
    There will be a quiz on 5.1 and 5.2.

HW due Monday, Sept. 15:  (6.1) B14, 20, 26, 30.  [Not all results need to be proved from scratch. You may cite earlier results as prior.]  Also, begin a sheet outlining the principles of proof.  That is, write out, concisely in outline form that makes sense to you, the principles that you (we) often find useful when it comes to resolving a conjecture and proving it true or false. Hand it in to show me you are thinking about this (This course is more about principles than it is about particular proofs.) . I will hand it back and you can add to it or reorganize it repeatedly throughout the semester.
HW due Wednesday, Sept. 10:  (5.2) B11, 15, 17
    Read  Section 6.1, at least through Conjecture 9.  (6.1) A1, A4.
 HW due Friday, Sept 5:  Read 5.1. Re-read any earlier sections that are relevant such as 1.1 and the logic in Chapter 1.
    Hand in:  Section 5.1, B5, 13, 21, and
        Problem 4 [Hard]:  Conjecture:  There is a 1-1 and onto map from (0, 1] to (0, 1).
Read: "Is Google is making us stupid?"  Read about it here:  http://www.npr.org/templates/story/story.php?storyId=91543814
    (Really, it is short, so read it!)  
The original article in The Atlantic magazine is not short (I don't expect you to read it):   http://www.theatlantic.com/doc/200807/google   It has provoked quite a buzz, so search on the title wouldl get many hits.  

HW due Monday, Sept 8:  Read Section 5.2 (Aways read the section). A6, 11, B1, 6, 16, 18 (address Conjecture 16) 
 
Later:  We will not finish Chapter 5 (although you might find it useful) because it is time to move ahead to number theory, the subject of Chapter 6.  Read 6.1 (or more) and be prepared to consider its conjectures.
    The first day you got a white handout with a list of  terms from the prerequisite Math 256. If there are any you are not comfortable with, please bring it up in class or see me in my office. They are all critical.

                       
Syllabus for Foundations of Discrete Mathematics, Math 328, at Montana State University.

Goals:  You will learn to read, write, and think like an advanced mathematician. You will learn to read symbolic mathematics with comprehension, express mathematical thoughts clearly, reason logically, recognize and employ common patterns of mathematical thought, and read and write proofs. Also, you will learn the basics, including proofs, of number theory, group theory in abstract algebra, combinatorics, and probability theory. 

Instructor:  Dr. Warren Esty, 994-5354, Wilson 2-238 (East wing, South wall). 
Office hours:  I love the material and am happy to help.
Mondays, Wednesdays, and Fridays:  8:30-9:45, 11:00-11:45.  
Mondays and Wednesdays, also:  2:10-3:00.
If you want to meet some other hour, just ask in class or call (994-5354). For example, Mondays 3:10ff are also good for appointments.
Tuesdays:  By appointment.
Thursdays:  Reserved for math research

Required text:  Proof: Introduction to Higher Mathematics, third edition, by Warren W. Esty and Norah C. Esty. There is no solutions manual.
    Some other material will be placed on-line at the library reserve site, including  the material on combinatorics. 

Course Content:  The course covers several topics of "discrete mathematics," including number theory and group theory (from Esty and Esty) and combinatorics and probability theory (from another source to be provided later), focusing on proofs in each area.
    There will be required reading and homework due each day. It will be listed on this website. Bookmark this site. 

Prerequisite:  Math 256 (Foundations of Higher Mathematics) or explicit consent of Dr. Esty.  Do not attempt this course without Math 256 first.
    This course is primarily for students who wish to be math teachers or math majors. 

Time and room:  10:00 am, MWF, Wilson Hall, 1-133.  

Etiquette. Proper etiquette is required. During class, students will not engage in any potentially distracting behavior such as reading a newspaper, whispering about non-math subjects, or using electronic devices. Cell phones must be turned off and unavailable.No text messaging! Pagers or watches that make a sound, however quietly, must have the sound off. Also, no type of earphones is allowed.

Attendence:  Attendence is expected. More than a couple unexcused abscences is unacceptable. Of course, excuses for academic reasons, illness, participation in university sporting events, and significant life events will be accepted.
    Every day in class you will learn about common mistakes and how to avoid them. It is not possible to recogonize your own errors in logic, so you must take every opportunity to see deceptive errors in reasoning explained and to get feedback about your own and your classmates errors in reasoning. Students who miss a day are missing a significant lesson that cannot easily be recovered from the text alone.

Homework.  There will be homework due almost every day. It is important that it be attempted on time. The work you hand in need not be all correct, but it must display serious effort. More than a few late homeworks is not acceptable.
    You are expected to work, on average, about two hours outside class for each class hour.  (If the hours you spend regularly exceed this amount, please let me know.)
    You must read the assigned sections. Learning to read math with full comprehension is one of your goals, and you learn to read by reading.  Reading is part of those two hours.
    Bring your text to class every day. We will use it in class regularly.
 
Exams and Grading.  There will be unit exams, frequent quizzes, regular homework, class participation, and a comprehensive final.
   To receive full credit, daily homework must be handed in on time. Homework handed in late will receive half credit.
Exam dates will be announced on this site.
Homework and its due dates will be announced on this site.
The final exam will be 8:00-9:50 am, Tuesday, Dec. 16, as in the MSU Handbook. Arrange your winter-break schedule so you can take the final at the scheduled time.
 
Conflicts.  You are required to take all exams and the final exam at the scheduled hours (unless you have another exam or class scheduled at that hour, in which case we will make arrangements). Any exceptions must be approved well in advance, and in no case will exceptions be made for two exams.

Read each section. Do not skip the harder parts. In fact, when the going gets rough you need to slow down and read it several times until it makes sense. If it remains unclear, ask me! 

This is hard!  But, you will be learning an extremely valuable skill.
Don't skim.
Don't expect that only high points are important (Don't read only the bold parts).
Don't skip the rest of the paragraph because you want to move along to the next high point. 
Really do read the next paragraph in the text..