% This is a TeX file
% It is essentially a programming language for mathematics documents
% You can ignore this first portion of the file, as it is essentially a bunch of "include" statements.
\documentclass[10pt]{article}

\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{graphics}
\usepackage{fullpage}
\usepackage{fancyhdr}
\usepackage{hyperref}

\usepackage{algorithm,algorithmic}
\usepackage{multirow}

\setlength{\voffset}{-0.25in}
\setlength{\headsep}{0.25in}
\setlength{\parskip}{1em}
\setlength{\parindent}{0em}

% The following denotes a counter for the problems.
\newcounter{problem}
\newcommand{\problem}{\textbf{\refstepcounter{problem}Problem \theproblem.} }

% These are macro shortcuts! Helpful!
\def\vu{\mathbf{u}}
\def\vx{\mathbf{x}}
\def\vy{\mathbf{y}}
\def\vz{\mathbf{z}}
\def\vb{\mathbf{b}}
\def\vv{\mathbf{v}}
\def\vw{\mathbf{w}}

\renewcommand{\implies}{\rightarrow}
%\newcommand{\lnot}{\neg}
\renewcommand{\lor}{\vee}
\renewcommand{\land}{\wedge}
\newcommand{\xor}{\oplus}
\newcommand{\symmdiff}{\triangle}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\TRUE}{\mathbf{T}}
\newcommand{\FALSE}{\mathbf{F}}
\newcommand{\universe}{\mathcal{U}}


\def\N{\mathbb{N}}
\def\Q{\mathbb{Q}}
\def\C{\mathbb{C}}
\def\Z{\mathbb{Z}}
\def\R{\mathbb{R}}
\def\cP{\mathcal{P}}


\begin{document}
\pagestyle{fancyplain}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NOW you can start typing your text that will appear in the PDF!!!

% Note that anything after a '%' is a comment!

% Anything immediately after a '\' is a command. 
% Some denote formatting, some are for special characters.
% The '$' symbol starts and ends "math mode". Use this only for mathematical statements
% In math mode, any sequence of letters is meant to be a list of variables, so use "\sin x" for the sine of x, which will look much different from "sin x"
\chead{COM S 330 --- Homework 11 --- INSERT NAME HERE}

\textit{Type your answers to the following questions and submit a PDF file to Blackboard. 
One page per problem.}

\textit{A \textbf{*} means the problem is slightly harder than the others.}

% \clearpage
\problem\ [10pts] Let $n = 6$ and $r = 4$. Count the following things:

\textbf{a.} How many ways can we place $r$ distinguishable objects into $n$ distinguishable boxes?\\
\textbf{b.} How many ways can we place $r$ indistinguishable objects into $n$ distinguishable boxes?\\
\textbf{c.*} How many ways can we place $r$ indistinguishable objects into $n$ indistinguishable boxes?\\
\textbf{d.*} How many ways can we place $r$ distinguishable objects into $n$ indistinguishable boxes?\\

% \clearpage
\problem\textbf{*}\ [10pts] Let $n$ and $k$ be positive integers.
Let $P(n,k)$ be the number of integer partitions of $n$ into $k$ nonnegative parts (i.e. number of representations $n = a_1 + \cdots + a_k$ where each $a_i \in \N$ and $a_1 \geq a_2 \geq \cdots \geq a_k$.)
Let $P^+(n,k)$ to be the number of integer partitions of $n$ into $k$ \emph{positive} parts (i.e. the number of representations $n = a_1 + \cdots + a_k$ where $a_i \in \Z^+$ and $a_1 \geq a_2 \geq \cdots \geq a_k$.)

Prove that $P^+(n,k) = P(n-k,k)$.

% GRAPHS!
% \clearpage
\problem\ [10pts] Let $t \geq 2$ and $n_1,\dots, n_t$ be positive integers. The \emph{$n_1 \times n_2 \times \cdots \times n_t$ grid} is the graph whose vertices are the $t$-tuples $(x_1,\dots,x_t)$ with $x_i \in \{1,\dots,n_i\}$ for each $i$ and two vertices $(x_1,\dots,x_t)$ and $(y_1,\dots,y_t)$ are adjacent if and only if for some $j \in \{1,\dots,t\}$ we have $x_i = y_i$ for all $i \in \{1,\dots,t\} \setminus \{j\}$ and $|x_j-y_j| = 1$ (i.e. they differ in exactly one coordinate, and they differ by exactly 1 in that coordinate). 

Prove that for all $t \geq 2$ and $n_1, \dots, n_t$ the $n_1\times n_2 \times \cdot \times n_t$ grid is bipartite. [Hint: Recall the proof that the $k$-dimensional grid is bipartite and use a similar idea to produce a bipartition.]


% GRAPHS!
% \clearpage
\problem\ [15pts] The \emph{degree sequence} of a graph is the list of $|V(G)|$ values $d(v)$ for $v \in V(G)$, sorted from largest to smallest.
For example, the degree sequence of $W_4$ is $(4,3,3,3,3)$.

\textbf{a.} [2pts] Describe the degree sequence of $K_n$ for $n \geq 1$.\\
\textbf{b.} [2pts] Describe the degree sequence of $C_n$ for $n \geq 3$.\\
\textbf{c.} [2pts] Describe the degree sequence of $W_n$ for $n \geq 3$.\\
\textbf{d.} [2pts] Describe the degree sequence of $Q_n$ for $n \geq 2$.

A nonincreasing list of $n$ numbers $(d_1,d_2,\dots,d_n)$ is \emph{graphic} if it is the degree sequence of a graph.

\textbf{e.} [3pts] Prove that if $(d_1,d_2,\dots,d_n)$ is graphic, then $\sum_{i=1}^n d_i$ is even.\\
\textbf{f.}  [3pts] Prove that the sequence $(n,n-1,n-2,\dots,2,1,0)$ is not graphic.








\end{document} 