\documentclass[10pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[small]{titlesec}
\usepackage{palatino, mathpazo}
\usepackage{inconsolata}
\usepackage{amsmath, amssymb}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage[normalem]{ulem}
\usepackage{setspace}
\usepackage{tikz}
\newcommand\mc[2]%
{\mathchoice{\left(\kern-0.5em{\binom{#1}{#2}}\kern-0.5em\right)}
{\bigl(\kern-0.3em{\binom{#1}{#2}}\kern-0.3em\bigr)}
{\bigl(\kern-0.3em{\binom{#1}{#2}}\kern-0.3em\bigr)}
{\bigl(\kern-0.3em{\binom{#1}{#2}}\kern-0.3em\bigr)}}
\newcommand{\ds}{\displaystyle}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.5ex}
\title{\sc Math 4670 / 5670 -- Combinatorics\\Homework 4}
\author{
Spring 2024\\[10pt]
assigned Wednesday, March 6\\
due Wednesday, March 27, \underline{by the beginning of class}\\[5pt]
}
\date{This homework covers the material from Sections 2.2 and 2.3.}
\begin{document}
\maketitle
\begin{center}
\emph{This homework assignment was written in \LaTeX{}. You can find the source code on the course website.}
\end{center}
\textbf{\underline{All answers must be fully justified to receive credit.} Answers without justification will not be considered correct.}
{\Huge $\star$} Questions that ask you to ``prove'' something or ask you to ``give a proof'' should be answered with formal mathematical proofs.
\begin{enumerate}
\item The table on page 50 of our textbook has sixteen cells for the number of distributions of balls into buckets depending on whether the buckets are identical or distinct, whether the balls are identical or distinct, and whether there are any particular restrictions.
Draw \emph{two copies} of the table.
For the first one, fill in the first three rows (what we've covered in 2.1, 2.2, and 2.3) for the \emph{specific case} of $n = 7$ and $k=4$.
Repeat for the second table, filling in the first three rows for the specific case where $n=7$ and $k=7$.
Each value in the table should just be a \underline{number}. Do not use formulas like $4^7$ for this question. You may use a calculator or computer to help with the calculations.
% ================================================
\item Give a combinatorial proof of the Pascal's Triangle identity
\[
{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}.
\]
(In class we only gave a proof for the case where $n=5$ and $k=3$.)
% ================================================
\item The identity
\[
\mc{n}{k} = \mc{n-1}{k} + \mc{n}{k-1}
\]
is kind of like the Pascal's Triangle identity, but for multisets.
\begin{enumerate}
\item Write a version of Pascal's Triangle, but for the numbers $\mc{n}{k}$, using this identity. How do you compute each term? Note that it won't be a triangle anymore. Your table should include all of the terms where $n \leq 7$ and $k \leq 7$.
\item Give an arithmetic proof of the identity.
\item Give a combinatorial proof of the identity.
\end{enumerate}
% ================================================
\item Give a combinatorial proof of the identity
\[
\mc{n}{k} = \mc{n-1}{k} + \mc{n-1}{k-1} + \mc{n-1}{k-2} + \cdots + \mc{n-1}{0}.
\]
Note that this can be written with summation notation as
\[
\mc{n}{k} = \sum_{i=0}^k \mc{n-1}{i}.
\]
% ================================================
\item How many solutions does the equation
\[
z_1 + z_2 + \cdots + z_n = k
\]
have, where each $z_i$ is either $0$ or $1$?
% ================================================
\item What is the coefficient of $x^3y^{12}$ in
\[
\left(\frac{2x^2}{y} + \frac{y^2}{5x}\right)^{15}?
\]
% ================================================
\item What is the coefficient of $a^5b^7c^8$ in $(a+b+c)^{20}$?
\emph{Hint:} First apply the binomial theorem with $x = a+b$ and $y = c$, pull out the correct coefficient of $c$, then apply the binomial theorem again.
% ================================================
\item What does the Binomial Theorem tell you when you substitute $x = -1$ and $y = 1$? What fact does this prove about the entries in each row of Pascal's Triangle? If you're stuck, try writing out the equation it tells you for some values of $n$.
% ================================================
\item We define a function to be \emph{almost surjective} if it ``misses'' exactly one element of its codomain. (That is, $f : A \to B$ is almost surjective if there exists exactly one $b \in B$ for which there is no $a \in A$ such that $f(a) = b$.) How many almost surjective functions $[k] \to [n]$ are there?
% ================================================
\end{enumerate}
\end{document}