Mathematical Thinking Quiz 2: 3 December 2023 (September 2023 term)

Section I (20 Marks)

1. Find the number of bijective functions from the set $\{1, 2, 3, 4\}$ to itself. [4 marks]

2. Which of the following option(s) is (are) true? [4 marks]

(a) There are infinitely many primes of the form $2n + 1$, where $n \in \mathbb{N}$.
(b) There are infinitely many primes of the form $6n + 3$, where $n \in \mathbb{N}$.
(c) There are infinitely many primes of the form $4n + 1$, where $n \in \mathbb{N}$.
(d) There are infinitely many primes of the form $10n + 5$, where $n \in \mathbb{N}$.

1. Which of the following option(s) is (are) true? [4 marks]

[Hint: use the binomial theorem]

(a) $\displaystyle\sum_{i=0}^{n}(-1)^i\binom{n}{i} = 0$ for all $i, n \in \mathbb{N}$
(b) $\displaystyle\sum_{i=0}^{n}\binom{n}{i} = 2^n$ for all $i, n \in \mathbb{N}$.
(c) $\displaystyle\sum_{i=0}^{n}2^i\binom{n}{i} = 4^n$ for all $i, n \in \mathbb{N}$.
(d) $\displaystyle\sum_{i=0}^{n}(-1)^i2^i\binom{n}{i} = (-1)^n$ for all $i, n \in \mathbb{N}$.

1. How many inversions does the permutation 4321 (with one-line notation) have? [4 marks]

2. Suppose a tree $T$ has $n$ vertices of degree one, 2 vertices of degree two, 2 vertices of degree three, and 1 vertex of degree 5. Find the value of $n$. [4 marks]