There are 20 people at a chess club on a certain day. They each find opponents and start playing. How many possibilities are there for how they are matched up, assuming that in each game it does matter who has the white pieces (in a chess game, one player has the white pieces and the other player has the black pieces)?

$\mathbf{20}$ people can be ordered in $\mathbf{20!}$ ways. But we do not care about the order of the $\mathbf{10}$ pairs, so we need to divide by $\mathbf{10!}$ to adjust for overcounting. Since it matters who has the white pieces, the order within those pairs matter. Hence the total number of possibilities is $$\mathbf{\frac{20!}{10!}}.$$


Two chess players, A and B, are going to play 7 games. Each game has three possible outcomes: a win for A (which is a loss for B), a draw (tie), and a loss for A (which is a win for B). A win is worth 1 point, a draw is worth 0.5 points, and a loss is worth 0 points.

  1. How many possible outcomes for the individual games are there, such that overall player A ends up with 3 wins, 2 draws, and 2 losses?

    Out of the $\mathbf{7}$ games player A can win any of the $\mathbf{3}$ games, which gives $\mathbf{\binom{7}{3}}$ possibilities. Similarly out of the remaining $\mathbf{4}$ games player A can draw any of the $\mathbf{2}$ games and player A loses the remaining $\mathbf{2}$ games. So the total number of possible outcomes for the individual games are: $$\mathbf{\binom{7}{3} \binom{4}{2} \binom{2}{2}.}$$

  2. How many possible outcomes for the individual games are there, such that A ends up with 4 points and B ends up with 3 points?

    A ends up with $\mathbf{4}$ points and B with $\mathbf{3}$ points in the following cases:

    1. A wins $\mathbf{4}$ games, draws $\mathbf{0}$ games and loses $\mathbf{3}$ games.
    2. A wins $\mathbf{3}$ games, draws $\mathbf{2}$ games and loses $\mathbf{2}$ games.
    3. A wins $\mathbf{2}$ games, draws $\mathbf{4}$ games and loses $\mathbf{1}$ game.
    4. A wins $\mathbf{1}$ game, draws $\mathbf{6}$ games and loses $\mathbf{0}$ games.
    So the total number of possible outcomes for the individual games such that A ends up with 4 points and B ends up with 3 points is: \begin{align*} \mathbf{\binom{7}{4} \binom{3}{0} \binom{3}{3} + \binom{7}{3} \binom{4}{2} \binom{2}{2}} \\ & \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \mathbf{+ \binom{7}{2} \binom{5}{4} \binom{1}{1} + \binom{7}{1} \binom{6}{6} \binom{0}{0}.} \\ \end{align*}

  3. Now assume that they are playing a best-of-7 match, where the match will end as soon as either player has 4 points. For example, if after 6 games the score is 4 to 2 in favor of A, then A wins the match and they don't play a 7th game. How many possible outcomes for the individual games are there, such that the match lasts for 7 games and A wins by a score of 4 to 3?

    Since the match has to last for $\mathbf{7}$ games, A has to either win or draw the $\mathbf{7th}$ game, otherwise the match would end earlier. First let us consider the case where A $\mathbf{wins}$ the $\mathbf{7th}$ game. So by the end of the first $\mathbf{6}$ games A scores $\mathbf{3}$ points and B scores $\mathbf{3}$ points. The number of ways this happens is as follows:

    1. A wins $\mathbf{3}$ games, draws $\mathbf{0}$ games and loses $\mathbf{3}$ games.
    2. A wins $\mathbf{2}$ games, draws $\mathbf{2}$ games and loses $\mathbf{2}$ games.
    3. A wins $\mathbf{1}$ game, draws $\mathbf{4}$ games and loses $\mathbf{1}$ game.
    4. A wins $\mathbf{0}$ games, draws $\mathbf{6}$ games and loses $\mathbf{0}$ games.
    So the total number of possible outcomes for the individual games such that A ends up with 4 points and B ends up with 3 points with A $\mathbf{winning}$ the $\mathbf{7th}$ game is: \begin{align*} \mathbf{\binom{6}{3} \binom{3}{0} \binom{3}{3} + \binom{6}{2} \binom{4}{2} \binom{2}{2}} \\ & \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \mathbf{+ \binom{6}{1} \binom{5}{4} \binom{1}{1} + \binom{6}{0} \binom{6}{6} \binom{0}{0}.} \\ \end{align*} Now let us consider the case where A $\mathbf{draws}$ the $\mathbf{7th}$ game. This can happen in the following ways:
    1. A wins $\mathbf{3}$ games, draws $\mathbf{1}$ game and loses $\mathbf{2}$ games.
    2. A wins $\mathbf{2}$ games, draws $\mathbf{3}$ games and loses $\mathbf{1}$ game.
    3. A wins $\mathbf{1}$ game, draws $\mathbf{5}$ games and loses $\mathbf{0}$ games.
    So the total number of possible outcomes for the individual games such that A ends up with 4 points and B ends up with 3 points with A $\mathbf{drawing}$ the $\mathbf{7th}$ game is: \begin{align*} \mathbf{\binom{6}{3} \binom{3}{1} \binom{2}{2} + \binom{6}{2} \binom{4}{3} \binom{1}{1} + \binom{6}{1} \binom{5}{5} \binom{0}{0} .} \\ \end{align*} Hence the total number of possible outcomes for the individual games such that A ends up with 4 points and B ends up with 3 points and the match lasts till the $\mathbf{7th}$ game is: \begin{multline} \notag \mathbf{\binom{6}{3} \binom{3}{0} \binom{3}{3} + \binom{6}{2} \binom{4}{2} \binom{2}{2}} \\ \mathbf{+ \binom{6}{1} \binom{5}{4} \binom{1}{1} + \binom{6}{0} \binom{6}{6} \binom{0}{0}} \\ \mathbf{+ \binom{6}{3} \binom{3}{1} \binom{2}{2} + \binom{6}{2} \binom{4}{3} \binom{1}{1} + \binom{6}{1} \binom{5}{5} \binom{0}{0} .} \\ \end{multline}


