$K_1$ is the graph with only one vertex. $K_2$ is the graph with two vertices and $1$ edge.

We will show that $R(3,2)=3$.

First we show that $R(3,2)\le 3$. Consider any colouring of $K_3$. If all edges are coloured red then we have a red $K_3$. Otherwise, at least one edge $v_iv_j$ of $K_3$ is coloured blue, in which case $v_iv_j$ is a blue $K_2$.

Next we show that $R(3,2)>2$. Colour the single edge of $K_2$ red. This colouring of $K_2$ does not contain any red triangle (since $K_2$ has only one edge and a triangle has three edges) and does not contain any blue edge, so it does not contain a red $K_3$ or a blue $K_2$.

Therefore $R(3,2)$ is an integer that is stricly greater than $2$ and less than or equal to $3$, so $R(3,2)=3$.

We will show that, for any $s\ge 2$, $R(s,2)=s$.

First we show that $R(s,2)\le s$. Consider any colouring of $K_s$. If all edges are coloured red then we have a red $K_s$. Otherwise, at least one edge $v_iv_j$ of $K_s$ is coloured blue, in which case $v_iv_j$ is a blue $K_2$.

Next we show that $R(s,2)>s-1$. Colour all the edges of $K_{s-1}$ red. This colouring of $K_{s-1}$ does not contain any red $K_s$ (it only has $s-1$ vertices) and does not contain any blue edge, so it does not contain a red $K_s$ or a blue $K_2$.

Therefore $R(s,2)$ is an integer that is stricly greater than $s-1$ and less than or equal to $s$, so $R(s,2)=s$.

Let $n=R(s-1,t)+R(s,t-1)$ so we need to show that $R(s,t)\le n$. In other words, we need to show that any colouring of $K_n$ contains a red $K_s$ or a blue $K_t$.

Consider any colouring of $K_{n}$ and consider the vertex $v_1$ of $K_{n}$. There are $n-1$ edges of $K_{n}$ incident to $v_1$. Let $r$ be the number of these edges coloured red and let $b$ be the number of these edges coloured blue. Then $r+b=n-1$. It must be the case that $r\ge R(s-1,t)$ or $b\ge R(s,t-1)$ since, otherwise, $r\le R(s-1,t)-1$ and $b\le R(s,t-1)-1$, so $r+b \le n-2$. We consider each of these cases separately:

• If $r\ge R(s-1,t)$ then there are vertices $x_1,\ldots,x_{R(s-1,t)}$ such that $v_1x_i$ is a red edge, for each $1\le i\le R(s-1,t)$. By the definition of $R(s-1,t)$, the graph on $x_1,\ldots,x_{R(s-1,t)}$ contains a red $K_{s-1}$ or it contains a blue $K_t$. If it contains a blue $K_t$, then we are done. If it contains a red $K_{s-1}$, we can add $v_1$ to this red $K_{s-1}$ to get a red $K_s$ and we are also done.

• If $b\ge R(s,t-1)$ then there are vertices $x_1,\ldots,x_{R(s,t-1)}$ such that $v_1x_i$ is a blue edge, for each $1\le i\le R(s,t-1)$. By the definition of $R(s,t-1)$, the graph on $x_1,\ldots,x_{R(s,t-1)}$ contains a red $K_{s}$ or it contains a blue $K_{t-1}$. If it contains a red $K_s$, then we are done. If it contains a blue $K_{t-1}$, we can add $v_1$ to this blue $K_{t-1}$ to get a blue $K_t$ and we are also done. ∎

This is an easy application of the Product Rule. Let $x_1,\ldots,x_n$ be the elements of $X$. Define the following procedure: For each $i\in\{1,\ldots,n\}$, choose one of the sets $A$, $B$, or $C$ and add $x_i$ to this chosen set.

This is an $n$-step procedure and at each step $i$ we have $N_i=3$ options. Therefore, the number executions of the procedure is $N_1\times N_2\cdots N_n=3^n$. Clearly we can generate any partition of $X$ using this procedure and for any partition there is only one way to generate it using this procedure. Therefore, there are $3^n$ ways to partition $X$ into three sets $A$, $B$, and $C$.

There are lots of possible answers to this question. Another is to observe that this is the same as asking for the number of functions $f:X\to\{a,b,c\}$. That is, the number of ways of labelling the elements of $X$ with the set to which they should be assigned. In the first class we saw that the number of such functions is $3^n$.

