\documentclass[12pt]{amsart}

\usepackage[margin=1in]{geometry}
\usepackage{xypic}

\begin{document}

Math 188, Spring 2021

Homework 6

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

~

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

\begin{enumerate}
    
\item Let $B_n$ be the set of binary strings of length $n$, i.e., of words of length $n$ in the alphabet $\{0,1\}$. We define a simple graph $G_n$ whose vertex set is $B_n$ where two binary strings are connected by an edge if and only if they differ in exactly one position. Let $V$ be the real vector space with basis $\{v_x \mid x \in B_n\}$. We can think of the adjacency matrix $A$ of $G_n$ as a linear operator on $V$:
    \[
      A \sum_{x \in B_n} c_x v_x = \sum_{x \in B_n} c_x \sum_{\substack{y \text{ such that}\\ \{y,x\} \text{ is an edge}}} v_y.
    \]
    \begin{enumerate}
    \item For each $x \in B_n$, define $E_x \in V$ by
      \[
        E_x = \sum_{y \in B_n} (-1)^{x \cdot y} v_y
      \]
      where $x \cdot y = x_1y_1 + \cdots + x_ny_n$. Show that this is an eigenvector for $A$ with eigenvalue $n - 2|x|$ where $|x|$ is the number of $x_i$ equal to 1.

    \item For $x \in B_n$ and a non-negative integer $d$, give a formula for the number of closed walks of length $d$ in $G_n$ beginning at $x$.

      [You may assume without proof that $\{E_x \mid x \in B_n\}$ is linearly independent.]
    \end{enumerate}
    
  \item Let $A$ be the adjacency matrix of the following directed graph:
    \[
      \xymatrix{ 1 \ar[d]<2pt> \ar[dr]<2pt> \ar[dr]<-2pt> & & 2 \ar[dr] \ar[ll] \ar[dl] \\ 3 \ar[u]<2pt> \ar[r]<2pt> \ar@(dl,dr)& 4 \ar[l]<2pt> & \ar[l] \ar[r]<2pt> 5 \ar[u]<2pt> \ar[u]<-2pt> & \ar[l]<2pt> 6 \ar@(dl,dr)}
    \]
    ~
  
    Express $F_{A;1,4}(x)$ as a rational function.
  
  \item \begin{enumerate}
    \item Fix a positive integer $k$. Construct a directed graph for which walks (between certain vertices) can be interpreted as binary strings with exactly $k$ zeroes. Explain clearly how this interpretation works, including how the length of the walk relates to the length of the binary string.

    \item Construct a directed graph for which walks (between certain vertices) can be interpreted as binary strings in which no symbol ever appears 3 times in a row. Explain clearly how this interpretation works, including how the length of the walk relates to the length of the binary string.

    \item Explain why it is impossible to have a directed graph for which walks of length $2n$ can be interpreted as balanced sets of $n$ pairs of parentheses.
    \end{enumerate}

  \item \begin{enumerate}
    \item We have $n$ distinguishable tables. We want to paint each one either red, blue, green, or black such that an odd number of them are red and an odd number of them are blue. How many ways can this be done?
    \item Continuing with that situation, we add the colors white and yellow, but the total number of tables which are white or yellow must be even. How many ways are there to choose colors?
    \end{enumerate}

  \item Let $a(n,k)$ be the number of set partitions of $[n]$ with $k$ blocks such that no block has size 1. Find a formula for the EGF $A_k(x) = \sum_{n \ge 0} a(n,k) \frac{x^n}{n!}$.
  
    \section{Optional problems (don't turn in)}
  
  \item Compute $G_3$ in Example 4.11.
  \item Given a sequence $(a_n)_{n \ge 0}$ we can define its $q$-EGF to be
    \[
      A(x) = \sum_{n \ge 0} a_n \frac{x^n}{[n]_q!}.
    \]
    What is the $q$-analogue of Proposition 5.2?
  \end{enumerate}

\end{document}
