Math 116: Midterm Study Guide (Part III)

3.3 The Binomial Theorem and Pascal’s Triangle

Exercise 1 What is the coefficient of the term $t^5$ of $(1+t)^7$ ?

By the Binomial Theorem, we have:

$\begin{align*} (1+t)^7=\sum_{k=0}^7 \binom{7}{k}t^{k} \end{align*}$

Therefore, the coefficient is $\binom{7}{5}$ .

Exercise 2 What is the coefficient of the term $x^6y^3$ of $(x+y)^9$ ?

By the Binomial Theorem, we have:

$\begin{align*} (x+y)^9=\sum_{k=0}^9 \binom{9}{k}x^ky^{9-k} \end{align*}$

Therefore, the coefficient is $\binom{9}{6}$ .

Exercise 3 What is the coefficient of the term $x^2y^3z^4$ of $(x+y+z)^{10}$ ?

By the Multinomial Theorem, we have:

$\begin{align*} (x+y+z)^{10}=\sum_{i+j+k=10} \frac{10!}{i!j!k!}x^iy^jz^k \end{align*}$

Therefore, the coefficient is $\frac{10!}{2!3!4!}$ .

Exercise 4 Use the binomial theorem to compute $5^6$ (you don’t have to simplify, just write it out).

By the Binomial Theorem, we have:

$\begin{align*} 5^6&= (1+4)^6=\sum_{k=0}^6 \binom{6}{k}4^k \end{align*}$

Exercise 5 Let $X=\{0,1,2,3,4,5,6,7,8,9\}$ .

(a) How many subsets are there of size $4$ ?

There are $\binom{10}{4}$ subsets of size $4$ .

(b) How many subsets are there of size divisible by $5$ ?

There are $\binom{10}{0} + \binom{10}{5} + \binom{10}{10}$ subsets of size divisible by $5$ .

(c) How many subsets are there of size divisible by $2$ ?

There are $\binom{10}{0}+\binom{10}{2}+\binom{10}{4}+\binom{10}{6}+\binom{10}{8}+\binom{10}{10}$ subsets of size divisible by $2$ .

3.4 Congruences of binomial coefficients

Exercise 1 Reduce $\binom{11}{6}$ modulo $3$ .

Note that

$\begin{align*} 11&= 1\cdot 3^2 + 0\cdot 3^1 + 2\cdot 3^0 \\ 6 &=0\cdot 3^2 + 2\cdot 3^1 + 0\cdot 3^0 \end{align*}$

Thus,

$\begin{align*} \binom{11}{6} &\equiv \binom{1}{0}\binom{0}{2}\binom{2}{0} \mod{3} \\ &\equiv1\cdot 0 \cdot 1 \mod{3} \\ &\equiv 0 \mod{3} \end{align*}$

Exercise 2 Use Lucas’s Theorem to determine if $5 \mid \binom{17}{5}$ .

Note that

$\begin{align*} 17 &= 3\cdot5^1 + 2 \cdot 5^0 \\ 5 &= 1 \cdot 5^1 + 0 \cdot 5^0 \end{align*}$

Thus,

$\begin{align*} \binom{17}{5} &\equiv \binom{3}{1}\binom{2}{0} \mod{5} \\ &\equiv 3 \cdot 1 \mod{5} \\ &= 3 \mod{5} \end{align*}$

Therefore, $5\nmid \binom{17}{5}$ .

3.5 Permutations

Exercise 1 Let

$\sigma=\begin{pmatrix} 1& 2 & 3 & 4 & 5 & 6 \\ 2 & 1 & 4 & 5 & 6 & 3 \end{pmatrix}$

(a) Compute $\sigma(1)$ , $\sigma(2)$ , $\sigma(3)$ , $\sigma(4)$ , $\sigma(5)$ , and $\sigma(6)$ .

$\begin{align*} \sigma(1)&= 2 & \sigma(2) &= 1 & \sigma(3) &=4 \\ \sigma(4)&= 5 & \sigma(5) &= 6 & \sigma(6) &=3 \end{align*}$

(b) Compute $\sigma \circ \sigma (1)$ , $\sigma \circ \sigma (2)$ , $\sigma \circ \sigma (3)$ .

$\begin{align*} (\sigma\circ \sigma)(1)&= 1 & (\sigma\circ \sigma)(2) &= 2 & (\sigma\circ \sigma)(3) &=5 \end{align*}$

(c) Find a formula for $\sigma^k(1)$ where $\sigma^k$ means apply $\sigma$ $k$ times.

$\begin{align*} \sigma^k(1)&=1 & \text{ if } k \text{ is even} \\ \sigma^k(1)&=2 & \text{ if } k \text{ is odd} \end{align*}$

(d) Find a formula for $\sigma^k(3)$ where $\sigma^k$ means apply $\sigma$ $k$ times.

$\begin{align*} \sigma^k(3)&=3 & \text{ if } k \equiv 0\mod{4} \\ \sigma^k(3)&=4 & \text{ if } k \equiv 1\mod{4} \\ \sigma^k(3)&=5 & \text{ if } k \equiv 2\mod{4} \\ \sigma^k(3)&=6 & \text{ if } k \equiv 3\mod{4} \end{align*}$