This is very similar to the previous question. For each element $x\in X$, we get to choose if $x$ goes into $A$, or $x$ goes into $B$, or $x$ doesn't go into either set. Again, this gives an $n$ step procedure with $3$ choices at each step, so the answer is $3^n$.

Since $A\cup B\cup C=X$ any procedure we come up with has to make sure that $x$ belongs to at least one of $A$, $B$, or $C$ for each $x\in S$. This means that, for each $x\in S$ we have $7$ options for the sets that contain $x$, where each option corresponds to one of the $7$ non-empty subsets of $\{A,B,C\}$. More specifically, for each $x\in S$, we can have choose any of $\{C\}$, $\{B\}$, $\{B,C\}$, $\{A\}$, $\{A,C\}$, $\{A,B\}$ or $\{A,B,C\}$ and place $x$ into each of the sets we choose. This gives an $n$ step procedure for defining $A$, $B$, and $C$, where each step has $7$ options, so the answer is $7^n$.

This is another easy application of the Product Rule. The obvious procedure for generating such a password has $10$ steps and has $26$ options at each step, the answer is $26^{10}$. (Note that this is exactly like counting the number of functions $f:\{1,\ldots,10\}\to\{\mathtt{a},\mathtt{b},\ldots,\mathtt{z}\}$.)

Again, this is easy to answer using the Product Rule with a $10$-step procedure. The only difference is that, when choosing the $i$th letter in the password, we are not allowed to choose any of the $i-1$ letters that appear before it. In our notation $N_i=26-(i-1)$. Then \[ N_1\times N_2\times\cdots\times N_{10}=26\times25\times\cdots\times 18\times 17=\frac{26!}{16!} \enspace . \] (Note that this is exactly like counting the number of one-to-one functions $f:\{1,\ldots,10\}\to\{\mathtt{a},\mathtt{b},\ldots,\mathtt{z}\}$.)

Again, we use the Product Rule with a $10$-step procedure. In the first step, we have $N_1=26$ options. In every subsequent step, we must choose a letter different from the one chosen in the previous step, we only have $N_i=25$ operations. So the the number of passwords $N_1\times N_2\times\cdots\times N_{10}=26\cdot 25^9$.

The question is asking us to define a one-to-one function from the set $A$ of $n=200$ students onto the set $B=\{d_1,\ldots,d_m\}$ of $m$ desks. We have seen in class that the number of one-to-one functions from a set of size $n$ onto a set of size $m$ is $m!/(m-n)!$, so the answer is $m!/(m-200)!$.

This can be solved with an application of the Product Rule using a $2$-step procedure. In the first step, we choose a one-to-one function that maps the COMP2804 students onto desks. There are $N_1=100!$ ways to do this. In the second step, we choose a one-to-one function that maps the PSYC1000 students onto desks. There are $N_2=100!$ ways to do this. Therefore, there are $N_1\times N_2=100!\times100!$ ways to do this.

This question is a bit trickier than the last, and is closely related to the number of rearrangements of a word (an example we cover in class). First we figure out how many ways there are to assign the COMP2804 students to the first $50$ desks, with $2$ students per desk. We do this with a $50$-step procedure. In the first step, we choose two of the $100$ students to assign to desk $d_1$. In the $i$th step we choose two of the $100-2(i-1)$ students that have not yet been assigned desks to place at desk $d_i$. Then, the number of ways to perform Step~$i$ is $\binom{100-2(i-1)}{2}$, so the total number of ways to assign the COMP2804 students to desks $d_1,\ldots,d_{50}$ with two students per desk is \[ \binom{100}{2}\binom{98}{2}\binom{96}{2}\cdots\binom{2}{2} = \frac{100\cdot99}{2!}\cdot\frac{98\cdot 97}{2!}\cdot\frac{96\cdot 95}{2!}\cdot\cdots\cdot \frac{2\cdot 1}{2!}=
\frac{100!}{2^{50}} \]

Next we have to assign the $100$ PSYC1000 students to the last fifty desks $d_{51},\ldots,d_{100}$. This is exactly the same as the number of ways of assigning the $100$ COMP2804 students to the first fifty desks, so this is also $100!/2^{50}$.

Thus, we have a $2$-step procedure with $N_1=100!/2^{50}$ ways to do the first step and $N_2=100!/2^{50}$ ways to do the second step, so the total number of ways to assign students to desks is $N_1\times N_2=(100!)^2/2^{100}$.

