Information on this syllabus is subject to change. Any updates will be posted to this site, and the class will be notified of any major updates by email or in class announcement. In particular, any required changes in course delivery, such as transition to remote delivery only, may necessitate significant modifications to this syllabus.
| Date/Date due | Event | |
| Monday, Aug. 19 | First day of class | |
| Friday, Aug. 23 | Last day to add a course | |
| Friday, Aug. 30 | Last day to drop a course | |
| Monday, Sep. 2 | Labor Day (no class) | |
| HW 1 | Wednesday, Sep. 4 |
Self-checked problems (these problems need not be turned in)
Grimaldi, Section 1.1/1.2 (p. 11–14): 1–13 Grimaldi, Section 1.3 (p. 24–26): 1, 3, 5, 11, 13 Graded problems (these problems should be turned in) Grimaldi, Section 1.1/1.2 (p. 11–14): 4, 6, 14 Grimaldi, Section 1.3 (p. 24–26): 2, 12 Homework is to be turned in in gradable condition. In particular:
|
| HW 2 | Monday, Sep. 9 |
Self-checked problems (these problems need not be turned in)
Grimaldi, Section 1.3 (p. 24–26): 23, 25, 27, 29 Grimaldi, Section 1.4 (p. 34–36): 1, 3, 5, 7, 19 Grimaldi, Section 8.1 (p. 396–397): 3, 5 Graded problems (these problems should be turned in) Grimaldi, Section 1.3 (p. 24–26): 26, 30 Grimaldi, Section 1.4 (p. 34–36): 14 Grimaldi, Section 8.1 (p. 396–397): 4 |
| HW 3 | Monday, Sep. 16 |
Self-checked problems (these problems need not be turned in)
Grimaldi, Section 8.1 (p. 396–397): 7, 11, 13, 17 Grimaldi, Section 8.2 (p. 401): 3, 5, 7; the mathematically inclined students may be interested in Problem 8 Graded problems (these problems should be turned in) Grimaldi, Section 8.1 (p. 396–397): 6 Grimaldi, Section 8.2 (p. 401): 2, 6 |
| Friday, Sep. 20 | First midterm exam–good luck! You will be allowed a non-graphing calculator and a double-sided 3 inch by 5 inch card of notes. | |
| HW 4 | Friday, Sep. 27 |
Self-checked problems (these problems need not be turned in)
Grimaldi, Section 8.3 (p. 403–404): 3, 7, 11, 13 Grimaldi, Section 9.1 (p. 417–418): 1, 3, 5 Graded problems (these problems should be turned in) Grimaldi, Section 8.3 (p. 403–404): 2, 12 Grimaldi, Section 9.1 (p. 417–418): 2 Be careful! Your book has an annoying habit of asking two-part questions without clearly marking them as part (a) and part (b). |
| HW 5 | Friday, Oct. 4 |
Self-checked problems (these problems need not be turned in)
Grimaldi, Section 9.2 (p. 431–432): 1, 2, 3, 5, 7, 9, 13, 15 Grimaldi, Section 9.3 (p. 435): 1, 3, 5, 7 Graded problems (these problems should be turned in) Grimaldi, Section 9.2 (p. 431–432): 6 (AB 5) In how many ways can Traci select 40 marbles from a large bin of red, yellow, and blue marbles if the number of blue marbles selected must be a multiple of 3? Grimaldi, Section 9.3 (p. 435): 2 |
| HW 6 | Friday, Oct. 11 |
Self-checked problems (these problems need not be turned in)
Grimaldi, Section 9.5 (p. 442): 1, 3, 7 Grimaldi, Section 10.1 (p. 455): 1, 2, 3, 5 Grimaldi, Section 10.2 (p. 468–470): 5, 11, 13 (you only need to find the recurrence relations and initial conditions; you will solve the recurrence relations next week) Graded problems (these problems should be turned in) Grimaldi, Section 9.5 (p. 442): 8 Grimaldi, Section 10.1 (p. 455): 6 Grimaldi, Section 10.2 (p. 468–470): 6 (you only need to find the recurrence relations and initial conditions; you will solve the recurrence relations next week) |
| Oct. 14–15 | Fall Break (no class) | |
| HW 7 | Friday, Oct. 18 |
Self-checked problems (these problems need not be turned in)
Grimaldi, Section 10.2 (p. 468–470): 1, 3, 5, 11, 13, 25 Graded problems (these problems should be turned in) Grimaldi, Section 10.2 (p. 468–470): 6 (AB 7a) Solve the recurrence relation \(49a_{n+1}=70a_n-25a_{n-1}\), \(a_2=4\), \(a_3=5\). (AB 7b) Solve the recurrence relation \(a_n+10a_{n-1}+100a_{n-2}=0\), \(a_4=50\), \(a_5=200\). |
| Friday, Oct. 25 | Second midterm exam–good luck! This exam will cover the material on HW 4–6. You will be allowed a non-graphing calculator and a double-sided 3 inch by 5 inch card of notes. | |
| HW 8 | Friday, Nov. 1 |
Self-checked problems (these problems need not be turned in)
Grimaldi, Section 10.3 (p. 481–482): 1, 3, 9 Graded problems (these problems should be turned in) Grimaldi, Section 10.3 (p. 481–482): 4, 8 (AB 8) Solve the recurrence relation \(a_{n+1}+3a_n=2^{n+3}\), \(a_2=7\). |
| HW 9 | Friday, Nov. 8 |
Self-checked problems (these problems need not be turned in)
Grimaldi, Section 10.3 (p. 481–482): 5 Grimaldi, Section 10.4 (p. 487): 1, 3 Grimaldi, Section 14.3 (p. 696–697): 1, 2, 3 Graded problems (these problems should be turned in) Grimaldi, Section 10.3 (p. 481–482): 6 (AB 9a) Let \(\{a_n\}_{n=0}^\infty\) be the solution to the recurrence relation \(a_{n+2}-5a_{n+1}+4a_n=4^n\), \(a_0=3\), \(a_1=7\). Let \(f\) be the generating function for the sequence \(\{a_n\}_{n=0}^\infty\), that is, \(f(x)=\sum_{n=0}^\infty a_n x^n\). Find a simple closed form expression (with no infinite sums) for \(f(x)\). (AB 9b) Suppose that \(\{b_n\}_{n=0}^\infty\) and \(\{c_n\}_{n=0}^\infty\) satisfy the recurrence relations and initial conditions \[\begin{aligned} b_{n+1}&=3b_n+2c_n+1, & b_0&=4, \\ c_{n+1}&=5b_n-7c_n+n, & c_0&=-3. \end{aligned}\] Let \(B(x)\) be the generating function for the sequence \(\{b_n\}_{n=0}^\infty\), that is, \(B(x)=\sum_{n=0}^\infty b_n x^n\). Find a simple closed form expression (with no infinite sums) for \(B(x)\). |
| Friday, Nov. 15 | Third midterm exam–good luck! This exam will cover the material on HW 7–9. You will be allowed a non-graphing calculator and a double-sided 3 inch by 5 inch card of notes. | |
| Friday, Nov. 15 | Last day to withdraw from a course. | |
| Friday, Nov. 15 | If you have three final exams scheduled on the same day, then under university policy you are entitled to an alternative exam date; however, you must inform me by email (aeb019@uark.edu) that you need a make-up exam on or before Nov. 15. | |
| HW 10 | Wednesday, Nov. 20 |
Self-checked problems (these problems need not be turned in)
Without a calculator, find the value of \([18]\times [-12]+[36]\times [773]\) in \(\mathbb{Z}_7\). Grimaldi, Section 14.1 (p. 678–678): 1, 7 Grimaldi, Section 14.2 (p. 684–686): 3, 4, 5 Grimaldi, Section 4.4 (p. 236–237): 1 Graded problems (these problems should be turned in) (AB 10a) Find the values of \(7^2\mod10\), \(7^3\mod10\), \(7^4\mod10\), \(7^5\mod10\), and \(7^6\mod10\). (AB 10b) We have seen that if \(a\equiv_c b\) and \(d\equiv_c e\), then \(a+d\equiv_c b+e\) and \(a\times d\equiv_c b\times e\). Show that this does not work with exponents; that is, find integers \(a,b,c,d,e\), with \(c\gt0\), such that \(a\equiv_c b\) and \(d\equiv_c e\) but such that \(a^d\not\equiv_c b^e\). Justify your answer by explicitly computing \(a^d\mod c\) and \(b^e\mod c\). (AB 10c) For each of the following properties, either (a) tell me that it is true for all rings \((R,+,\times)\), or (b) give an example of a ring \((R,+,\times)\) in which the given property is not true. (If the property is always true, you will receive full credit for stating that it is always true, but if it is sometimes false and you claim it is always true, you will receive more partial credit if you explain why you think it is always true.)
(AB 10d) Find \(\gcd(465, 1983)\) and then find integers \(m\) and \(n\) such that \(465m+1983n=\gcd(465, 1983).\) |
| HW 11 | Monday, Nov. 25 |
Self-checked problems (these problems need not be turned in)
Grimaldi, Section 14.3 (p. 696–697): 15, 23, 25 (AB 11ℵ) Encode the secret message SPHERE by adding the random ciphertext FDGHUZ modulo 26. [Solution: XSNLLD] (AB 11ℶ) You have intercepted the secret message LURJIZX. You are given that I encoded my original message by adding the random ciphertext XSYJCLK modulo 26. What was my original message? [Solution: OCTAGON] Graded problems (these problems should be turned in) Grimaldi, Section 14.3 (p. 696–697): 26 (AB 11a) You intercept the secret message VLHDEA that I have encrypted by adding a nonrandom ciphertext modulo 26. You are given that the original message was one of the five words CIRCLE, COSINE, FINITE, MATRIX, and ELEVEN. Which of these words was my original message, and what was my nonrandom ciphertext? (You are allowed to write a computer program that does addition modulo 26 for you and to use it to do this problem.) (AB 11b) You intercept two secret messages, first GBPCUA and then XPJIJH, that I have encrypted by adding the same completely random ciphertext modulo 26. You are given that the two original messages were among the five words SECANT, DIVIDE, EIGHTY, NUMBER, and VECTOR. Which of these words was my first message, which of these words was my second message, and what was my random ciphertext? (You are allowed to write a computer program that does addition and subtraction modulo 26 for you and to use it to do this problem.) |
| Nov. 27–29 | Thanksgiving (no class) | |
| Nov. 21–Dec. 6 | Complete the online course evaluation on or before the due date. Because at least 80% of the class completed the course evaluation before the deadline, I will drop your 2 lowest homework scores. | |
| Wednesday, Dec. 4 | Last day of class | |
| HW 12 | Wednesday, Dec. 4 |
Self-checked problems (these problems need not be turned in)
Grimaldi, Section 14.4 (p. 704): 13, 15 (AB 12ℵ) Find \(3^{319}\mod 319\) by repeated squaring. Show all your work. [Solution: \(3^{319}=3^{256}*3^{32}*3^{16}*3^8*3^4*3^2*3 \equiv_{319} 168*284*223*181*81*9*3\equiv_{319} 15\).] (AB 12β) Find \(2^{341}\mod 341\) by repeated squaring. Show all your work. [Solution: \(2^{341}=2^{256}*2^{64}*2^{16}*2^4*2 \equiv_{341} 64*16*64*16*2\equiv_{341} 2\).] (AB 12γ) Can you be sure whether \(319\) is prime? Can you be sure whether \(341\) is prime? [Solution: You can be certain that \(319\) is not prime; if \(319\) were prime then we would have that \(3^{319}\equiv_{319} 3\) and this is not true. Based on this test \(341\) is probably (but not certainly!) prime.] (AB 12δ) Determine definitively whether \(341\) is prime. [Solution: It is not, because it is a multiple of \(11\).] Grimaldi, Section 16.4 (p. 761): 3 Grimaldi, Section 16.5 (p. 765): 3ab (AB 12ε) I transmit the three-bit string (code word) 110 over a channel that has a 95% chance of transmitting each bit correctly. What is the probability that the code word arrives correctly? [Solution: 0.857375 ] (AB 12ζ) I transmit the three-bit string (code word) 110 over a channel that has a 95% chance of transmitting each bit correctly. I have agreed with my recipient that I will only send code words with an even number of 1s. What is the probability of making a detectable error? [Solution: The probability of making exactly one error is 0.135375. The probability of making exactly three errors (which is also detectable) is 0.000125. Thus the probability of making a detectable error is 0.1355.] (AB 12η) What is the probability of making an undetectable error? [Solution: 0.007125] (AB 12θ) I agree with my recipient that I will always send five copies of each bit. They will decode my message by taking a majority vote in each group of five bits. I send the message 1111100000. What is the probability that they receive a message that can be decoded as 10? [Solution: 0.99768509125] Graded problems (these problems should be turned in) Grimaldi, Section 14.4 (p. 704): 14 (AB 12a) Find \(11^{41} \mod 16\) by repeated squaring. Show all your work. (AB 12b) Find \(11^{1602} \mod 17\) by using Fermat's little theorem. Show all your work. (AB 12c) Choose two three-digit prime numbers \(p\) and \(q\) from the list on Wikipedia. Find two integers \(e\) and \(d\), each with at least two digits, such that \((m^e)^d\equiv_{pq} m\) for all integers \(m\). Check your answer by computing \(32^e\mod pq\) and \((32^e)^d\mod pq\). |
| Professor Barton graded your homework herself this semester. She is scheduled to teach combinatorics again next semester and would be delighted to have the math department pay someone (possibly you!) to grade homework next semester. If you are interested, please fill out the grader application form linked to from this web page or email the department's vice-chair Phil Harrington. | ||
| Wednesday, Dec. 11, 8:00–10:00 a.m. | Final exam—Good luck! You will be allowed a non-graphing calculator and two double-sided 3 inch by 5 inch cards of notes. | |
| Instructor | Ariel Barton (email aeb019@uark.edu, office SCEN 348) |
| Lecture | Monday, Wednesday, Friday, 8:35–9:25 a.m. Human Environmental Sciences Building (HOEC) Classroom 0005 |
| Office hours |
If the University is closed due to inclement weather, office hours will be held over Zoom unless the instructor is without electricity or internet access. Class will either be also held over Zoom or cancelled; you will be notified of which by email as soon as possible. |
Course Description: Basic combinatorial techniques including the study of the principle of inclusion and exclusion and generating functions. Additional topics may include modular arithmetic, algebraic coding theory, Polya’s method of enumeration, and an introduction to abstract algebraic structures.
Prerequisites: MATH 26103 (Discrete Mathematics) or MATH 28003 (Transition to Advanced Mathematics); pre- or corequisite MATH 30803 or MATH 30903 (Linear Algebra). Students should be familiar with the standard notation and properties of sets, functions, and relations.
Text: Discrete and Combinatorial Mathematics by Ralph P. Grimaldi, 5th edition, ISBN 9780321385024.
Notetaking: To benefit the most from in-class attendance, careful note-taking is essential. You may not understand the material that you see in class the first time that you see it, but research shows that the act of physically writing down notes on what you see helps your brain to retain and process the new information that you are seeing. This also gives you a resource to review after class and when you are doing homework and preparing for exams. If you find yourself falling behind, feel free to ask me to pause.
Classroom etiquette: Students and instructors each have an important role in maintaining a classroom environment optimal for learning, and are expected to treat each other with respect during class, using thoughtful dialogue, and keeping disruptive behaviors to a minimum. Both students and faculty perceive abusive language directed towards others as the most disruptive behavior. Other behaviors that can be disruptive are chatting and whispering during class, the use of smartphones or laptops for texting or in other ways unrelated to the course, preparing to leave before class is over, and consistently arriving late to class. Inappropriate behavior in the classroom (whether in a lecture or a drill session) may result in a request to immediately leave the classroom and/or a referral to the Office of Academic Integrity and Student Conduct.
Cell phones: Cell phones, tablets, laptops, and other electronic devices may be used in class. The expectation is that these devices will be used for taking notes, routine calculations (i.e., calculator apps), accessing course materials, and other course-related uses only. Please do not text or play games in class!
Course grade: Here is how I plan to weigh your grades:
| Homework | 30% |
| Midterm tests | 14% each |
| Final | 28% |
Homework: Assignments will be posted to this website or to Blackboard. The due date and time will be clearly indicated. Each week you will be assigned a number of self-checked problems and a smaller number of graded problems. You may ask anyone for help with your homework, but you must write up your solutions on your own.
Self-checked problems will not be graded and need not be turned in. You will be able to check your answers by looking at the answers given in the back of the book. It is important that you do these problems; you will learn the material much better if you practice it by doing all problems, and material covered only on self-checked problems and not on instructor-corrected problems will still appear on the midterm tests and final exam.
Graded problems should be turned in on paper during class on the due date. We expect you to turn in your homework in class.
If you cannot make it to class on the day homework is due, you may:
Late homework will not be accepted without prior permission, except in the case of a medical or other unforeseeable emergency, and documentation will be required.
I expect to have 12 assignments over the course of the semester; your lowest score (or two scores) will be dropped.
Tests: There will be three midterms tests and a final exam. I plan to hold midterm exams during class time on the dates indicated in the calendar above. The final exam will occur at the time and place indicated on UAConnect; this should be our regular classroom and should coincide with the time indicated on the registrar's website.
Students may use non-graphing calculators, one index card of notes (two on the final), and portable timepieces on exams. All other electronic devices, including watches that do anything other than tell the time and date, are prohibited.
Accommodations: If you have a documented disability and require accommodations, please contact me privately at the beginning of the semester to make arrangements for necessary classroom adjustments. If you require accommodations on an exam, you must contact me at least one week before the exam is to be held.
Please note, for significant accommodations (such as extra time on exams) you must first verify your eligibility through the Center for Educational Access (contact 479–575-3104 or visit http://cea.uark.edu for more information on registration procedures). Some accommodations must be fulfilled using the CEA's resources. Minor accommodations (such as large print exams) are available to any student who requests them in a timely fashion.
Make-up exams: Make-up exam requests also require written documentation as to your conflict. Except in the case of medical or other unforeseen emergencies, make-up exam requests must be made at least one week before the exam is to be held. Make-up exams are at the instructor's discretion; if you do not provide a documented reason why you cannot take the exam at the usual time, if your reason is considered inadequate, or if your request for a make-up exam is not made in a timely fashion, I reserve the right to refuse a make-up exam or to assess a late penalty (deduction from your score).
As per the university policy, examples of absences that should be considered excusable include those resulting from the following: 1) disabilities documented by the CEA (see above under “Accommodations”); 2) illness of the student, 3) serious illness or death of a member of the student’s immediate family or other family crisis, 4) University-sponsored activities for which the student’s attendance is required by virtue of scholarship or leadership/participation responsibilities, 5) religious observances, 6) jury duty or subpoena for court appearance, and 7) military duty.
If you have three or more final exams scheduled for the same date, then under University policy you are entitled to reschedule one of your finals. If you wish to reschedule the final for our class, please notify me by email before the registrar's withdrawal deadline, and I will arrange for you to take a make-up final later in the week.
Make-up exams will be taken in the Mathematics Testing Center maintained by the MRTC. You will be allowed to take your exam on the scheduled exam date at any time when the Testing Center is open. You must finish your exam before the Testing Center closes; it is your responsibility to arrive early enough to allow this to happen.
Inclement weather policy: Class will meet unless the University is closed. On-campus students are expected to be present. Off-campus students should make their own decisions in the best interest of personal safety. Off-campus students will not be penalized for being absent on those days the Fayetteville Public Schools are closed due to weather.
If the University is closed due to inclement weather, our class will default to synchronous distance instruction; that is, I will deliver a lecture over Zoom. Students are encouraged to log in to Zoom and participate in lecture in real time (so that they may ask clarifying questions as necessary); however, a recording of the Zoom lecture will also be made available through Blackboard for any student unable to participate over Zoom.
If the University is closed due to inclement weather, office hours will be held over Zoom unless the instructor is without electricity or internet access.
If the University is closed on a day an exam is scheduled, the exam will be rescheduled to the first succeeding class period during which the University is open. A standard lecture covering new material will be held over Zoom, as described above, to make up the material that would have been covered on the new exam date.
If attendance is severely affected by weather, deadlines and exam dates may be adjusted. Please do not call the Department of Mathematical Sciences with weather-related inquiries. You may contact me for information.
Video recordings: The lecture will be recorded on the room’s camera and recordings will be posted to Blackboard for student reference. These recordings are provided “as is” as a hopefully-useful supplement, but their availability and quality is not guaranteed and no make-up recordings or materials will be posted in the event of technical issues. Students should not view class recordings as a substitute for class attendance.
Students who need or particularly desire high-quality reliable recordings are allowed to record lectures with their own devices for their own use.
In addition, if the University is open but the weather is severe, a Zoom meeting will be opened during class so that students may participate remotely in real time.
By attending this class, the student understands the course may be recorded and consents to being recorded for official university educational purposes. Be aware that incidental recording may also occur before and after official class times. Recordings may include personally-identifiable comments submitted to the chat stream during class.
Unauthorized Use of Class Recordings: These recordings may be used by students only for the purposes of the class. Students may not download, store, copy, alter, post, share, or distribute in any manner all or any portion of the class recording, (e.g. a 5-second clip of a class recording sent as a private message to one person is a violation of this provision). This provision may protect the following interests (as well as other interests not listed): faculty and university copyright; FERPA rights; and other privacy interests protected under state and/or federal law. Unauthorized recording, or transmission of a recording, of all or any portion of a class is prohibited unless the recording is necessary for educational accommodation as expressly authorized and documented through the Center for Educational Access with proper advance notice to the instructor. Unauthorized recordings may violate federal law, state law, and university policies. Student-made recordings are subject to the same restrictions as instructor-made recordings. Failure to comply with this provision will result in a referral to the Office of Student Standards and Conduct for potential charges under the Code of Student Life. In situations where the recordings are used to gain an academic advantage, it may also be considered a violation of the University of Arkansas’ academic integrity policy.
Grade Disputes: The instructor is committed to keeping students informed of their standing in the class. Scores on all graded items will be posted in a timely manner. Students are expected to bring any possible errors to the attention of the instructor within one week of posting. This maintains an accurate grade record throughout the semester. All scores posted before Reading Day will be deemed accurate unless a possible error is brought to the attention of the instructor before the scheduled final exam.
Incompletes: Only given in extreme circumstances, and only when the student has satisfactorily completed all but a small portion of the work in the course. Students must make prior arrangements with the professor well before the end of the semester.
Academic Integrity: As a core part of its mission, the University of Arkansas provides students with the opportunity to further their educational goals through programs of study and research in an environment that promotes freedom of inquiry and academic responsibility. Accomplishing this mission is only possible when intellectual honesty and individual integrity prevail. Each University of Arkansas student is required to be familiar with and abide by the university’s ‘Academic Integrity Policy’ at http://honesty.uark.edu/policy/index.php. Students with questions about how these policies apply to a particular course or assignment should immediately contact their instructor.
Unauthorized Websites or Internet Resources: There are many websites claiming to offer study aids to students, but in using such websites, students could find themselves in violation of our University’s Academic Integrity and Code of Student Life policies. These websites include (but are not limited to) Quizlet, Bartleby, Course Hero, Chegg, and Clutch Prep. The U of A does not endorse the use of these products in an unethical manner. These websites may encourage students to upload course materials, such as test questions, individual assignments, and examples of graded material. Such materials are the intellectual property of instructors, the university, or publishers and may not be distributed without prior authorization. Furthermore, paying for academic work to be completed on your behalf and submitting it for academic credit is considered ‘contract cheating’ per the Academic Integrity Policy. Students found responsible for this type of violation face a grading penalty of ‘XF’ and a minimum one-semester academic suspension per the University of Arkansas Sanction Rubric. Please let us know if you are uncertain about the use of a website.
Intellectual Property: Notes, review material, exams, quizzes, videos or other learning material used in this class are the intellectual property of the instructor. Selling or freely sharing this content in electronic or written form is a violation of intellectual property rights and also constitutes a violation of the University’s academic integrity policy. Your continued enrollment in this class signifies your understanding of and your intent to abide by this policy. There are severe consequences for sharing class content online.
Emergency Procedures: Many types of emergencies can occur on campus; instructions for specific emergencies such as severe weather, active shooter, or fire can be found at https://safety.uark.edu/emergency-preparedness/.
Health and wellness: https://catalog.uark.edu/generalinfo/studentaffairs/#healthcentertext