MUN Computer Science 1002 - Lab 9

Combinatorics and probability

Review:

Vocabulary

 

Individual work

Solve each of the following exercises.

  1. How many ways are there
    1. to choose 3 out of 10 students for a committee?
    2. 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?
    3. To choose a president, a vice-president and a treasurer from 20 members of CS Society?
    4. To sit 5 students around a round table?
  2. (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).
    1. How many different non-negative integer solutions are there for n=5 and b=8?
    2. How many different solutions that are natural numbers (starting with 1) are there if n=5, b=8?
  3. (Binomial theorem)
    1. Find expansion of $(x+y)^5$ using Binomial theorem. What is the coefficient of $xy^4$? Of $x^2y^3$?
    2. Use Pascal's identity to compute $\binom{6}{2} + \binom{6}{3}$.
  4. 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).
    1. What is the experiment here? What are its outcomes? What is the sample space, and how large is it (assuming dice look different)?
    2. What are the probabilities of each number from 1 to 6 coming up on the first die? On the second die?
    3. Suppose both dice are thrown simultaneously. What is the probability of the first die rolling 2 and the second rolling 4?
    4. What is the probability that sum of the rolls is an even number? Hint: consider different disjoint cases, and take a sum.

Group exercises

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.

  1. 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?
    1. How many permutations of your 5 cards are there? That is, how many ways you can arrange them in a row?
    2. 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?
    3. 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?
    4. Now, choose 2 out of your 5 cards. How many ways are there to do that?
    5. What is the probability that the 2 cards you chose have the same colour? The same suit?
    6. 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?

  2. 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)$ )

  3. 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?

Review after the group exercises

Consider sequences of numbers out of 1,2,4,5,6,8.
  1. 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"?
  2. How many 2-permutations of these numbers are there?
  3. 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?
  4. How many ways to select 4 out of these 6 numbers? What is the probability that your selection has at least one odd number?
  5. 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?