For this, we will use the Complement Rule to first count solutions in which at least one of the tables is empty. The number of ways of assigning students so that they all sit at one table (leaving two tables empty) is $3$; you just choose the table. The number of ways of assigning students so that exactly one table is empty can be computed using the Product Rule. First choose one of the $3$ tables that will be empty. There are $3$ ways to do this. Next, assign the students to the other two tables so that neither of those is empty. The number of ways to do this is $2^n-2$ since, of the $2^n$ possible assignments of students to tables, the two assignments that have all students sitting at a single table are not allowed. Therefore, the number of assignments in which at least one table is empty is \[ 3 + 3\times (2^n-2) = 3\times 2^{n} - 3 \] Now we use the Complement Rule. The number of ways to assign students to tables without any restrictions is $3^n$. Therefore, the number of ways to assign students to tables in such a way that no table is empty is $3^n - (3\times 2^{n} - 3) = 3^n - 3\times 2^n + 3$.

Let $f:S_n\to S_n$ be the function that flips the first bit of its input string, so $f(\langle b_1,b_2,b_3,\ldots,b_n\rangle)=\langle (1-b_1),b_2,b_3,\ldots,b_n\rangle$. Notice that $f$ is the inverse of itself, so $f(f(\langle b_1,\ldots,b_n\rangle ))=\langle b_1,\ldots,b_n\rangle $. Note also that, if the number of $1$ bits in $\langle b_1,\ldots,b_n\rangle $ is even then the number of $1$-bits in $f(\langle b_1,\ldots,b_n\rangle )$ is odd. Therefore, we can also view $f$ as a function from $S^0_n$ to $S^1_n$ and the fact that $f$ is a self-inverse implies that this function is a bijection. There there exists a bijection $f:S^0_n\to S^1_n$ so, by the Bijection Rule $|S^0_n|=|S^1_n|$.

Notice that the sets $S^0_n$ and $S^1_n$ are disjoint and $S_n=S^0_n\cup S^1_n$ so, by the Sum Rule \[ |S_n|=|S^0_n\cup S^1_n|=|S^0_n|+|S^1_n|=2|S^0_n| \enspace . \] Dividing the left and right hand sides by $2$ gives $|S^0_n|=\tfrac{1}{2}|S_n|=\tfrac{1}{2}\cdot 2^n = 2^{n-1}$.

This is similar to the previous question: Let $f:T_n\to T_n$ be the function that adds $1$ (mod $3$) to the first trit in its input. More precisely, \[
f(\langle t_1,t_2,t_3,\ldots,t_n\rangle)=\langle (t_1+1)\bmod 3,t_2,t_3,\ldots,t_n\rangle \enspace . \] Then $f$ is a bijection from $T_n^0$ to $T_n^1$, so $|T_n^0|=|T_n^1|$. Also, $f$ is a bijection from $T_n^1$ onto $T_n^2$, so $|T_n^1|=|T_n^2|$. Therefore $|T_n^0|=|T_n^1|=|T_n^2|$. By the Sum Rule, $|T_n^0|+|T_n^1|+|T_n^2|=|T_n|$. Combining these equations shows that $3|T^i_n|=T_n$, for each $i\in\{0,1,2\}$ and dividing both sides of this equation by $3$ answers the question.

This an application of the Product Rule using binomial coefficients. Here's the procedure:

1. Choose $75$ of the chairs and paint them red. There are $\binom{200}{75}$ ways to do this.
2. Choose $25$ of the remaining $125$ unpainted chairs and colour them green. There are $\binom{125}{25}$ ways to do this.
3. Paint the remaining $100$ chairs blue. There only one way to do this.

So, by the Product Rule, there are $\binom{200}{75}\cdot\binom{125}{25}$ ways to paint the chairs so that we have $75$ red, $25$ green, and $100$ blue chairs.

If you use the Produce Rule in other ways, you may get different-looking answers like $\binom{200}{100}\cdot\binom{100}{25}$ or $\binom{200}{25}\cdot\binom{175}{100}$.

In a board with $9$ marked cells, all cells are marked. Such a board is completely defined by the choice of the $\lceil 9/2\rceil=5$ cells that contain X. Therefore there $\binom{9}{5}$ tic-tac-toe boards with $9$ marked cells.

In a board with $5$ marked cells, $\lceil 5/2\rceil=3$ of the marked cells contain X and the remaining $2$ marked cells contain O. We can define such a board with a $2$-step procedure:

1. Choose $3$ cells that will contain X. There are $\binom{9}{3}$ ways to do this.

2. From the remaining $6$ unmarked cells, choose $2$ cells that will contain O. There are $\binom{6}{2}$ ways to do this.

