\documentclass[12pt]{amsart}

\usepackage[margin=1in]{geometry}

\newcommand{\bF}{\mathbf{F}}
\newcommand{\bL}{\mathbf{L}}
\newcommand{\qbinom}[2]{\begin{bmatrix} #1 \\ #2 \end{bmatrix}_q}

\begin{document}

Math 188, Spring 2021

Homework 5

Due: May 7, 2021 11:59PM via Gradescope

~

Solutions must be {\bf clearly} presented. Incoherent or unclear solutions will lose points. 

\begin{enumerate}
  
\item Prove the following identities about the number of integer partitions:
  \begin{enumerate}
  \item For $n \ge k$, $p_k(n) = p_{\le k}(n-k)$.
  \item For $n>0$, the number of partitions of $n$ not using 1 as a part is $p(n) - p(n-1)$.
  \end{enumerate}

\item
  \begin{enumerate}
  \item Use the following $q$-analogue of Pascal's identity
        \begin{align*}
      \qbinom{n}{k} &= q^k \qbinom{n-1}{k} + \qbinom{n-1}{k-1} \qquad (\text{for } n \ge k > 0)
        \end{align*}
    to show that if $d$ is a non-negative integer, then
    \[
      \sum_{n \ge 0} \qbinom{n+d}{n} x^n = \prod_{i=0}^d (1-q^ix)^{-1} = \frac{1}{(1-x)(1-qx) \cdots (1-q^d x)}.
    \]
  \item Give a direct explanation for why the coefficient of $x^n$ of the right side is the sum $\sum_\lambda q^{|\lambda|}$ over all integer partitions $\lambda$ fitting in the $n \times d$ rectangle.
  \end{enumerate}
  
\item Let $T$ be a subset of the positive integers such that if $x \in T$, then $2x \in T$. Define $2T = \{2x \mid x \in T\}$ and let $S = T \setminus 2T$.

  Let $p_S(n)$ be the number of partitions of $n$ using only parts from $S$, and let $p_{T,{\rm dist}}(n)$ be the number of partitions of $n$ using only parts from $T$ and not repeating any parts. Prove that $p_S(n) = p_{T,{\rm dist}}(n)$ for all $n$.

\item Use the notation from HW2 \#3. Show that for $k \ge 0$, we have
  \[
    \sum_{n \ge 0} \frac{c(n,k)}{n!} x^n = \frac{(-\bL( 1-x ))^k}{k!}.
  \]
 
  \item Let $V,W$ be $\bF_q$-vector spaces with $\dim V = n$ and $\dim W = m$.
    \begin{enumerate}
    \item How many linear maps $V \to W$ are there?
    \item Suppose $n \ge m$. How many surjective linear maps $V \to W$ are there?
    \item Pick $k \le \min(m,n)$. How many rank $k$ linear maps $V \to W$ are there?
    \end{enumerate}


\section{Optional problems (don't turn in)}

\item Let $a_n$ be the number of ways to give $n$ dollars using bills of size $1,2,5,10,20,50$ such that at most three 20 dollar bills can be used. Give a simple formula for the generating function $A(x) = \sum_{n \ge 0} a_n x^n$.

\item This one is challenging (I can't see a solution that is simple, but it doesn't require anything outside of this class). Prove:
  \[
    \sum_{n \ge 1} x^{n(n-1)/2} = \prod_{n \ge 1} \frac{1-x^{2n}}{1-x^{2n-1}}.
  \]

\item Let $\lambda$ be an integer partition of $n$ whose Durfee square has size $r \times r$. Call $\lambda$ {\bf almost self-conjugate} if $\lambda_i = \lambda_i^T + 1$ for $i=1,\dots,r$. Let $q(n)$ be the number of almost self-conjugate partitions of $n$ ($q(0)=0$). Find a formula for
  \[
    \sum_{n \ge 0} q(n) x^n
  \]
  in the same spirit as Example 3.27.

\item Consider a group of $n+1$ people of different ages and consider the following scenario:
  \begin{itemize}
  \item The youngest person becomes a zombie, and all others start as non-zombies.
  \item Each zombie may turn any non-zombie older than them into a zombie.
  \item Once a zombie, a person stays a zombie.
  \item Everyone eventually becomes a zombie.
  \end{itemize}
  At the end, we get a set of pairs $\{(i,j) \mid i \text{ infected } j\}$. Call this a {\bf zombie set} of size $n+1$. For $n,k \ge 0$, show that $c(n,k)$ is the number of zombie sets of size $n+1$ such that the youngest person infects $k$ people.
    

\item Show that the number of complete flags in $\bF_q^n$ is $[n]_q!$.


\item
  \begin{enumerate}
  \item Let $r \ge 0$ be a non-negative integer. Show that $c(n+r,n)$ is a polynomial function of $n$ of degree $2r$.
  \item Compute this polynomial for $r=1,2,3,4$.
  \end{enumerate}
  
\end{enumerate}
    
\end{document}
