这是一份离散数学Discrete Mathematics的作业代写，离散数学代写，辅导请认准Uprivateta
Solve the recurrence $a_{n}=3 a_{n-1}+2$, with initial condition $a_{0}=0 .$
Consider the function $f(z)=\frac{1}{\sqrt{1-4 z}}$. Find a nice formula for the coefficient of $z^{n}$ when this is expanded as a power series about $0 .$ That is, when it is expanded as $f(z)=c_{0} z^{0}+c_{1} z^{1}+\cdots$, what is a general formula for $c_{n} ?$ You may express your answer in terms of (integer) factorials and binomial coefficients of the form $\left(\begin{array}{l}a \ b\end{array}\right)$, where $a$ and $b$ may depend on $n$, but are always non-negative integers (no matter what $n$ is).
We learned in class that the $n$ -th Catalan number $C_{n}$ was the number of strings of length $2 n$ consisting of the characters ‘(‘ and ‘)’, such that they were valid expressions. For example, $C_{3}=5$, as the five ways are ()()()$,()(()),(())(),(()())$, and $((()))$. Let $D_{n}$ be the number of strings of length $2 n$ consisting of the characters ‘ $(‘, \cdot)$ ‘, ‘[‘, and ‘ $]$ ‘, such that they are valid expressions. Now, (([]]) is not a valid expression, because the underlined'(‘ is closed by the underlined ‘]’, and of course, something like ()) $[$ [ is still not valid, because the underlined ‘)’ is closing nothing. On the other hand, ( $[())$ is a valid expression.
Find and prove a general formula for $D_{n}$.
After the end of a round-robin math tournament among $n$ students (in which every pair of students was matched head-to-head exactly once), it was observed that every student had won exactly the same number of games. Characterize all $n$ for which this could have happened.
This means that you should describe a set $S \subset \mathbb{Z}^{+}$, and then:
(a) for every $n \in S$, show that there is a way to choose the $\left(\begin{array}{l}n \ 2\end{array}\right)$ outcomes of the head-to-head matches such that every student wins the same number of times; and also
(b) for every $n \notin S$, prove that no matter how the $\left(\begin{array}{c}n \ 2\end{array}\right)$ matches played out, it is impossible for every student to have the same number of wins.
For example, it is relatively easy to see that $3 \in S$ because it’s possible for Alice to beat Bob, Bob to beat Charlie, and Charlie to beat Alice, resulting in 1 win for each student. Also, it is easy to see that $2 \notin S$ because if $n=2$, then there is only one game, and it can only give the win to one of the students.
Suppose that an arrow is drawn on each edge of a cube, giving each edge a direction, in such a way that every vertex of the cube has at least one arrow coming out of it and at least one arrow going into it. (A cube has 6 faces, 8 vertices, and 12 edges, so there will be 12 arrows.) Prove that under these conditions, it is always possible to find a face of the cube such that the directions of the four boundary edges of that face go in a cycle.
21-228: Discrete Mathematics (Spring 2021)
Po-Shen Loh
Last updated 30 Apr 2021.
Location
- Lecture meets Mon/Wed/Fri 2:10pm-3:00pm on Zoom (CMU only); also publicly live-streamed on YouTube
- Instructor office hours are Mon 11:00am-Noon and Tue 10:00pm-11:00pm, at the Zoom links corresponding to the times.
- Teaching assistants: Ariel Uy, Andrew Chen, and Daniel Hathcock.
- TA office hours: TBA.
Course Description
Combinatorics, which concerns the study of discrete structures such as sets and networks, is as ancient as humanity’s ability to count. Yet although in the beginning, combinatorial problems were solved by pure ingenuity, today that alone is not enough. A rich variety of powerful methods have been developed, often drawing inspiration from other fields such as probability, analysis, algorithms, and even algebra and topology.
This course provides a general introduction to this beautiful subject. Students will learn both classical methods for clever counting, as well as how to apply more modern methods to analyze recursions and sequences. Students will also learn fundamental techniques in graph theory. Throughout the course, students will encounter novel challenges that blur the lines between combinatorics and other subjects, such as number theory, probability, and geometry, so that they develop the skills to creatively combine seeming disparate areas of mathematics.
This course is structured around challenge. Lecture topics are hand-picked to reflect the rather advanced ability level of the general CMU student, and consequently, much of the curriculum sequence is original. Homework and exam problems are particularly difficult, and require creative problem-solving rather than application of learned techniques. To encourage students to truly develop these skills, collaboration is encouraged on homework, and exams (which are non-collaborative) will be open-notes.
The only pre-requisite for the course is one of 21-127 Concepts of Mathematics or 21-128 Mathematical Concepts and Proofs.
Learning Objectives
Students will learn how to:
- Use classical methods of combinatorial counting to determine exact and asymptotic values.
- Solve a variety of recurrence relations, using linear algebra and generating functions.
- Deduce, conjecture, and prove fundamental results in graph theory.
Learning Resources
The course roughly follows the order of topics in the well-written book Discrete Mathematics, by L. Lovász, J. Pelikán, and K. Vesztergombi. This book is not required for the class, because the level of CMU students is somewhat beyond. To adjust for the level of students at CMU, a substantial amount of extra material (not in the textbook) is covered in class. Students are encouraged to reference the book for further clarification, as it provides a clear presentation of an alternate perspective on the content discussed in class.
Grading
The course grade will be calculated by applying a curve to the following calculation, in which at least 25% of students will receive an A grade:
- Homework: 10%.
- Intermediate exams: 60%.
- Final exam: 30%.
Historically, the cutoff for an A grade has been around 66% of the weighted total points. All exams will be open notes / open book.
Homework
The only way to learn mathematics is to do mathematics. (Paul Halmos)
In order to encourage students to experiment with the concepts taught in class, homework assignments will be given on alternate weeks. They will be due in class on Fridays, at the beginning of lecture. Each assignment will consist of four to five challenging problems, for which the proof or justification of each answer is more important than actual numerical answer.
Since homework is a learning activity, students are welcome to discuss ideas with each other, although collaboration in the writing stage is not permitted. In other words, please do not look at the actual document that another student is handing in.
Exams
There will be 3 in-class exams, each with 5 problems, on Fri Feb 26, Fri Mar 26, and Fri Apr 30. There will also be a comprehensive final exam with 8 problems, at a date and time which will be determined by the registrar. No collaboration is permitted on exams, and students are required to have cameras on during the exam period. Due to time zone issues, people who cannot attend the USA Eastern Time exam will have the opportunity to take a make-up exam with entirely different problems between 9:00pm-9:50pm Eastern Time on that same day.
Other make-up exams will be given only in the case of a documented medical excuse, a university-sanctioned absence (e.g., participation in a varsity sporting event), or a family emergency. However, this must be requested before the official start time of each exam.
