% Like most advanced LaTeX files, this one begins with a lot of
% boilerplate. You don't need to understand (or even read) most of it.
% All you need to do is fill in your name, email address,
% and the number of the pset. (Search for "METADATA" to find the place
% for this.) Then, you can go straight to the "EXERCISE 1"
% section and start writing your solutions.
% The "VARIOUS USEFUL COMMANDS" section is probably worth taking a
% look at at some point.

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------
\documentclass[paper=a4, fontsize=12pt]{scrartcl} % A4 paper and 12pt font size
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm,amssymb} % Math packages
\usepackage{mathrsfs}    % More math packages
\usepackage{sectsty}  % Allows customizing section commands
\allsectionsfont{\centering \normalfont\scshape} % Make all section titles centered, the default font and small caps %remove this to left align section tites
\usepackage{hyperref} % Turns cross-references into hyperlinks,
                      % and defines \url and \href commands.
\usepackage{graphicx} % For embedding graphics files.
\usepackage{framed}   % For the "leftbar" environment used below.
\usepackage{ifthen}   % Used for the \powset command below.
\usepackage{lastpage} % for counting the number of pages
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}     % This is a powerful tool to draw vector
                      % graphics inside LaTeX. In particular, you can
                      % use it to draw graphs.
\usepackage{verbatim} % For the "verbatim" environment, in which
                      % special symbols can be used freely without
                      % confusing the compiler. (And it's typeset in
                      % a constant-width font.)
                      % Useful, e.g., for quoting code (or ASCII art).
\usepackage{tabls}

%\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{20pt} % Makes indentation for paragraphs longer.
                           % This makes paragraphs stand out more.

%----------------------------------------------------------------------------------------
%	VARIOUS USEFUL COMMANDS
%----------------------------------------------------------------------------------------
% The commands below might be convenient. For example, you probably
% prefer to write $\powset[2]{V}$ for the set of $2$-element subsets
% of $V$, rather than writing $\mathcal{P}_2(V)$.
% Notice that you can easily define your own commands like this.
% Caveat: Some of these commands need to be properly "guarded" when
% they occur in subscripts or superscripts. So you should not write
% $K_\CC$, but rather $K_{\CC}$.
\newcommand{\CC}{\mathbb{C}} % complex numbers
\newcommand{\RR}{\mathbb{R}} % real numbers
\newcommand{\QQ}{\mathbb{Q}} % rational numbers
\newcommand{\NN}{\mathbb{N}} % nonnegative integers
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}} % integers modulo k
                                            % (syntax: "\Z{k}")
