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} (\binom{k}{i}) (k - i)^{n}

Proof ▼

denote

f_{x} = {f : f^{- 1} [C] s.t [C] \subseteq [k], | C | \leq | 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 $(\binom{k}{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 $(\binom{k}{1}) (k - 1)$ functions. and for general $x$ it is $| f_{x} | = (\binom{k}{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 \leq x \leq y \leq k$ then :

f_{o n t o} \in ⋂_{i = 1}^{k} \overset{―}{f_{i}} \Rightarrow | ⋂_{i = 1}^{k} \overset{―}{f_{i}} | = \footnote D e M o r g a n | S - ⋃_{i = 1}^{k} f_{i} |

using inclusion exclusion principle we get that.

(\binom{k}{0}) k^{n} - (\binom{k}{1}) (k - 1)^{n} + (\binom{k}{2}) (k - 2)^{n} - \dots \pm (\binom{k}{k - 2}) 2^{n} \mp (\binom{k}{k - 1}) 1^{n} \pm (\binom{k}{k}) 0^{n}

that is

\sum_{i = 0}^{k} (- 1)^{i} (\binom{k}{i}) (k - i)^{n}

Proposition 5

\sum_{i = 0}^{n} (- 1)^{i} (\binom{n}{i}) (n - i)^{n} = n!

Proof ▼

$\Rightarrow$ using the result above, for $k = n$ its following that :

\sum_{i = 0}^{n} (- 1)^{i} (\binom{n}{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} (\binom{n}{i}) (n - i)^{n}

Proposition 6

\sum_{i = 0}^{k} (- 1)^{i} (\binom{k}{i}) (k - i)^{n} = 0 when k > n .

Proof ▼

$\Rightarrow$ using the result above, for $k > n$ its following that :

\sum_{i = 0}^{k} (- 1)^{i} (\binom{k}{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.

Proposition 7

S (n, k) = \frac{1}{k!} \sum_{i = 0}^{k} (- 1)^{i} (\binom{k}{i}) (k - i)^{n}

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} (\binom{k}{i}) (k - i)^{n}

$\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} (\binom{k}{i}) (k - i)^{n} = \sum_{i = 0}^{k} (- 1)^{i} (\binom{k}{i}) (k - i)^{n}

5.2 Problem 2

claim

the number of ways of coloring the integers ${1 \dots 2 n}$ using the colors red/blue in such a way that if i is colored red then so is $i - 1$ , is:

\sum_{k = 0}^{n} (- 1)^{k} (\binom{2 n - k}{k}) 2^{2 n - 2 k} = 2 n + 1

Proof ▼

I will use counting in two ways method to deduce the identity
$\Rightarrow$ we can consider the problem as placing $2 n$ 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 $2 n - 2$ in between any two adjacent numbers from 1 to $2 n$ . 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 $2 n + 1$ .
$\Leftarrow$ There are in total $S = 2^{2 n}$ 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^{2 n - 2} (\binom{2 n - 1}{1})

now same idea for 2 paris

2^{2 n - 4} (\binom{2 n - 1}{2})

and in general :

2^{2 n - 2 i} (\binom{2 n - i}{i})

Using Inclusion exclusion principle we get that

2^{2 n} - 2^{2 n - 2} (\binom{2 n - 1}{1}) + \dots \pm (\binom{2 n - n}{n}) 2^{2 n - 2 n}

that is :

\sum_{k = 0}^{n} (- 1)^{k} (\binom{2 n - k}{k}) 2^{2 n - 2 k}

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 : {\begin{array}{ccc} k & \mapsto & x \in N \mapsto {\begin{cases} 0 & , if x \notin N \\ 1 & , if x \in N \end{cases} \end{array} f^{- 1} {{0, 1}^{N} \mapsto {x \in N 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 $(\binom{n - k + 1}{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 < 2 k - 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 \geq 2 k - 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 - (\underset{k \times \mathds 1^{'} s}{\underset{⏟}{k}} + \underset{(k - 1) \times 0^{'} s}{\underset{⏟}{(k - 1)}}) = n - 2 k + 1

it is $n - 2 k + 1$ number of 0’s in the $k + 1$ optinal positions and. that is "Stars and bars" ² problem :

(\binom{n - 2 k + 1 - 1}{k + 1 - 1}) = (\binom{n - 2 k}{k})

5.4 Problem 4

Lemma 5.1

1 \geq m - (\binom{m}{2}) m \geq 1, m \in N

Proof ▼

\begin{aligned} 1 \geq m - (\binom{m}{2}) & \Leftrightarrow 1 \geq m - \frac{m^{2} - m}{2} \\ m^{2} - 3 m + 2 \geq 0 & \Leftrightarrow (m - 1) (m - 2) \geq 0 \end{aligned}

And the right hand size grater then zero for any $m \geq 2$

Lemma 5.2

1 \leq m - (\binom{m}{2}) + (\binom{m}{3}) m \geq 1, m \in N

Proof ▼

\begin{aligned} 1 \leq m - (\binom{m}{2}) + (\binom{m}{3}) & \Leftrightarrow 1 \leq m - \frac{m^{2} - m}{2} + \frac{m^{3} - 2 m^{2} - 2 m}{6} \\ \Leftrightarrow 0 \leq m^{3} - 6 m^{2} + 11 m - 6 \\ \Leftrightarrow 0 \leq (m - 3) (m - 2) (m - 1) \end{aligned}

The right hand size grater then zero for any $m \geq 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

| ⋃_{i = 1}^{n} A_{i} | \geq \sum_{1 \leq i \leq n} | A_{i} | - \sum_{1 \leq i \leq j \leq 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 \geq 1$ sets, then at the right hand side its count $(\binom{m}{1})$ times at the first argument, and $(\binom{m}{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

| ⋃_{i = 1}^{n} A_{i} | \leq \sum_{1 \leq i \leq n} | A_{i} | - \sum_{1 \leq i \leq j \leq n} | A_{i} \cap A_{j} | + \sum_{1 \leq i \leq j \leq k \leq 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 $(\binom{m}{1})$ on the $1^{nd}$ term. $(\binom{m}{2})$ on the $2^{nd}$ and $(\binom{m}{3})$ at the $3^{nd}$ term. Hence using Lemma 5.3 the inequality hold for any $a \in A$ . and that lead to finish the proof. □