2. Teaching
3. MAT526
4. Homework

Guidelines

On each homework assignment, please write (i) your name, (ii) name of course, and (iii) homework number. You are allowed and encouraged to work together on homework. Yet, each student is expected to turn in their own work. In general, late homework will not be accepted. However, you are allowed to turn in up to three late homework assignments with no questions asked. Unless you have made arrangements in advance with me, homework turned in after class will be considered late. When doing your homework, I encourage you to consult the Elements of Style for Proofs.

Daily Homework

The following assignments are due at the beginning of the indicated class meeting. However, most assignments will be collected at the end of the class meeting. I reserve the right to modify the assignment if the need arises. These exercises will form the basis of the student-led presentations. Daily assignments will be graded on a $\checkmark$-system. During class, you are only allowed and encouraged to annotate your homework using the colored marker pens that I provide.

• Daily Homework 1: Read the syllabus and write down 5 important items. Note: All of the exam dates only count as a single item. Turn in on your own paper at the beginning of class. (Due Wednesday, January 16)
• Daily Homework 2: If you haven’t already, read the Preface (3 pages) and Chapter 0: Introduction to this book (14 pages) in Inquiry Based Enumerative Combinatorics. Jot down some notes and be prepared to explain/justify (1) the recurrence relation, (2) the closed form, and (3) the structural recurrence diagram for the $n$-disk version of the Towers of Hanoi. (Due Wednesday, January 16)
• Daily Homework 3: Complete Problems 1-7 and digest the surrounding text along the way. (Due Friday, January 18)
• Daily Homework 4: Complete Problems 8-13 and digest the surrounding text along the way. (Due Wednesday, January 23)
• Daily Homework 5: Complete Problems 14-18 and digest the surrounding text along the way. (Due Friday, January 25)
• Daily Homework 6: Complete Problems 19-25. In addition, read “Organizing data” (pages 26-31). (Due Monday, January 28)
• Daily Homework 7: Complete Problems 26-37. In addition, carefully read and digest “The symmetric group” (pages 38-41). (Due Wednesday, January 30)
• Daily Homework 8: Complete Problems 38-40. (Due Friday, February 1)
• Daily Homework 9: Complete Problems 41-46. In addition, read “Anagrams, or multiset permutations” (pages 49-53). (Due Monday, February 4)
• Daily Homework 10: Complete Problems 47-53. (Due Wednesday, February 6)
• Daily Homework 11: Complete Problems 54-56. (Due Friday, February 8)
• Daily Homework 12: Complete Problems 57-60. (Due Monday, February 11)
• Daily Homework 13: Read and take notes (to turn in) on “Counting permutations according to cycles” (pages 59-64) and “Lucas numbers and polynomials” (pages 70-75). (Due Wednesday, February 20)
• Daily Homework 14: Complete Problem 67. (Due Monday, February 25)
• Daily Homework 15: Complete Problems 69-71. (Due Wednesday, February 27)
• Daily Homework 16: Complete Problems 72-74. (Due Friday, March 1)
• Daily Homework 17: Complete Problems 75 and 76. (Due Monday, March 4)
• Daily Homework 18: Complete Problems 77-81. (Due Wednesday, March 6)
• Daily Homework 19: Complete Problems 82-84. (Due Friday, March 8)
• Daily Homework 20: Complete Problems 85 and 86. (Due Monday, March 11)
• Daily Homework 21: Complete Problems 87, 93, 94. (Due Wednesday, March 13)
• Daily Homework 22: Complete Problems 95, 97, 98. (Due Friday, March 15)
• Daily Homework 23: Complete Problems 101-103. (Due Wednesday, March 27)
• Daily Homework 24: Complete Problems 107 and 108. (Due Friday, March 29)
• Daily Homework 25: Complete Problems 109 and 110. (Due Monday, April 1)
• Daily Homework 26: Complete Problems 115 and 117. (Due Monday, April 15)
• Daily Homework 27: Complete Problems 120-122. (Due Wednesday, April 17)
• Daily Homework 28: Complete Problem 124. (Due Friday, April 19)
• Daily Homework 29: Complete Problems 125 and 126. (Due Monday, April 22)
• Daily Homework 30: Prove that $L_{n,k}(q)=\sum_{w\in S_n, \text{Des}(w)\subseteq \{k\}}q^{\text{inv}(w)}$ using a bijection between $L(k,n-k)$ and $\{w\in S_n\mid \text{Des}(w)\subseteq \{k\}\}$. (Due Wednesday, April 24)
• Daily Homework 31: Define the $q$-multinomial via \[\begin{bmatrix}n\\ a_1,\ldots, a_k\end{bmatrix}=\frac{[n]!}{[a_1]!\cdots [a_k]!}.\] Prove that for any $J=\{j_1,\ldots,j_{k-1}\}\subseteq \{1,\ldots,n-1\}$, the distribution of inversions for all $w\in S_n$ with descent set contained in $J$ is given by the $q$-multinomial coefficient. That is, \[\sum_{w\in S_n, \text{Des}(w)\subseteq J}q^{\text{inv}(w)}=\begin{bmatrix}n\\ a_1,\ldots, a_k\end{bmatrix},\] where $a_1=j_1, a_k=n-j_{k-1}$, and $a_i=j_i-j_{i-1}$ for all $1<i<k$. (Due Friday, April 26)
• Daily Homework 32: Complete the following problems. (Due Monday, April 29)
  1. Prove that for any $n\geq k\geq 0$, we have \[\sum_{p\in L(k,n-k)}q^{\text{maj}(p)}=\begin{bmatrix}n\\ k\end{bmatrix}.\]
  2. Let $P$ be the labeled poset consisting of the disjoint union of the chains $1<_P 2 <_P \cdots <_P k$ and $k+1 <_P k+2 <_P \ldots <_P n$ for some $k$. A linear extension of $P$ is a permutation in $S_n$ whose ordering respects the ordering of $P$. Characterize the set of linear extensions of $P$. Hint: For a linear extension $w$, consider $\text{Des}(w^{-1})$.