Therefore, the number of number of tic-tac-toe boards with $5$ marked cells is $\binom{9}{3}\cdot\binom{6}{2}$.

Note that this is more than the number of tic-tac-toe boards with $9$ marked cells. Isn't that interesting?

We can construct an ordered partition using a $7$-step procedure, where step $i$ involves choosing the $3$ elements in $P_i$ from the $(21-3(i-1))$-element set $S\setminus(P_1\cup\cdots\cup P_{i-1})$, for each $i\in\{1,ldots,7\}$. Then the number of ways to perform step $i$ is $N_i\binom{21-3(i-1)}{3}$. Therefore, the number of ordered partitions is \begin{align*} \prod_{i=1}^7 \binom{21-3(i-1)}{3} & = \binom{21}{3} \binom{18}{3} \binom{15}{3} \binom{12}{3} \binom{9}{3} \binom{6}{3} \binom{3}{3} \\ & = \frac{21\cdot 20\cdot 19}{3!} \frac{18\cdot 17\cdot 16}{3!} \frac{15\cdot 14\cdot 13}{3!} \frac{12\cdot 11\cdot 10}{3!} \frac{9\cdot 8\cdot 7}{3!} \frac{6\cdot 5\cdot 4}{3!} \frac{3\cdot 2\cdot 1}{3} \\ & = \frac{21!}{(3!)^7} = \frac{21!}{6^7} \enspace . \end{align*}

Define $q$ to be the number of unordered partitions. Let us count the number of ordered partitions using the Product Rule with $2$-step procedure.
1. Choose an unordered partition $\mathcal{P}$. By definition, there are $N_1=q$ ways to do this. Then $\mathcal{P}$ is a $7$-element set.
2. Choose a permutation $P_1,\ldots,P_7$ of $\mathcal{P}$, which gives us an ordered partition. There are $N_2=7!$ ways to do this.

Therefore, the number of ordered partitions is $N_1\cdot N_2=q\cdot 7!$. But in the previous question, we showed that the number of ordered partitions is $\frac{21!}{6^7}$. Therefore, $q\cdot 7! = \frac{21!}{6^7}$ and dividing both sides by $7!$ gives $q=\frac{21!}{6^7\cdot 7!}$, which is what we are trying to prove.

The hint (and Pascal's Triangle/Identity) suggests that most of the coefficients $\binom{n}{k}$ that we are looking for will appear disguised as $\binom{n-1}{k}+\binom{n-1}{k-1}$. In particular, we'll try to find $\binom{n}{1},\binom{n}{2},\ldots,\binom{n}{n-1}$ this way. We'll find $\binom{n}{0}$ and $\binom{n}{n}$ separately. Continuing from the last equation above, \begin{align*} & = \color{red}{\sum_{k=0}^{n-1}\binom{n-1}{k}x^{n-k}y^k} + \color{blue}{\sum_{k=0}^{n-1}\binom{n-1}{k}x^{n-1-k}y^{k+1}} \\ & = \color{red}{\sum_{k=0}^{n-1}\binom{n-1}{k}x^{n-k}y^k} + \color{blue}{\sum_{k=1}^{n}\binom{n-1}{k-1}x^{n-k}y^{k}} \\ & = \color{red}{\binom{n-1}{0}x^n+\sum_{k=1}^{n-1}\binom{n-1}{k}x^{n-k}y^k} + \color{blue}{\sum_{k=1}^{n}\binom{n-1}{k-1}x^{n-k}y^{k}} & \text{(we found $\binom{n}{0}=\binom{n-1}{0}=1$)} \\ & = \color{red}{\binom{n-1}{0}x^n+\sum_{k=1}^{n-1}\binom{n-1}{k}x^{n-k}y^k} + \color{blue}{\sum_{k=1}^{n-1}\binom{n-1}{k-1}x^{n-k}y^{k} + \binom{n-1}{n-1}y^{n}} & \text{(we found $\binom{n}{n}=\binom{n-1}{n-1}=1$)}\\ & = \color{red}{\binom{n}{0}x^n+\sum_{k=1}^{n-1}\binom{n-1}{k}x^{n-k}y^k} + \color{blue}{\sum_{k=1}^{n-1}\binom{n-1}{k-1}x^{n-k}y^{k} + \binom{n}{n}y^{n}} \\ & = \color{red}{\binom{n}{0}x^n}+\sum_{k=1}^{n-1}\left(\color{red}{\binom{n-1}{k}} + \color{blue}{\binom{n-1}{k-1}}\right)\color{purple}{x^{n-k}y^{k}} + \color{blue}{\binom{n}{n}y^{n}} & \text{(combine both sums)}\\ & = \color{red}{\binom{n}{0}x^n}+\color{purple}{\sum_{k=1}^{n-1}\binom{n}{k}x^{n-k}y^{k}} + \color{blue}{\binom{n}{n}y^{n}} & \text{(Pascal's Identity: $\color{purple}{\binom{n}{k}}=\color{red}{\binom{n-1}{k}}+\color{blue}{\binom{n-1}{k-1}}$)} \\ & = \color{purple}{\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^{k}} \enspace . \end{align*}

