Discrete-math 9

1

\begin{matrix} How many even numbers with 6 different digits exist? \\ Solution: \\ 1. Number of numbers without digit 0: \\ 4 options for the last digit and 5 places with 8 digits left: 4 \cdot \frac{8!}{3!} \\ 2. 0 is the last digit: \\ Five places for 9 digits: \frac{9!}{4!} \\ 3. 0 is the second, third, fourth or fifth digit, for each case: \\ Last digit has 4 options \\ Four digits left have 8 options and 4 places \\ ⟹ 4 \cdot 4 \cdot \frac{8!}{4!} \\ The final answer: 4 \cdot \frac{8!}{3!} + \frac{9!}{4!} + 4 \cdot 4 \cdot \frac{8!}{4!} = 68880 \end{matrix}

2

\begin{matrix} How many 7 letter words can you construct using "a, b, c, d" such that \\ letters "a" and "b" appear exactly once \\ Solution: \\ Number of ways to place one "a" and one "b" in a 7 letter word is: 7 \cdot 6 \\ 5 places left will be filled with "c" and "d", so it’s a "without order, with repetition" \\ 2^{5} \\ So the final answer is: \\ 7 \cdot 6 \cdot 2^{5} = 42 \cdot 32 = 1344 \end{matrix}

3

\begin{matrix} What is the sum of all 3 digit numbers that are constructed from digits "7, 5, 3, 1" \\ Each digit can appear more than once \\ Solution: \\ Number of all such numbers is (without order, with repetition): 4^{3} = 64 \\ If we fix any given digit, then the number of options is 4^{2} = 16 \\ ⟹ \begin{matrix} Sum of hundreds is (7 + 5 + 3 + 1) \cdot 16 \cdot 100 = 25600 \\ Sum of tens is (7 + 5 + 3 + 1) \cdot 16 \cdot 10 = 2560 \\ Sum of ones is (7 + 5 + 3 + 1) \cdot 16 \cdot 1 = 256 \end{matrix} \\ ⟹ Sum of all such numbers is: \\ 25600 + 2560 + 256 = 28416 \end{matrix}

4

\begin{matrix} Let A = {1, 2, \dots, 10}, B = {a, b, c, d, e, f} \end{matrix}

4a

\begin{matrix} What is the size of C = {g | g : A \to B} \\ Solution: \\ C = B^{A} ⟹ | C | = | B^{A} | = 6^{10} \end{matrix}

4b

\begin{matrix} What is the size of D = {h | h : B \to A} \\ Solution: \\ D = A^{B} ⟹ | D | = | A^{B} | = 10^{6} \end{matrix}

4c

\begin{matrix} What is the size of E = {g | g : A \to B, g is injective} \\ Solution: \\ | A | > | B | ⟹ Number of injective functions from A to B is zero \end{matrix}

4d

\begin{matrix} \begin{matrix} What is the size of F = {h | h : B \to A, h is injective} \\ Solution: \\ We have 6 sources and 10 images \\ We need to choose exactly 6 different images in order for the function to be injective \\ This is "with order, without repetition" formula which is \frac{n!}{(n - k)!} \\ ⟹ The final answer is \frac{10!}{(10 - 6)!} = \frac{10!}{4!} \end{matrix} \end{matrix}

5

\begin{matrix} Let A be a set of n elements \end{matrix}

5a

\begin{matrix} How many relations there are on A? \\ Solution: \\ | A \times A | = n^{2} \\ Relation is a subset of A \times A \\ Number of relations is a number of ways to choose a subset of A \times A \\ ⟹ Number of relations is equal to | P (A \times A) | = 2^{n^{2}} \end{matrix}

5b

\begin{matrix} How many reflexive relations there are on A? \\ Solution: \\ Reflexive relations are supersets of I d_{A} \\ Number of pairs in I d_{A} is n \\ ⟹ Number of reflexive relations is a number of ways to choose a subset of \\ A \times A ∖ I d_{A} \\ Which is | P (A \times A ∖ I d_{A}) | = 2^{| A \times A ∖ I d_{A} |} = 2^{n^{2} - n} \end{matrix}

5c

\begin{matrix} How many symmetric relations there are on A? \\ Solution: \\ Number of pairs with equal elements is n \\ Number of pairs with different elements is n (n - 1) \\ For each pair with different elements we will automatically choose it’s symmetric one \\ ⟹ Number of symmetric pair choices is \frac{n (n - 1)}{2} \\ ⟹ Number of pairs to choose from is \frac{n (n - 1)}{2} + n = \frac{n (n + 1)}{2} \\ ⟹ Number of symmetric relations on A is 2^{n (n + 1) / 2} \end{matrix}

5d

\begin{matrix} How many total order relations there are on A? \\ Solution: \\ Let R be a total order relation on A \\ Let us construct a "sorted" chain of elements of A \\ For each i \in [1, n] : a_{i} \in A : \\ 1. If chain is empty, place a_{i} anywhere \\ 2. If a_{i} R "the leftmost element of the chain", then place a_{i} to the left e.g. a_{i} < a_{j} < \dots \\ 3. \forall j \in [1, n] : If a_{i} R a_{j} - continue, otherwise place a_{i} to the right of a_{j} \\ e.g. \dots < a_{j} < a_{i} < \dots \\ This will result in a unique "sorted" chain of length n : a_{i} < a_{j} < a_{k} \dots < a_{l} \\ Number of such ordered chains is a "with order, without repetition", which is n! \\ ⟹ Number of total order relations on A is n! \end{matrix}

6

\begin{matrix} 2 classes went to a school trip. With them went 6 mothers and 8 fathers. \end{matrix}

6a

\begin{matrix} How many ways there are to choose 5 parents responsible for food, \\ such that they are 3 mothers and 2 fathers? \\ Solution: \\ We need to choose 3 out of 6 mothers and 2 out of 8 fathers \\ which is (\binom{6}{3}) \cdot (\binom{8}{2}) \end{matrix}

6b

\begin{matrix} How many ways there are to choose 3 parents to be medics? \\ Solution: \\ Choosing 3 different parents from the total of 14 parents is: \frac{14!}{(14 - 3)!} = \frac{14!}{11!} \end{matrix}

6c

\begin{matrix} How many ways there are to choose two groups of 7 parents, \\ such that there is at least one mother in each group? \\ Solution: \\ Number of ways to choose two groups is: (\binom{14}{7}) \\ Number of ways to choose a group that has no mothers is \\ the number of ways to choose 7 out of 8 fathers: (\binom{8}{7}) \\ Groups of parents are different, so we will count this number twice \\ Number of ways to choose two groups such that there is at least one mother is: \\ (\binom{14}{7}) - 2 \cdot (\binom{8}{7}) = (\binom{14}{7}) - 2 \cdot 8 \end{matrix}

7a

\begin{matrix} How many ways there are to sit 2 women and 4 men on a bench, \\ such that 2 women sit next to each other? \\ Solution: \\ Let us count 2 women as one "option" \\ Then we have to choose a sit for each of 5 options: 5! \\ Number of ways to sit 2 women is: 2! \\ So the final answer is: 5! \cdot 2! = 120 \cdot 2 = 240 \end{matrix}

7b

\begin{matrix} How many ways there are to sit 2 women and 4 men on a bench, \\ such that 4 men sit next to each other? \\ Solution: \\ Let us count 4 men as one "option: \\ Then we have to choose a sit for each of 3 options: 3! \\ Number of ways to sit 4 men is: 4! \\ So the final answer is: 3! \cdot 4! = 6 \cdot 24 = 144 \end{matrix}