Basic Combinatorics - Spring, Home Assignment 5.tex

\documentclass[12pt]{article}
\usepackage{lingmacros}
\usepackage{tree-dvips}
\usepackage[english]{babel}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{amsmath}
\newtheorem*{claim*}{claim}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{claim}
\newtheorem*{theorem*}{Theorem}
\newcommand{\ndiv}{\hspace{-4pt}\not|\hspace{2pt}}
\usepackage{amssymb}
\newtheorem{prop}{Proposition}
\usepackage{mathrsfs} 
\newtheorem{Theorem}{Theorem}
\usepackage{babel}
\usepackage{calc}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{lipsum}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{dsfont}
\setcounter{section}{4}


\begin{document}
\begin{center}
\section*{Basic Combinatorics - Spring\\$\sim$ Home Assignment 5 $\sim$ }
\subsubsection*{Saar Barak}
\end{center}
\subsection*{Problem 1}
\begin{claim*}the number of surjective  mappings from [n] to [k] is given by\[
\sum_{i=0}^k(-1)^i {k \choose i}(k-i)^n
\]
\end{claim*}
\begin{proof}
denote $$f_{x}=\{f: f^{-1}[C] \text{ s.t } [C]\subseteq[k],\quad|C|\le |k-x|   \}$$ to be the set of all function  from $[n]$ to subset of $[k]$ where at least $x$ element of $k$ is not in the image of $f_x$.
let look at $f_1$, we can choose 1 from $k$ element to not be part of the image, it is $k \choose 1$. now we have $k-1$ elements to choose from $n$ items, i.e which item from $n_i\in n$ will map to  $k_j\in k$. 
Hence we looking at total ${k \choose 1} (k-1)$ functions. and for general $x$ it is $|f_x|={ k \choose x}(k-x)^n$. now lets $f_0=S$ to be the set of all function from $[n]$ to $[m]$, since $f_x \subseteq f_y$ for $0\le  x \le y\le k$ then :
\[f_{onto} \in \bigcap_{i=1}^{k}\overline{f_i}\Rightarrow|\bigcap_{i=1}^{k}\overline{f_i}|=\footnote{De Morgan}| S - \bigcup_{i=1}^{k}f_i|
\]
using inclusion exclusion principle we get that. 
\[{k \choose 0}k^n - {k \choose 1}(k-1)^n + {k \choose 2}(k-2)^n - \cdots \pm {k \choose k-2}2^n \mp {k \choose k-1}1^n \pm {k \choose k}0^n
\]
that is \[\sum_{i=0}^k(-1)^i {k \choose i}(k-i)^n
\]
\end{proof}
\pagebreak

\begin{prop}\[\sum_{i=0}^n(-1)^i {n \choose i}(n-i)^n=n!
\]
\end{prop}
\begin{proof} 
$\Rightarrow$ using the result  above, for $k=n$ its following that :
\[\sum_{i=0}^n(-1)^i {n \choose i}(n-i)^n=n!
\]
$\Leftarrow$ the number of onto function from $[n]$  to $[n]$ is equivalence to to the number of ways to arrange $n$ distinct elements in row , that is 
\[n!=\sum_{i=0}^n(-1)^i {n \choose i}(n-i)^n
\]
\end{proof}

