\documentclass[10pt]{article}

\usepackage[margin=1in]{geometry}
\usepackage[small]{titlesec}
\usepackage{palatino, mathpazo}
\usepackage{inconsolata}
\usepackage{amsmath, amssymb}
\usepackage{enumitem}
\usepackage{graphicx}
\usepackage[normalem]{ulem}
\usepackage{tikz}
\usepackage{wasysym}


\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 2022\\[10pt]
	due Wednesday, April 6, \underline{by the beginning of class}\\[10pt]
}
\date{}
\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{Mathematical Writing:} An important component of this course is learning how to write mathematics correctly and concisely. Your goal should always be the convince the reader that you are correct! That means explaining your thinking and each step in your solution. I expect you to do the following: explain your reasoning, don't leave out steps, and use full sentences with correct spelling and grammar (including your use of math symbols).

\textbf{\underline{All answers must be fully justified to receive credit.} Answers without justification will not be considered correct.}

\begin{enumerate}

	\item How many solutions does the inequality $a + b + c + d + e + f \leq 517$ have in which $a, b, c, d, e, f$ are all non-negative integers, $b \geq 5$, and $e \geq 20$? (\emph{Hint:} Think about using stars-and-bars, or the robot method.)

%	\item Prove that for any fixed $n$, the sum of binomial coefficients $\ds{n \choose k}$ where $k$ is even is equal to the sum of the binomial coefficients $\ds{n \choose k}$ where $k$ is odd. In other words, prove that
%	\[
%		{n \choose 0} + {n \choose 2} + {n \choose 4} + \cdots = {n \choose 1} + {n \choose 3} + {n \choose 5} + \cdots
%	\]
%	(\emph{Hint:} Move all terms to one side, and use the Binomial Theorem in reverse to simplify.)

	\item Compute $\ds\sum_{k=0}^{100} 2^k(-3)^{100-k}\ds{100 \choose k}$.
	\item Prove the identity
	\[
		\sum_{k=0}^n {n \choose k} (n+k)(n+k-1) = n(9n-5)2^{n-2}
	\]
	by applying the Binomial Theorem to $(t+t^2)^n$ and taking the second derivative of both sides.
	\item Find the coefficient of $x^{12}y^{24}$ in $(x^3+2xy^2+y+3)^{18}$.
	\item Suppose $n$ lines are drawn so that no two lines are parallel and no three lines intersect at any one point. Let $a_n$ denote the number of regions the plane is divided into by $n$ such lines. See Figure 5.2 on page 68 of our textbook for example that shows $a_3 = 7$. Find a recurrence for $a_n$.
	\item Let $b_n$ be the number of ways you can write the number $n$ as an ordered sum of odd numbers (i.e., the number of compositions of $n$ in which all of the parts are odd numbers). For example $a_4 = 3$ because the valid compositions are $3+1$, $1+3$, and $1+1+1$. Find a recurrence for $b_n$.
	\item An \emph{L-tiling} of a $2 \times n$ rectangle is like a domino tiling except that it uses the pieces
	\begin{center}
		\begin{tikzpicture}[scale=0.4]
			\draw (0,0) rectangle (1,1);
		\end{tikzpicture}
		\qquad and \qquad
		\begin{tikzpicture}[scale=0.4]
			\draw (0,0) -- (2,0) -- (2,1) -- (1,1) -- (1,2) -- (0,2) -- cycle;
		\end{tikzpicture}
	\end{center}
	including any rotations of the second piece. See the top of Figure A.5 on page 209 of our textbook for an example of an $L$-tiling of a $2 \times 10$ rectangle. Let $L_n$ be the number of $L$-tilings of a $2 \times n$ rectangle. Find a recurrence for $L_n$.
\end{enumerate}
\end{document}