\newcommand{\ZZ}{\mathbb{Z}} % integers
\newcommand{\id}{\operatorname{id}} % identity map
\newcommand{\lcm}{\operatorname{lcm}}
% Lowest common multiple. For historical reasons, LaTeX has a \gcd
% command built in, but not an \lcm command. The preceding line
% rectifies that.
\newcommand{\rev}{\operatorname{rev}} % reversal of a walk
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
% $\powset[k]{S}$ stands for the set of all $k$-element subsets of
% $S$. The argument $k$ is optional, and if not provided, the result
% is the whole powerset of $S$.
\newcommand{\set}[1]{\left\{ #1 \right\}}
% $\set{...}$ compiles to {...} (set-brackets).
\newcommand{\abs}[1]{\left| #1 \right|}
% $\abs{...}$ compiles to |...| (absolute value, or size of a set).
\newcommand{\tup}[1]{\left( #1 \right)}
% $\tup{...}$ compiles to (...) (parentheses, or tuple-brackets).
\newcommand{\ive}[1]{\left[ #1 \right]}
% $\ive{...}$ compiles to [...] (Iverson bracket, aka truth value).
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
% $\ceil{...}$ compiles to the ceiling of ..l..
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
% $\verts{...}$ compiles to V(...) (vertex set of a graph/digraph).
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
% $\edges{...}$ compiles to E(...) (edge set of a graph).
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
% $\arcs{...}$ compiles to A(...) (arc set of a digraph).
\newcommand{\lf}[2]{#1^{\underline{#2}}}
% $\lf{...1}{...2}$ compiles to $...1^{\underline{...2}}$.
% This is a notation for the falling factorial.
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
% $\underbrack{...1}{...2}$ yields
% $\underbrace{...1}_{\substack{...2}}$. This is useful for doing
% local rewriting transformations on mathematical expressions with
% justifications. For example, try this out:
% $ \underbrack{(a+b)^2}{= a^2 + 2ab + b^2 \\ \text{(by the binomial formula)}} $
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height
\newcommand{\nnn}{\nonumber\\} % Don't number this line in an "align" environment, and move on to the next line.
\newcommand{\explain}[1]{\tup{\hspace{-0.5pc}\text{\begin{tabular}{c}#1\end{tabular}\hspace{-0.5pc}}}}
% $\explain{...}$ interprets the "..." as text (you can
% nest some math inside by putting it in $...$'s as you
% would in any other text block) and puts it in parentheses.

%----------------------------------------------------------------------------------------
%	MAKING SUMMATION SIGNS ALWAYS PUT THEIR BOUNDS ABOVE AND BELOW
%	THE SIGN
%----------------------------------------------------------------------------------------
% The following are hacks to ensure that sums (such as
% $\sum_{k=1}^n k$) always put their bounds (i.e., the $k=1$ and the
% $n$) underneath and above the sign, as opposed to on its right.
% Same for products (\prod), set unions (\bigcup) and set
% intersections (\bigcap). Remove the 8 lines below if you do not want
% this behavior.
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}

%----------------------------------------------------------------------------------------
%	ENVIRONMENTS
%----------------------------------------------------------------------------------------
% The incantations below define how theorem environments
% (\begin{theorem} ... \end{theorem}) and their likes will look like.
\newtheoremstyle{plainsl}% <name>
  {8pt plus 2pt minus 4pt}% <Space above>
  {8pt plus 2pt minus 4pt}% <Space below>
  {\slshape}% <Body font>
  {0pt}% <Indent amount>
  {\bfseries}% <Theorem head font>
  {.}% <Punctuation after theorem head>
  {5pt plus 1pt minus 1pt}% <Space after theorem headi>
  {}% <Theorem head spec (can be left empty, meaning `normal')>

% Environments which make the text inside them slanted:
\theoremstyle{plainsl}
  \newtheorem{theorem}{Theorem}[section]
  \newtheorem{proposition}[theorem]{Proposition}
  \newtheorem{lemma}[theorem]{Lemma}
  \newtheorem{corollary}[theorem]{Corollary}
  \newtheorem{conjecture}[theorem]{Conjecture}
% Environments that don't:
\theoremstyle{definition}
  \newtheorem{definition}[theorem]{Definition}
  \newtheorem{example}[theorem]{Example}
  \newtheorem{exercise}[theorem]{Exercise}
  \newtheorem{examples}[theorem]{Examples}
  \newtheorem{algorithm}[theorem]{Algorithm}
  \newtheorem{question}[theorem]{Question}
 \theoremstyle{remark}
  \newtheorem{remark}[theorem]{Remark}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}

%----------------------------------------------------------------------------------------
%	METADATA
%----------------------------------------------------------------------------------------
\newcommand{\myname}{Darij Grinberg} % ENTER YOUR NAME HERE
\newcommand{\mymail}{darij.grinberg@drexel.edu} % ENTER YOUR EMAIL HERE
\newcommand{\psetnumber}{4} % ENTER THE NUMBER OF THIS PSET HERE

%----------------------------------------------------------------------------------------
%	HEADER AND FOOTER
%----------------------------------------------------------------------------------------
\ihead{Solutions to homework set \#\psetnumber} % Page header left
\ohead{page \thepage\ of \pageref{LastPage}} % Page header right
\ifoot{\myname} % left footer
\ofoot{\mymail} % right footer

%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------
\title{	
\normalfont \normalsize 
\textsc{Drexel University, Department of Mathematics} \\ [25pt] % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge Math 222: Enumerative Combinatorics, \\
Fall 2022:
Homework \psetnumber\\% The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}
\author{\myname}

\begin{document}

\maketitle % This command causes the title part to be printed.

\begin{center} % Delete this if you want to save space!
{\vspace{-1.5pc} \large due date: \textbf{Monday, 2022-11-14} at 11:59 PM on gradescope.

\vspace{0.5pc}Please solve \textbf{3 of the 6 exercises}!}
\end{center}

%----------------------------------------------------------------------------------------
%	EXERCISE 1
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 1}

\subsection{Problem}

Let $A$, $B$ and $C$ be three finite sets such that $C \subseteq B$.
Let $a = \abs{A}$ and $b = \abs{B}$ and $c = \abs{C}$.

Prove that the \# of maps $f : A \to B$ satisfying\footnote{We
let $f\tup{A}$ denote the range of $f$, that is, the set
$\set{f\tup{x} \mid x \in A}$.}
$C \subseteq f\tup{A}$ is
\[
\sum_{k=0}^{c} \tup{-1}^k \dbinom{c}{k} \tup{b-k}^a .
\]

\subsection{Remark}

Applying this to $C = B$, we recover the explicit formula
for $\operatorname{sur}\tup{a, b}$ (\cite[Theorem 2.4.17]{notes}),
because a map $f : A \to B$ satisfying $B \subseteq f\tup{A}$
is the same as a surjection from $A$ to $B$.

\subsection{Solution}

[...] % Enter your solution here!

%----------------------------------------------------------------------------------------
%	EXERCISE 2
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 2}

\subsection{Problem}

Let $n \in \NN$. Prove that
\[
\sum_{k=0}^{n} \tup{-2}^{n-k} \dbinom{n}{k} \dbinom{2k}{k}
= \dbinom{n}{n/2}.
\]

[Note that the right hand side is $0$ when $n$ is odd.]

\subsection{Hint}

Consider $2\times n$-matrices
$A =
\begin{pmatrix}
a_1 & a_2 & \cdots & a_n \\
b_1 & b_2 & \cdots & b_n
\end{pmatrix}$
with the following properties:
\begin{enumerate}
\item All entries of $A$ belong to the set $\set{0, 1}$.
\item We have
$a_1 + a_2 + \cdots + a_n = b_1 + b_2 + \cdots + b_n$
(that is, the entries in each row of $A$ add up to
the same number).
\item We have $a_i + b_i = 1$ for all $i \in \ive{n}$
(that is, each column of $A$ contains a $0$ and a $1$).
\end{enumerate}
Count these matrices in two different ways: once directly,
and once using the Principle of Inclusion and Exclusion
(letting $U$ be the set of matrices satisfying
properties 1 and 2).

\subsection{Solution}

[...] % Enter your solution here!

%----------------------------------------------------------------------------------------
%	EXERCISE 3
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 3}

\subsection{Problem}

Let $n \in \NN$. Let $U$ be a finite set. Let $A_1, A_2, \ldots, A_n$
be $n$ subsets of $U$. Let $k \in \NN$. Let $G_k$ be the set of all
elements of $U$ that belong to at least $k$ of the $n$ subsets
$A_1, A_2, \ldots, A_n$. In other words, let
\[
G_k =
\set{ s \in U \ \mid \ \text{the number of } i \in \ive{n}
\text{ satisfying }s \in A_i \text{ is } \geq k }.
\]
Prove that
\[
\abs{G_k}
=
\sum_{I \subseteq \ive{n}} \tup{-1}^{\abs{I} - k}
   \dbinom{\abs{I} - 1}{\abs{I} - k}
   \abs{\bigcap_{i\in I} A_i }.
\]
Here, the intersection $\bigcap_{i\in \varnothing} A_i$ is understood
to mean the whole set $U$.

\subsection{Remark}

Note that $G_0 = U$ and $G_1 = A_1 \cup A_2 \cup \cdots \cup A_n$.
Thus, by setting $k=1$ in this exercise, you recover the
Principle of Inclusion and Exclusion (in the union form).

\subsection{Hint}

This is an analogue of \cite[Exercise 1]{17f-hw7s}, which you can use
without proof. You can also use \cite[Exercise 2.1.1]{notes}.

\subsection{Solution}

[...] % Enter your solution here!

%----------------------------------------------------------------------------------------
%	EXERCISE 4
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 4}

\subsection{Problem}

Let $U$, $V$ and $W$ be three sets, with $U$ and $W$ being finite.
Prove that
\[
\sum_{I\subseteq U}
 \tup{-1}^{\abs{\tup{I \setminus V} \cup W}}
=
\begin{cases}
2^{\abs{U}} \tup{-1}^{\abs{W}}, & \text{if } U \subseteq V \cup W; \\
0, & \text{otherwise.}
\end{cases}
\]

\subsection{Hint}

This equality is in the vein of \cite[Section 2.9.7]{notes}.

\subsection{Solution}

[...] % Enter your solution here!

%----------------------------------------------------------------------------------------
%	EXERCISE 5
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 5}

\subsection{Problem}

Let $n$ and $k$ be two positive integers with $k \geq 2$.

A composition $\tup{a_1, a_2, \ldots, a_k}$ of $n$ into $k$
parts will be called \emph{lopsided} if one of its entries $a_i$
is larger than $n/2$.
(For instance, the composition $\tup{1, 5, 3}$ is
lopsided, but the composition $\tup{1, 4, 3}$ is not.)

Prove that the \# of lopsided compositions of $n$ into $k$
parts is $k \dbinom{\ceil{n/2} - 1}{k-1}$.

\subsection{Remark}

This can be restated as follows:
If a stick of length $n$ is broken into $k$ pieces at random
(by choosing a random $\tup{k-1}$-element subset of $\ive{n-1}$
and breaking the stick at the positions in this subset),
then the probability that these $k$ pieces are the sidelengths
of a (possibly degenerate) $k$-gon is
$1 - \dfrac{k \dbinom{\ceil{n/2} - 1}{k-1}}{\dbinom{n-1}{k-1}}$.
(Indeed, $k$ positive real numbers $a_1, a_2, \ldots, a_k$ are
the sidelengths of a (possibly degenerate) $k$-gon if and only
if they satisfy the ``polygon inequalities'', which say that
no $a_i$ is larger than $\dfrac{a_1+a_2+\cdots+a_k}{2}$.)

\subsection{Solution}

[...] % Enter your solution here!

%----------------------------------------------------------------------------------------
%	EXERCISE 6
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 6}

\subsection{Problem}

Let $n \in \NN$.
How many (ordered) pairs $\tup{A, B}$ of two nonempty subsets of
$\ive{n}$ have the property that $\max A > \abs{B}$ and
$\max B > \abs{A}$ ?
\medskip

[\textbf{Example:} The pair $\tup{\set{1, 4}, \set{1, 2, 3}}$
(for $n = 4$)
qualifies, since $\max \set{1, 4} = 4 > 3 = \abs{\set{1, 2, 3}}$
and $\max \set{1, 2, 3} = 3 > 2 = \abs{\set{1, 4}}$.
However, the pair $\tup{\set{1, 3}, \set{2, 3, 4}}$ does not
qualify, since
$\max\set{1, 3} \leq \abs{\set{2, 3, 4}}$.]

\subsection{Solution}

[...] % Enter your solution here!

\horrule{0.3pt} \\[0.4cm]

\begin{thebibliography}{99999999}                                                                                         %

% This is the bibliography: The list of papers/books/articles/blogs/...
% cited. The syntax is: "\bibitem[name]{tag}Reference",
% where "name" is the name that will appear in the compiled
% bibliography, and "tag" is the tag by which you will refer to
% the source in the TeX file. For example, the following source
% has name "Math222" (so you will see it referenced as
% "[Math222]" in the compiled PDF) and tag "notes" (so you
% can cite it by writing "\cite{notes}").

\bibitem[17f-hw7s]{17f-hw7s}
Darij Grinberg,
\textit{UMN Fall 2017 Math 4990
homework set \#7 with solutions},
\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw7os.pdf}

\bibitem[Math222]{notes}
Darij Grinberg,
\textit{Enumerative Combinatorics: class notes},
13 September 2022. \\
\url{http://www.cip.ifi.lmu.de/~grinberg/t/19fco/n/n.pdf} 
Also available on the mirror server
\url{http://darijgrinberg.gitlab.io/t/19fco/n/n.pdf}

\end{thebibliography}

\end{document}

