\documentclass[12pt]{amsart}

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

\begin{document}

Math 188, Spring 2021

Homework 4

Due: April 30, 2021 11:59PM via Gradescope

~

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

\begin{enumerate} 
\item Let $n$ be a positive integer. Consider the equation
  \[
    x_1 + x_2 + \cdots + x_8 = 2n.
  \]
  For each of the following conditions, how many solutions are there? Give as simple of a formula as possible. (Each part is an independent problem, don't combine the conditions.)
  \begin{enumerate}
  \item The $x_i$ are non-negative even integers.
  \item The $x_i$ are positive odd integers.
  \item The $x_i$ are non-negative integers and $x_8 \le 10$.
  \end{enumerate}
  

\item Let $k,n$ be positive integers.
  \begin{enumerate}
  \item Show that
    \[
      \sum_{(a_1,\dots,a_n)} a_1a_2\cdots a_n = \binom{n+k-1}{k-n}
    \]
    where the sum is over all compositions of $k$ into $n$ parts. (Hint at end.)
    
  \item Show that
    \[
      \sum_{(a_1,\dots,a_n)} 2^{a_2-1} 3^{a_3-1} \cdots n^{a_n-1} = S(k,n)
    \]
    where the sum is over all compositions of $k$ into $n$ parts.    
\end{enumerate}

\item 
  \begin{enumerate}
  \item Give a closed formula for the number of pairs of subsets $S,T$ of $[n]$ such that $S \subsetneqq T$ (i.e., $S \subset T$ and $S \ne T$).
  \item Give a closed formula for the number of $k$-tuples of subsets $(S_1,\dots,S_k)$ of $[n]$ such that $\bigcap_{i=1}^k S_i = \emptyset$.
  \end{enumerate}
\item
  \begin{enumerate}
  \item Let $r$ be a fixed positive integer. Show that $S(n+r,n)$ is a polynomial function of $n$ of degree $2r$ for $n \ge 0$.
  \item Compute this polynomial for $r=2,3,4$.
  \end{enumerate}

\item Let $F(n)$ be the number of set partitions of $[n]$ such that every block has size $\ge 2$. Prove that
  \[
    B(n) = F(n) + F(n+1),
  \]
  where  $B(n)$ is the $n$th Bell number.


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

\item What is the total number of parts of all compositions of $k$?

  [For example, when $k=2$, the only compositions are $(2)$ and $(1,1)$ so there are a total of 3 parts.]

\item Fix an integer $k \ge 2$. Call a composition $(a_1, \dots, a_n)$ of $k$ {\bf doubly even} if the number of $a_i$ which are even is also even (i.e., there could be no even $a_i$, or 2 of them, or 4, etc.). Show that the number of doubly even compositions of $k$ is $2^{k-2}$.

For example, if $k=4$, then here are the $4$ doubly even compositions of $4$:
\[
(2,2), \qquad (3,1), \qquad (1,3), \qquad (1,1,1,1).
\]

\item Give a closed formula for the number of $k$-tuples of subsets $(S_1,\dots,S_k)$ of $[n]$ such that $S_i \subseteq S_{i+1}$ for $i=1,\dots,k-1$.
\end{enumerate}

\section{Hints}

(2)a: Consider the product
\[
  \left( \sum_{a_1 \ge 1} a_1 x^{a_1} \right) \cdots  \left( \sum_{a_n \ge 1} a_n x^{a_n} \right).
\]

(7): Given a composition $\alpha = (a_1, \dots, a_n)$, define another composition $\Phi(\alpha)$ by
\[
\Phi(\alpha) = \begin{cases} (1, a_1  - 1, a_2, a_3, \dots, a_n) & \text{if $a_1>1$}\\
(a_2+1, a_3, \dots, a_n) & \text{if $a_1=1$} \end{cases}.
\]
(in both cases, we didn't do anything to $a_3, \dots, a_n$). Show that $\Phi$ defines a bijection between the set of doubly even compositions of $k$ and the set of compositions of $k$ which are not doubly even.
\end{document}
