5 Assignment 5

5.1 Problem 1

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 \]

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 \]

Proposition 5

\[ \sum _{i=0}^n(-1)^i {n \choose i}(n-i)^n=n! \]

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 \]

Proposition 6

\[ \sum _{i=0}^k(-1)^i {k \choose i}(k-i)^n=0 \quad \text{when } k{\gt}n. \]

Proof ▼

\(\Rightarrow \) using the result above, for \(k{\gt}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{\gt}0\) pigeons. following the Pigeonhole principle there are is-no option to do so, or equivalence to 0 ways.

Proposition 7

\[ 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

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 \]

5.2 Problem 2

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 \]

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} \]

5.3 Problem 3

Proposition 8

Let N be a set, then any \(k\subseteq N \) have bijection such that \(k\to \{ 0,1\} ^{|N|}\)

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

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\)

Proof ▼

using Proposition 8. 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{\lt} 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" ² problem :

\[ \binom {n-2k+1-1}{k+1-1}=\binom {n-2k}{k} \]

5.4 Problem 4

Lemma 5.1

\[ 1\ge m-{m \choose 2} \quad m\ge 1, m\in \mathbb {N} \]

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\)

Lemma 5.2

\[ 1\le m-{m \choose 2}+{m\choose 3} \quad m\ge 1, m\in \mathbb {N} \]

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 \\ & \Leftrightarrow 0\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.

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

claim 5.3

\[ \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| \]

Proof ▼

to prove the following claim I will use "Donation to the Argument" ³ 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 5.1 the inequality hold for any \(a\in A\). and that lead to finish the proof

claim 5.4

\[ \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| \]

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 5.3 the inequality hold for any \(a\in A\). and that lead to finish the proof.