Combinatorics and probability

- Lectures 25-28.

- Combinations, permutation (with or without repetition)
- Binomial theorem, Pascal identity, Pascal triangle
- Experiment, outcome, sample space, event
- Probability, distribution, uniform distribution

Solve each of the following exercises.

- How many ways are there
- to choose 3 out of 10 students for a committee?
- to choose 3 out of 10 students, provided at least one of them must be first-year, and half of the 10 students are first-year?
- To choose a president, a vice-president and a treasurer from 20 members of CS Society?
- To sit 5 students around a round table?

- (Combinations with repetitions).

Let $x_1+x_2 + \dots +x_n = b$ be an equation over non-negative integers numbers (that is, $b$ and all possible values for variables are natural numbers or 0).- How many different non-negative integer solutions are there for n=5 and b=8?
- How many different solutions that are natural numbers (starting with 1) are there if n=5, b=8?

- (Binomial theorem)
- Find expansion of $(x+y)^5$ using Binomial theorem. What is the coefficient of $xy^4$? Of $x^2y^3$?
- Use Pascal's identity to compute $\binom{6}{2} + \binom{6}{3}$.

- Suppose that pair of dice is biased so that in the first die, probability of 3 appearing is three times the probability of any other number, and in the second die, the probability of both 2 and 4 appearing is twice the probability of any other number (that is, 2 is twice as likely as 1, 3, 5 or 6, and as likely as 4).
- What is the experiment here? What are its outcomes? What is the sample space, and how large is it (assuming dice look different)?
- What are the probabilities of each number from 1 to 6 coming up on the first die? On the second die?
- Suppose both dice are thrown simultaneously. What is the probability of the first die rolling 2 and the second rolling 4?
- What is the probability that sum of the rolls is an even number? Hint: consider different disjoint cases, and take a sum.

For this part of the lab, you will be working in groups of three. Use the deck of cards provided to solve the questions below. There are 4 suits (clubs, diamonds, hearts and spades) of 13 cards each (numbers 1 to 10, counting ace as 1, and face cards king, queen and jack). For the questions below, make sure to write the formulas; you can use a calculator to compute the actual numbers.

- First, each of the 3 of you should randomly select 5 cards from the deck. Now, answer the following questions about your 5 cards, and compare notes with the other two people from your group. Which answers do you expect to be the same, and which different?
- How many permutations of your 5 cards are there? That is, how many ways you can arrange them in a row?
- How many of these permutations have all cards of the same suit next to each other? Write the formula. What is the probability of this happening for your 5 cards?
- How many of these permutations have cards of the same suit in non-decreasing order (counting face cards higher than numbers, and king above queen above jack)? What is the probability of selecting a permutation which has all cards in non-decreasing order out of the 5 cards you have?
- Now, choose 2 out of your 5 cards. How many ways are there to do that?
- What is the probability that the 2 cards you chose have the same colour? The same suit?
- What is the probability that when you select 5 cards at random from the deck, then all of them are the same suit? That exactly 2 of them are face cards? That at least one is a diamond?

- Take another 10 cards each, making sure each of you has cards of all suites and both face cards and number cards. Calculate the probability that when you pick a random card out of these 15 then it is red. Then calculate a probability that if you pick a random card then it is a number. Calculate the probability that you pick a red number.
Finally, calculate conditional probability of picking a red card given that it is a number card (a conditional probability of an event $A$ given that the event $B$ did happen, written as $P(A | B)$, is calculated by a formula $P(A | B) = P(A \cap B) / P(B)$ )

- Play the following game. The player 1 selects several red and several black cards, and gives them to player 2, who puts them face down (so that player 3 does not see which is which). The player 3 selects a face-down card. Then player 2 opens a certain number of cards (of either colour, but not touching the card player 3 selected), leaving at least one red card uncovered. The player 3 can now open one of the remaining cards (either her original choice or one of the others left uncovered). Player 3 wins if her final choice is red.
Play the game 3 times, changing roles. Each time, record the number of red card $r_1$, number of black cards $b_1$ selected by player 1, and numbers $r_2$ and $b_2$ of red and black cards opened by player 2. Calculate the probabilities that player 3's original choice is red, and that her final choice is red. How many times did player 3 win in your game?

- How many permutations of these 6 numbers are there? What is a probability to pick a permutation with odd numbers next to each other? With a substring "12"?
- How many 2-permutations of these numbers are there?
- How many 4-digit numbers can you make if you are only allowed to use these 6 as digits (with repetition, any order)? How many of them have 5 at least once?
- How many ways to select 4 out of these 6 numbers? What is the probability that your selection has at least one odd number?
- What is the probability of picking a number greater than 3 out of {1,2,4,5,6,8} under the condition that the picked number is even?