\begin{prop}\[\sum_{i=0}^k(-1)^i {k \choose i}(k-i)^n=0 \quad \text{when } k>n.
\]
\end{prop}
\begin{proof}$\Rightarrow$  using the result  above, for $k>n$ its following that :
\[\sum_{i=0}^k(-1)^i {k \choose i}(k-i)^n=0
\]
$\Leftarrow$ assume we have $k$ pigeons, we need to find in how many ways we can place them all in $n$  holes, when each one of them in different hole.
after placing $n-k$ of them  the all the holes are full and we left with $k-n>0$ pigeons. following the  Pigeonhole principle there are is-no option to do so, or equivalence to 0 ways.
\end{proof}
\begin{prop}\[
S(n,k)=\frac{1}{k!}\sum_{i=0}^k(-1)^i {k \choose i}(k-i)^n\quad 
\]
where S(n, k) are the Stirling numbers of the second kind
\end{prop}
\begin{proof}
$\Rightarrow$its immediate from the definition of $S(n,k)$ :
\[S(n,k)=\frac{1}{k!}\sum_{i=0}^k(-1)^i {k \choose i}(k-i)^n\quad 
\]
$\Leftarrow$ we can consider the the set $S_k$:
 \[S_k:=\{\{f^{-1}(x)\},\forall x\in k \}
\]
we are looking at total of $k$ non-empty sets. the amount of subjective function from $[n]$  to $[k]$ is  number of ways to distribute the elements of $n$ into these sets, let $S(n,S_k)$ be the number of ways to partition a set of n objects into $S_k=|k|$ non-empty subsets. now we can notice that any $k_i\in k$ can be associated with any of these sets i.e total of $k!$. and in  total we get:
\[
S(n,S_k)k!=S(n,k)k!=k!\frac{1}{k!}\sum_{i=0}^k(-1)^i {k \choose i}(k-i)^n =\sum_{i=0}^k(-1)^i {k \choose i}(k-i)^n
\]
\end{proof}
\subsection*{Problem 2}
\begin{claim*}the number of ways of coloring the integers $\{ 1 \dots 2n \}$ using the colors red/blue in such a way that if i is colored red then so is $i-1$, is:
\[\sum^n_{k=0}(-1)^k\binom{2n-k}{k}2^{2n-2k}=2n+1
\]
\end{claim*}
\begin{proof} I will use  counting in two ways method to deduce the identity\\
$\Rightarrow$ we can consider the problem as placing $2n$ items in a row and choose spot to place separator s.t any item to its left are red and all the other are blue. we looking at total of $2n-2$ in between  any two adjacent numbers from 1 to $2n$. by including 2 more additional option that all of them red or blue, we get that the total of number of ways to place the separator is given by $2n+1$ .\\
$\Leftarrow$ 
There are in total $S=2^{2n}$ ways of coloring the integers. with same idea as above, we can consider the separator as choose pair of adjacent integers the first will be coloring with R and the second B and rest dont care, it is:
\[2^{2n-2}\binom{2n-1}{1}
\]
now same idea for 2 paris
\[2^{2n-4}\binom{2n-1}{2}
\]
and in general :
\[2^{2n-2i}\binom{2n-i}{i}
\]
Using Inclusion exclusion principle we get that
\[2^{2n}-2^{2n-2}\binom{2n-1}{1}+\dots\pm \binom{2n-n}{n}2^{2n-2n}
\]
that is :
\[\sum^n_{k=0}(-1)^k\binom{2n-k}{k}2^{2n-2k}
\]
\end{proof}
\subsection*{Problem 3}
\begin{prop}
 Let N be a set, then any $k\subseteq N $ have  bijection such that