• Daily Homework 33: Define a shuffle of two words $u=u(1)u(2)\cdots u(k)$ and $v=v(1)v(2)\cdots v(l)$ to be the word containing the letters of $u$ and $v$ such that $u$ and $v$ appear as subwords in the proper order, and denote the set of shuffles of $u$ and $v$ by $\text{Shuff}(u,v)$. In the language of posets, the shuffles of $u$ and $v$ are the linear extensions of the disjoint union of $u$ and $v$. Prove that the $q$-binomial coefficient counts shuffles according to major index. That is, we have \[\sum_{w\in \text{Shuff}(u,v)}q^{\text{maj}(w)}=\begin{bmatrix}n\\ k\end{bmatrix}\] where $u=12\cdots k$ and $v=(k+1)\cdots n$. (Due Wednesday, May 1)

Weekly Homework

For most of the assignments below, you will be required to submit 2-3 formally written proofs. You are required to type your submission using LaTeX (see below). You can either submit a hardcopy of your assignment or email me the PDF of your completed work. If you email me the PDF, please name your file as WeeklyX-LastName.pdf, where X is the number of the assignment and Lastname is your last name. Notice there are no spaces in the filename.

• Weekly Homework 1: Read The Secret to Raising Smart Kids by Carol Dweck and write a one-page summary/reflection about the article. For this assignment, I suggest you use the template on Overleaf found here instead of using the “Start your homework in Overleaf” link below. (Due Tuesday, January 22 by 8PM)
• Weekly Homework 2: Complete the following problems. You must type up your proofs using LaTeX. I suggest you use my Overleaf template, which you can access by clicking the “Start your homework in Overleaf” link below. (Due Tuesday, January 29 by 8PM)
  1. Either (a) establish a bijection between the set of dominoes consisting of double blank through double $n$ and the set of edges in the complete graph on $n+2$ vertices, or (b) complete Problem 10 (including a closed form).
  2. Complete Problem 6 in the Supplementary Exercises for Chapter 1 (page 197).
  3. Carefully prove Version 3 of Theorem 2.
• Weekly Homework 3: Complete the following problems. You must type up your proofs using LaTeX. (Due Tuesday, February 5 by 8PM)
  1. Prove one of the identities in either Problem 31 or Problem 32 by establishing a bijection between the appropriate sets.
  2. Complete one of Problem 37, Problem 38, or Problem 40.
  3. Complete either Problem 10 or Problem 11 in the Supplementary Exercises for Chapter 3 (pages 202-203).
• Weekly Homework 4: Complete the following problems. You must type up your proofs using LaTeX. (Due Tuesday, February 12 by 8PM)
  1. Complete one of Problem 41, Problem 53, or Problem 56.
  2. Complete either Problem 9 in the Supplementary Exercises for Chapter 4 (pages 205) or Problem 6 in the Supplementary Exercises for Chapter 5 (pages 206).
• Weekly Homework 5: Complete the following problems. You must type up your proofs using LaTeX. (Due Tuesday, March 5 by 8PM)
  1. Complete one of Problems 69-74.
  2. Complete one of Problems 3-8 in the Supplementary Exercises for Chapter 6 (pages 209).
• Weekly Homework 6: Complete the following problems. You must type up your proofs using LaTeX. (Due Thursday, March 14 by 8PM)
  1. Complete one of Problems 75, 76, 81.
  2. Complete one of Problems 2, 4 in the Supplementary Exercises for Chapter 7 (pages 211).
• Weekly Homework 7: Complete one of Problems 85, 87, 97, 98, 99, 103 (Due Tuesday, April 2 by 8PM)

Using LaTeX for Weekly Homework

You are required to use LaTeX to type up your Weekly Homework assignments. The easiest way to get started with LaTeX is to use an online editor. I recommend using Overleaf, but there are other options. The good folks over at Overleaf have preloaded my homework template, so to get started, all you need to do is click the link below and then click on “Open as Template”. Be sure to update your name and the course title.

Start your homework in Overleaf