Exercise 2 Rewrite the following permutations in one-line notation:

(a) $\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{pmatrix}$

$(1\;2\;3\;4)$

(b) $\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 1 & 5 & 2 \end{pmatrix}$

$(1\;3)(2\;4\;5)$

(c) $\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 3 & 2 & 1 \end{pmatrix}$

$(1\;5)(2\;4)$

(d) $\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 1 & 4 & 3 & 6 & 5 \end{pmatrix}$

$(1\;2)(3\;4)(5\;6)$

Exercise 3 Rewrite the following permutations in two-line notation (assume each permutation is an element of $S_5$ :

(a) $(1\;2\;4\;5\;3)$

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \end{pmatrix}$

(b) $(1\;2)(4\;5)$

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 3 & 5 & 4 \end{pmatrix}$

(c) $(1\;2)(1\;3)$

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 2 & 4 & 5 \end{pmatrix}$

(d) $(1\;3\;4)(2\;3)$

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 2 & 1 & 5 \end{pmatrix}$

Exercise 4 How many transpositions (permutations which switch exactly two elements) are there in $S_4$ ?

Any transposition can be given in the form $(i\;j)$ and $(i\;j)=(j\;i)$ , i.e. choosing a transposition is equivalent to choosing two elements from a set of four objects in which order does not matter. Therefore, there are $\frac{4\cdot 3}{2!}$ transpositions.

Exercise 5 How many cycles are there in $S_5$ ?

Any cycle is of the form $(i_1\;i_2\;i_3\;i_4\;i_5)$ . Shifting any cycle by one does not change the permutation, i.e. $(i_1\;i_2\;i_3\;i_4\;i_5)=(i_5\;i_1\;i_2\;i_3\;i_4)$ . Thus, there are a total of five representations of the same cycle. Therefore, there are $\frac{5!}{5}=4!$ cycles in $S_5$ .

Exercise 6 Show that there exists a bijection between edges on a graph with $n$ vertices and the transpositions in $S_n$ .

Label the vertices of the graph by $1,2,3,4,\dots, n$ . For each transposition $(i\;j)$ in $S_n$ , send it to the edge connected the vertex $i$ and $j$ . Note that $(i\;j)=(j\;i)$ and the edge connecting $i$ to $j$ is the same as the edge connecting $j$ to $i$ . Therefore, this defines a bijection between transpositions and edges of the graph.

3.7 Selections

Exercise 1 Let $X=\{a,b,c,d\}$ and consider how many ways to create a string of $3$ -letters.

(a) How many possible strings are there if repetition is allowed and order matters?

There are $4^3$ possible strings.

(b) How many possible strings are there if repetition is not allowed and order matters?

There are $\frac{4!}{1!}$ possible strings.

(c) How many possible strings are there if repetition is allowed and order does not matter?

There are $\binom{4+3-1}{3}$ possible strings.

(d) How many possible strings are there if repetition is not allowed and order does not matter?

There are $\binom{4}{3}$ possible strings.

Exercise 2 Suppose an urn contains five balls with different colors: aqua, burgundy, crimson, dandelion, eggshell. How many ways can we select three balls if:

(a) Balls are returned to the urn after each choice and order matters.

There are $5^3$ possible selections.

(b) Balls are returned to the urn after each choice and order does not matter.

There are $\binom{5+3-1}{3}$ possible selections.

(c) Balls are not returned to the urn after each choice and order matters.

There are $\frac{5!}{2!}$ possible selections.

(d) Balls are not returned to the urn after each choice and order does not matter.

There are $\binom{5}{3}$ possible selections.

Exercise 3 How many solutions are there to the following equation:

$x_1+x_2+x_3=5$

if each $x_i$ is a non-negative integer.

There are $\binom{3+5-1}{5}$ possible solutions.

3.8 Equivalence and order

Exercise 1 Let $X=\{a,b,c,d\}$ , determine if the following relations are: (1) reflexive, (2) symmetric, (3) transitive, (4) irreflexive, or (5) antisymmetric.

(a) Let $R=\{(a,b),(b,b),(b,c),(c,d)\}$ .

Rendered by QuickLaTeX.com

Antisymmetric.
Reflexivity fails from $(c,c) \not \in R$ .
Symmetry fails from $(a,b)\in R$ , but $(b,a)\not\in R$ .
Transitive fails from $(a,b)\in R$ , $(b,c) \in R$ , but $(a,c)\not\in R$ .
Irreflexivity fails from $(b,b)\in R$ .

(b) Let $R=\{(a,b),(b,a),(b,b),(b,c),(c,b)\}$ .

Rendered by QuickLaTeX.com

Symmetric.
Reflexivity fails form $(a,a)\not\in R$ .
Antisymmetry fails from $(a,b)\in R$ and $(b,a)\in R$ .
Transitivity fails from $(a,b)\in R$ and $(b,c) \in R$ , but $(a,c)\not\in R$ .
Irreflexivity fails from $(b,b) \in R$ .

Malachi Alexander

UCSC Graduate Student

Math 116: Midterm Study Guide (Part III)