$k\to\{0,1\}^{|N|}$
\end{prop}
let define the following mapping 
\[
f:\left\{\begin{array}{ccc}k&\mapsto&x\in N\mapsto\left\{\begin{array}{ll}0&\textrm{, if }x\notin N\\1&\textrm{, if }x\in N\end{array}\right.\end{array}\right.\quad f^{-1}\{\{0,1\}^N \mapsto \{x\in N\textrm{ s.t. }f(x)=1\}
\]
we can consider it as binary encode of the subset indicate $\mathds{1}$ if the given integer in the subset and 0 otherwise
\begin{claim*} the number of subsets of size k of $\{1,\dots n\}$ which contain no pair of
consecutive integers is given by $n-k+1 \choose k$
\end{claim*}
\begin{proof}
 using Proposition 4. subset $k$ can represented as some binary string of length $n$, its yield that if in some  string have  two consecutive appearances $\mathds{1}$ then this subset contain pair of
consecutive integers. moreover we can notice that if  $n< 2k-1$ then its can not contain pair of
consecutive integers.\\\\
For given k  let $f(k)$  define the bijection of subset $k$ for some $n\ge 2k-1$. if we assume its not have any consecutive numbers, then its have k  $\mathds{1}$'s and $n-k$ 0's. since we know $k-1$ from the 0's must be followed by the first $k-1$ of $\mathds{1}$'s. hence the following problem becomes, how many ways could we distribute the remaining element i.e\[ 
n-(\underbrace{k}_{k\times \mathds{1}'s} + \underbrace{(k-1)}_{(k-1) \times 0's})=n-2k+1 
\]
it is $n-2k+1$ number of 0's in the $k+1$ optinal positions and. that is  "Stars and bars"\footnote{ Not sure if saw in class -\href{https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)}{\emph{"Stars and Bars from Wikipedia"}
}} problem  :
\[\binom{n-2k+1-1}{k+1-1}=\binom{n-2k}{k}
\]  
\end{proof}
\subsection*{Problem 4}
\begin{lemma}
\[1\ge m-{m \choose 2} \quad m\ge 1, m\in \mathbb{N}
\]\end{lemma}
\begin{proof}

\begin{align*}
1\ge m-{m \choose 2} &\Leftrightarrow 1\ge m-\frac{m^2-m}{2}
\\
m^2-3m+2\ge 0 &\Leftrightarrow (m-1)(m-2)\ge 0
\end{align*}
And the right hand size grater then zero for any $m\ge 2$
\end{proof}

\hrulefill
\begin{lemma}
\[1\le m-{m \choose 2}+{m\choose 3} \quad m\ge 1, m\in \mathbb{N}
\]\end{lemma}
\begin{proof}
\begin{align*}
1\le m-{m \choose 2}+{m\choose 3} &\Leftrightarrow 1\le m-\frac{m^2-m}{2}+\frac{m^3-2m^2-2m}{6}
\\
 &\Leftrightarrow 0 \le m^3 -6m^2+11m-6
 \\
  &\Leftrightarrow0\le  (m-3)(m-2)(m-1)
\end{align*} 
 The right hand size grater then zero for any $m\ge 3$, and equal 0  for $m\in\{1,2\}$ since m is an integer.
\end{proof}

Let $A_1,A_2\dots A_n$ be a family of n sets.

\begin{claim}\[
\left|\bigcup_{i=1}^nA_i \right|\ge \sum_{1\le i\le n} |A_i|-
\sum_{1\le i\le j\le n}|A_i\cap A_j|
\]
\end{claim}
\begin{proof}to prove the following claim I will use "Donation to the Argument" \footnote{To be honest I am not really sure what the name of this technique, Its kind of similar to "Counting derangements" I think } method. let assume that exists some $a\in A_i$. this $a$ adding at most 1 to the left hand side. now consider  $a$ is part of some other $m\ge 1$ sets, then at the right hand side   its count $m \choose 1$ times at the first argument, and $m\choose 2$ in the second. Hence using Lemma 4.2 the inequality hold for any $a\in A$. and that lead to finish the proof 
\end{proof}
\begin{claim}\[
\left|\bigcup_{i=1}^nA_i \right|\le \sum_{1\le i\le n} |A_i|-
\sum_{1\le i\le j\le n}|A_i\cap A_j|+\sum_{1\le i\le j\le k\le n}|A_i\cap A_j\cap A_k|
\]
\end{claim}
\begin{proof} using same idea described above, let $a\in A_i$
then $a$ count once on the left hand-sid. At the right hand-side $a$ count $m \choose 1$ on the $1^{\text{nd}}$ term. $m \choose 2$ on the $2^{\text{nd}}$ and $m \choose 3$ at the $3^{\text{nd}}$ term. Hence using Lemma 4.2 the inequality hold for any $a\in A$. and that lead to finish the proof. 
\end{proof}
\end{document}