The letter frequencies in this word are $4\times\mathrm{E}$, $2\times\mathrm{L}$, $2\times\mathrm{C}$, $1\times\mathrm{T}$, $2\times\mathrm{R}$, $2\times\mathrm{O}$, $1\times\mathrm{N}$, $2\times\mathrm{P}$, $2\times\mathrm{H}$, $2\times\mathrm{A}$, $1\times\mathrm{G}$, $1\times\mathrm{S}$.
We can create a rearrangement by a procedure that starts with $22$ blank spaces, chooses $4$ of them for the letter $E$, then chooses $2$ of the remaining $18$ for the letter L, and so on. Proceeding this way, we get the answer: \[ \binom{22}{4} \binom{18}{2} \binom{16}{2} \binom{14}{1} \binom{13}{2} \binom{11}{2} \binom{9}{1} \binom{8}{2} \binom{6}{2} \binom{4}{2} \binom{2}{1} \binom{1}{1} \enspace . \] If you were paying attention in class, I mentioned that there is something called the multinomial formula that lets you read off the answer directly from the length of the word and the letter frequencies. Using this we get the (equivalent) answer: \[ \frac{22!}{(4!)(2!)^7} \enspace . \]

We saw a Theorem in class that answers this (Theorem 3.9.2) in the textbook. Applying this theorem with $n=112$ and $k=5$, we get the answer \[ \binom{n+k-1}{k-1}=\binom{112+5-1}{5-1}=\binom{116}{4} \enspace . \]

The condition $x_1\ge 10$ requires that we do some rewriting. Let $y_1=x_1-10$ and consider the equation $y_1+x_2+x_3+x_4+x_5=102$. For any non-negative integer solution to this equation, we can set $x_1\gets y_1+10$ to obtain a solution to the original equation in which $x_1\ge 10$. In the other direction, for any non-negative integer solution $x_1,x_2,\ldots,x_5$ to the original equation with $x_1\ge 10$, we can set $y_1\gets x_1-10$ to get a non-negative integer solution to $y_1+x_2+x_3+x_4+x_5=102$. Therefore, there is a bijection between non-negative integer solutions to $y_1+x_2+x_3+x_4+x_5=102$ and non-negative integer solutions to $x_1+x_2+x_3+x_4+x_5=112$ with the extra condition $x_1\ge 10$. Now, applying Theorem 3.9.1 with $n=102$ and $k=5$ we get the answer \[ \binom{n+k-1}{k-1}=\binom{102+5-1}{5-1}=\binom{106}{4} \enspace . \]

In class, we saw a theorem (Theorem 3.9.2 in the textbook) that considers exactly this problem. Applying Theorem 3.9.2 with $n=112$ and $k=5$ gives the answer \[ \binom{n+k}{k}=\binom{112+5}{5}=\binom{117}{5} \enspace . \]

The thing we will count is the number of non-negative integer solutions to the inequality \[ x_1+x_2+\cdots+x_k \le n \] Let $S$ be the set of all solutions to this inequality. By Theorem 3.9.2, \[ |S| = \binom{n+k}{k} \] We can also compute $|S|$ using the Sum Rule. For each $r\in\{0,\ldots,n\}$, let $S_r$ be the set of all non-negative integer solutions to $x_1+x_2+\cdots+x_k=r$. Then, by Theorem 3.9.1, $|S_r|=\binom{r+k-1}{k-1}$. Notice that the sets $S_0,\ldots,S_n$ are pairwise disjoint and $S=\bigcup_{r=0}^n S_r$. Therefore, by the Sum Rule, \[ |S| = \sum_{r=0}^n |S_r| = \sum_{r=0}^n \binom{r+k-1}{k-1} \enspace. \] Putting these two solutions together we get the identity \[ \binom{n+k}{k} = |S| = \sum_{r=0}^n \binom{r+k-1}{k-1} \]