Lesson 2

Advanced Problems.

1. (20 points) Let \(r, s, n\) be nonnegative integers. Show that \[\sum_{k=0}^{n}\binom{r+k}{k}\binom{s+n-k}{n-k}= \binom{r+s+n+1}{n}.\] Extend to a trivariate version with three parameters on top.
   Hint:

   Consider all lattice paths from \((0,0)\) to \((n, r+s+1)\). Can you establish a connection between these paths and the numbers appearing in the statement?

   A trivariate version with parameters \(r_{1}, r_{2}, r_{3}\) is given by: \[\sum_{\substack{k_1+k_2+k_3=n \\ k_1,k_2,k_3 \ge 0}}\binom{r_1+k_1}{k_1}\binom{r_2+k_2}{k_2}\binom{r_3+k_3}{k_3}= \binom{r_1+r_2+r_3+n+2}{n}.\]

2. (20 points) A partition of an integer \(n\) into \(k\) parts is defined as a non-increasing sequence of positive integers \(a_{1} \ge a_{2} \ge \dotsb \ge a_{k}\) such that \(a_{1} + a_{2} + \dotsc + a_{k} = n\). Which quantity is greater: the number of partitions of \(n\) into at most \(k\) parts, or the number of partitions of \(n + k\) into exactly \(k\) parts?
   Hint:

   To compare the sizes of these two sets of partitions, try to construct a bijection between them.
3. (20 points) What is the number of (unordered) pairs of lattice paths with \(n + 1\) steps each, starting at \((0, 0)\), using steps \((1, 0)\) or \((0, 1)\), ending at the same point, and only intersecting at the beginning and end?

   

   Hint:

   Indeed, it is equal to a Catalan number.
4. (20 points) In the game of backgammon, \(15\) white and \(15\) black checkers are placed on \(24\) positions such that each position is either empty, occupied by several white checkers, or occupied by several black checkers. In how many ways can the checkers be arranged on the board under these conditions? (The answer may involve summation notation.)
5. (20 points) For non-negative integers \(a\), \(b\), \(n\) with \(0 \le n \le b\), prove the identity \[\sum_{k=0}^{a}(-1)^{k} \binom{a}{k}\binom{b+k}{n}= (-1)^{a} \binom{b}{n-a}.\] Here, \(\binom{b}{r}=0\) when \(r<0\) or \(r>b\).
   Hint:

   Try to express the binomial \(\binom{b+k}{n}\) as the coefficient of \(x^{n}\) in the expansion of the polynomial \((1+x)^{(b+k)}\).
6. (20 points) Which is greater: the number of partitions of an integer \(n\) into distinct parts, or the number of partitions of \(n\) into odd parts?
   Hint:

   This is a classic theorem in partition theory, which states that the two quantities are, in fact, equal. A direct combinatorial proof can be constructed by finding a bijection between the two sets of partitions.
7. (20 points) For non-negative integers \(m\) and \(n\) and a prime \(p\), show that the following congruence relation holds: \[\binom{m}{n}\equiv \prod_{i=0}^{k}\binom{m_i}{n_i}\pmod{p},\] where \[m = m_{k} p^{k} + m_{k-1}p^{k-1}+ … + m_{1} p + m_{0},\] and \[n = n_{k} p^{k} + n_{k-1}p^{k-1}+ … + n_{1} p + n_{0}\] are the base \(p\) expansions of \(m\) and \(n\) respectively. Here, \(\binom{m}{n}= 0\) if \(m < n\).
   Hint:

   Consider the expansion of the polynomial \((1+x)^{m}\) in the ring of polynomials over \(\mathbb{Z}_{p}\). What can we say about its coefficient of \(x^{n}\)?
8. (20 points) Provide a combinatorial proof of the identity: \[\binom{n}{0}+ \binom{n-1}{1}+ \binom{n-2}{2}+ \dotsb = F_{n+1}\ ,\] where \(n > 0\), and \(F_{k}\) is the \(k\)-th Fibonacci number, with the sequence defined by \(F_{1}=1, F_{2}=1, F_{3}=2, \dotsb\).
9. (20 points) Which rows in Pascal’s triangle consist solely of odd numbers?
   Hint:

   Begin by formulating a conjecture.
10. (25 points) A permutation \(\sigma = a_{1}, …, a_{n}\) is called 321-avoiding if the length of the longest decreasing subsequence is at most two (i.e., there is no \(i < j < k\) such that \(a_{i} > a_{j} > a_{k}\)). Determine the number of 321-avoiding permutations of length \(n\).
    Hint:

    Perhaps surprisingly, this number is equal to the \(n\)-th Catalan number.