How many ways are there to split a dozen people into 3 teams, where one team has 2 people, and the other two teams have 5 people each?

First we choose $\mathbf{2}$ people out of the $\mathbf{12}$ to form the $\mathbf{2}$ member team. Then of the remaining $\mathbf{10}$ people we choose $\mathbf{5}$ people to form the first $\mathbf{5}$ member team and the remaining $\mathbf{5}$ people form the second $\mathbf{5}$ member team. This overcounts by a factor of $\mathbf{2}$ since the order of the two $\mathbf{5}$ member teams does not matter. So the number of ways to split a $\mathbf{dozen}$ people into $\mathbf{3}$ teams, where one team has $\mathbf{2}$ people, and the other two teams have $\mathbf{5}$ people each is: $$\mathbf{\frac{\binom{12}{2} \binom{10}{5} \binom{5}{5}}{2}}.$$

How many ways are there to split a dozen people into 3 teams, where each team has 4 people?

Following the same logic as (a), there are $\mathbf{\binom{12}{4} \binom{8}{4} \binom{4}{4}}$ ways of splitting $\mathbf{dozen}$ people into 3 teams, where each team has 4 people. However this overcounts by a factor of $\mathbf{3!}$ since the order of the teams does not matter. So the total number of ways is: $$\mathbf{\frac{\binom{12}{4} \binom{8}{4} \binom{4}{4}}{3!}}.$$


How many paths are there from the point (0, 0) to the point (110, 111) in the plane such that each step either consists of going one unit up or one unit to the right?

To reach point $\mathbf{(110, 111)}$ from $\mathbf{\left(0, 0\right)}$ a total of $\mathbf{221}$ steps must be taken, of which $\mathbf{110}$ steps involve going one unit to the right and the remaining $\mathbf{111}$ involve going one unit up. If a path is encoded by a sequence of U's and R's denoting 'up' and 'right' respectively, to determine the possible paths we just need to specify where the U's are located in the sequence (or where the R's are located). So the number of paths is: $\mathbf{\binom{221}{111}}$ or $\mathbf{\binom{221}{110}}$ both of which evaluate to the same number.

How many paths are there from (0, 0) to (210, 211), where each step consists of going one unit up or one unit to the right, and the path has to go through (110, 111)?

As calculated in (a), there are $\mathbf{\binom{221}{111}}$ paths from $\mathbf{\left(0, 0\right)}$ to $\mathbf{(110, 111)}$. From there, to reach $\mathbf{(210, 211)}$, $\mathbf{100}$ more unit steps should be taken in each direction (up, right). So the total number of paths is: $\mathbf{\binom{221}{111} \cdot \binom{200}{100}}.$


To fulfill the requirements for a certain degree, a student can choose to take any 7 out of a list of 20 courses, with the constraint that at least 1 of the 7 courses must be a statistics course. Suppose that 5 of the 20 courses are statistics courses.

  1. How many choices are there for which 7 courses to take?

    Since the student must take at least one statistics course, she can take anywhere between 1 to 5 statistics courses. So to find the number of ways the student can choose her courses, we consider all the possible ways she can choose 7 courses out of 20 courses and from that subtract the number of possibilities where no statistics courses were chosen. This is given by: $$\mathbf{\binom{20}{7} - \binom{15}{7}.}$$

  2. Explain intuitively why the answer to (a) is not $\mathbf{\binom{5}{1} . \binom{19}{6}.}$

    $\mathbf{\binom{5}{1} . \binom{19}{6}}$ means first we choose any 1 out of the 5 available statistic courses and then we choose from the remaining 19 courses any 6 courses. This is not the same as (a) because this leads to overcounting. Suppose each of the statistics courses are named $\mathbf{S1,S2,\cdots,S5}$ and each of the non-statistics courses are named $\mathbf{NS1,NS2,\cdots,NS15}$. As per (b) we could have a case where we first choose say S1 and then choose S2, S3, NS2, NS5, NS6, NS1 and another case where we choose S3 first and then choose S1, S2, NS2, NS5, NS6, NS1. These two possibilities lead to the same set of courses to be chosen. Hence (b) overcounts the number of possible ways of choosing the courses.



References:

Joseph K. Blitzstein and Jessica Hwang. Introduction to Probability $\textbf{Exercises: Counting}$