Cs150Test1 - HackMD

# Notice!!! TEST 1 will be on Wed. March 6 in class from 1:30 to 3:00PM [TOC] ## Chapter 1 **Introduction** ---- ### Why counting? --> Everyday math E.g. Lazy professor, permutating test among 3 students (A,B,C) possible permutations(6): (A,B,C) (A,C,B) (C,B,A) (B,A,C) (B,C,A) (C,A,B) only (B,C,A) and (C,A,B) are good. Therefore, the probability is $\frac{2}{6} = \frac{1}{3}$. In general, however, the number of permutations is: $n! = 1 \times 2 \times \ldots \times n = \prod_{i=1}^{n} i$ where $n$ is the number of students. Discrete mathematics deal with things that are not continuous, like number theory which studies integers. Consider for example the sum 1+2+3+...+n. In a continuous setting, one would explore the following expression: $\int_{0}^{n} x \, dx$ which is slightly different than the sum $1$ to $n$ above. A typical knowledge of calculus will make anyone realize that the integral represents the area under the function $f(x) = x$ taken between $x = 0$ and $x = n$. But what does the sum represent? This is related to an important result known as `the handshake lemma` and has many applications. Discrete mathematics is more like dealing with puzzles. The following is a list of topics that are typically covered in a discrete mathematics course: * combinatorics/counting * proofs (it is a mathematics course after all, and there is no mathematics without proofs) * algorithms/recursion/complexity * number theory * probability * graph theory ### Basic graph theory - Euler formula: $v - e + f = 2$ The quantities $v, e,$ and $f$ refer to vertices, edges, and faces respectively. Euler’s formula states that for any planar graph, $v − e + f = 2$. - In general, a graph consists of a set of vertices and a set of edges connecting pairs of vertices. - If edges do not cross the graph is said to be planar and faces are well defined. In fact, vertices can be placed arbitrarily and edges don’t have to be straight lines. Therefore, a graph is planar if it can be drawn while avoiding crossings (even if it can be drawn with crossings). ### Basic examples of counting (snakes and ladders) Snake head can be any space/square where $n$ is total number of spaces (let’s ignore that the head cannot be in the last square) snake tail must be in a lower number space/square which can be $n-1,n-2,...,1$ thus we have $n-1$ snakes with head on space $n$ - conclude --> The total number of snakes is therefore: $(n − 1) + (n − 2) + ... + 1$ Why addition? The idea is that each group of snakes is disjoint from all others. In other words, a snake cannot have its head in square $i$ and in another square $j$ for $i \neq j$ (unless it is a double headed snake!). ### Addition and multiplication rules - The **addition principle**: Consider $k$ sets $S_1,. . . , S_k$ that are pairwise disjoint. We denote by $|S_i|$ the size of set $S_i$ . The total number of elements in all sets is $|S_1| + |S_2| + ... + |S_k|$. e.g. previously The total number of snakes is therefore: $(n − 1) + (n − 2) + ... + 1 = \sum_{i=1}^{n-1} i$ same as $|S_1| + |S_2| + ... + |S_k|$ where $k=(n-1)$ $|S_i|$ represents a different pair of head and tail (one snake) - Second method aka **product/multiplication principle**: break into steps first step (head): $n$ choices second step (tail): $n-1$ choices $n(n − 1)$ outcomes but we have overcounts!!! > How do we know that we overcounted? Simply ask the following question: Given a snake, how many ways generate that same snake by our algorithm? Observe that square i followed by square j define the same snake as square j followed by square i (because the head of the snake has to be in the higher square). means there is overcount of 2 since (i,j) is same pair as (j,i) (1+1)/2 = 1 unique pair where head > tail; note order of i,j doesn't matter here: unordered--> k-combination Therefore, each snake is counted exactly twice. The number of possible snakes is n(n − 1)/2. - The multiplication principle: If an activity consists of $k$ stages, and stage $i$ can be carried out in $α_i$ ways, regardless of other stages, the activity can be carried out in $α_1,α_2 ... α_k$ ways. ### Generalization (n choose k) Where order is not important, we are choosing $k$ items from $n$. $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ e.g. - choosing pairs (order doesn't matter) - choosing letters alphabetically - choosing lottery numbers where order doesn't matter - snakes and ladders - **Handshake lemma** ### Handshake lemma Consider $n$ people that shake hands with each other. How many handshakes do we count? We first choose a person, then we choose another person. 2 people defines a handshake (pair, order doesn't matter) thus, n choose 2. Similar for graphs: - Degrees of vertices = edges connected to the vertex - 2 vertices makes an edge (a pair of vertices) (overcount of 2): $\binom{n}{2} = e = \frac {v(v-1)}{2}$ - The sum of the degrees is equal to twice the number of edges. * implies that the sum of degrees is always even. This in turn implies that there is a even number of vertices with odd degrees. $2e = v(v-1)$ ## Chapter 2 **Counting** ------- ### Permutations When order matters, e.g. ${a,b,c}\neq{c,b,a}$ = 2 different permutations $n!$ represents the number of possible seatings. In general, $n!$ is the number of permutations (orderings) on $n$ objects. This can be seen by considering chairs to be the ranks. Putting person $i$ on chair $j$ is equivalent to giving person i the j th rank. Assume now that we only have $k ≤ n$ chairs. How many seatings are possible (some people may not be given a chair)? Observe that the same algorithm above when stopped at stage $k$ will work. By the multiplication rule, the number of seatings is $n(n − 1). . .(n − k + 1) = \frac{n!}{(n − k)!}$ What happens if $n = k$? (one should be able to retrieve n!, read further) The above quantity is the number of ways of choosing k from n objects if their order is important. To see this, observe that we are effectively choosing k from n people and ranking them (by placing them on chairs). We are about to make the final step for obtaining $n$ choose $k$ and observe their relationship. If all we care about is the set of $k$ people that we choose to be seated, then the above modified algorithm overcounts our possibilities by $k!$. Why? Observe overcount = any permutation of a seating --> results in an equivalent one (because it preserves the set of k people that are seated). But we just learned that the number of permutations on k objects is k!. Therefore, the number of ways of choosing k from n objects is: $\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{P(n,k)}{k!}$ #### Anagrams How many anagrams can we build from a given word?*(not necessarily meaningful)* A quick answer would be as many ways the letters of the word can be permuted. For example, the word MATH has four letters and every permutation of those letters will make an anagram. Therefore, we have 4! = 24 anagrams that we can build from the word MATH. But what if the word was MATHEMATICA, can we apply the same reasoning? We now have 11 letters and hence we have 11! anagrams. As it turns out, this is wrong. The letters now are not unique. The number of anagrams of an n-letter word depends on how many times letters of the word are repeated. For instance, permuting the Ms or the As or the Ts in the word MATHEMATICA will result in the same anagram: M is repeated 2x, A is repeated 3x, and T is repeated 2x. The number of permutations that preserve the anagram is 2!3!2! = 24. Therefore, the 11! permutations overcount the number of anagrams by 24. The number of anagrams that we can build from the word MATHEMATICA is $\frac{11!} {2!3!2!}$ In general, given a n-letter word with $k$ unique letters where letter $i$ appears $n_i$ times, the number of anagrams that we can build from this word will be: $\frac{n!}{\prod_{i=1}^{k}{n_i!}} = \frac {n_i!}{n! n_1! n_2! . . . n_k!}$ - Ordered selection #### Forming teams Given $2n$ players, we would like to pair them up to form $n$ teams of 2. How many configurations of teams are possible? (3 methods) **Method 1**: Imagine placing each player face another(in the same team, total $2n$ people to $n$ teams of 2). This seating can be done in $(2n)!$ ways (a permutation). But does that really represent the number of possible configurations of teams? Permuting teams on the table produces equivalent configurations. $(A,B) = (B,A)$ Therefore, each configuration in the above example is counted exactly $(2!^{n})({n}!)$ times. In general, the $(2n)!$ represent/have overcounting by $2^{n}{n}!$. The number of possible configurations of teams is therefore:$\frac{(2n)!}{2^{n}{n}!}$ **Method 2**: An algorithm to generate teams: First choose any two players from $2n$ to form the first team. Then choose any other two players from remaining $2n−2$ to form the second team, etc... This consists of $n$ stages where in stage $i (i = 1, . . . , n)$ we choose 2 players from $2n−2(i−1)$. By the multiplication rule, the entire activity can be carried out in: $\binom{2n}{2}\binom{2n-2}{2}\binom{2n-4}{2}...\binom{2}{2}$ However, there is overcounting. By permuting the $n$ choices we still obtain an equivalent configuration. Therefore, we are overcounting by $n!$. The number of configurations of teams is therefore: $\frac{\binom{2n}{2}\binom{2n-2}{2}\binom{2n-4}{2}...\binom{2}{2}}{n!}$ **Method 2**: An algorithm to generate teams. add an order restiction: First start with 1 player, pick next short player from $2n-1$ to form the first team. Then choose another player, pick next short player from $2n-3$ to form the second team, etc... This consists of n stages where in stage i (i = 1, . . . , n) we choose 2 players from 2n−2(i−1). By the multiplication rule, the entire activity can be carried out in: $(2n − 1) × (2n − 3) × . . . × 5 × 3 × 1$ However, there is overcounting. By permuting the $n$ choices we still obtain an equivalent configuration. Therefore, we are overcounting by $n!$. The number of configurations of teams is therefore: $\frac{\binom{2n}{2}\binom{2n-2}{2}\binom{2n-4}{2}...\binom{2}{2}}{n!}$ ### n choose k - Unordered choosing By definition: 0! = 1 (the empty product) $\binom{n}{0} = \frac{n!}{0!(n-0)!} =1$ This is essentially saying that there is only one empty subset in a set of size n (clearly!). Similarly, $\binom{n}{n} = \frac{n!}{n!(n-n)!} = \frac{n!}{n!(0!)} = 1$ There is only one subset of size n in a set of size n (clearly!). In general: There are $\binom{n}{k}$ subsets of size k in a set of size n - Given $S = {1,2,...,n}$ to compute the number of subsets it would be: **Addtion rule:** the sum of set size of n choose subsets size k $\binom{n}{0} + \binom{n}{1}+...+\binom{n}{n} = \sum_{k=0}^{n}\binom{n}{k} = 2^n$ S = {1,2,3} $\binom{3}{0} + \binom{3}{1} + \binom{3}{2} + \binom{3}{3} = 8 = 2^3$ **Product rule:** 2 choices: yes or no for each element S = {1,2,3} Subsets: { ${(\emptyset,000)\text{,(1,100),(2,010),(3,001),({1,2},110),({1,3},101),({2,3},011),({123},111)}}$ } $=\text{(does subset have 1)(does subset have 2)(does subset have 3)}$ $=\text{(2)(2)(2)}=2^3=8$ - The binomial theorem and Pascal triangle $(a+b) = \sum_{k=0}^{n}\binom{n}{k}(a)^{n-k}(b)^k$ ### Sets, relations, functions **content to be updated** - Onto functions and one-to-one correspondence (bijection) - Selection with repetition (ordered and non-ordered) - Equivalence relations and partial orders ## Summary **content to be updated** empty sum = 0 $\sum_i^n$ when n ${}^n P_k = {}_{n}P_{k} =P(n,k)=\frac{n!}{(n-k)!}$ | unordered, no repeat, ${n}\geq{k}$ ${}^n C_k = {}_{n}C_{k} = C(n,k)$ $=\binom{n}{k} =\binom{n}{n-k}=\frac{P(n,k)}{n!}=\frac{n!}{n!(n-k)!}$ | | ordered, with repeat $n^k$ | unordered, with repeat $\binom{n-1+k}{k}=\left({n\choose k}\right)=\binom{n-1+k}{n-1}$ | ||| |Functions | Definition| | ------- |-------| | One-to-One |Each x corresponds to different y Similarly, Each y corresponds to different x A function $f: A \to B$ is said to be $\text{one-to-one}$ (or $\text{injective}$) if for any two elements $x_1$ and $x_2$ in the domain $A$, the following property holds: $f(x_1) = f(x_2)\Rightarrow{x_1} = x_2$ or if for any two elements $y_1$ and $y_2$ in the domain $B$, the following property holds: $f(x_1) \neq f(x_2)\Rightarrow{x_1} \neq x_2$| | Onto | A function $f: A \to B$ is said to be $\text{onto}$ (or $\text{surjective}$) if for every element $y$ in the codomain $B$, there exists at least one element $x$ in the domain $A$ such that $f(x) = y$. In other words: $\forall y \in B, \exists x \in A \text{ such that } f(x) = y$ | |Bijection|A function $f: A \to B$ is said to be a $\text{bijection}$ if it is **both one-to-one (injective) and onto (surjective).** In other words: $f(x_1) = f(x_2) \Leftrightarrow x_1 = x_2 \quad \text{and} \quad \forall y \in B, \exists x \in A \text{ such that } f(x) = y$| |||