{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "###
San Jose State University
Department of Applied Data Science
\n", "#
DATA 220
Mathematical Methods for Data Analysis
\n", "###
Spring 2021
Instructor: Ron Mak
\n", "#
Assignment #4
Combinatorics and Probability Problem Set
\n", "####
100 points total
(10 points each, except PROBLEM 9 is 20 points)

Work together with your lab partner.
Write your solutions in one or more cells after each problem.
You can compute by hand, but try use Python code and Python functions.
You can add your own functions or other support code.
Explain your code with comments and print intermediate values from your calculations.
\n", "####
Due February 25, 2021 at 5:30 PM
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### PROBLEM 1. You stand on a street corner and record the gender of the first ten people who pass by. If the city is half male and half female, what is the probability that you will record all females?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The probability of a female is 0.5, order matters, and repetitions of gender are allowed, so the probabability of ten females is 0.5^10." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "people_count = 10\n", "p_female = 0.5\n", "female_count = 10\n", "\n", "p = p_female**female_count\n", "\n", "print(f'The probability of a person being female = {p_female}')\n", "print(f'The probability of {female_count} females ' +\n", " f'after {people_count} people passed by = {p:.7f}')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "#### PROBLEM 2. What is the probability that a randomly selected leap year contains 53 Sundays?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Since a non-leap year has 52 weeks, it must have 52 Sundays. A leap year with 366 days has 366 - 7*52 = 2 extra days. How many possible pairs of consecutive days are there? How many of those pairs include a Sunday? We can solve this using the following Python code." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "first_day = ['Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday']\n", "second_day = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday']\n", "\n", "# Make a list of pairs of consecutive days.\n", "pairs = zip(first_day, second_day)\n", "pairs_count = len(first_day)\n", "\n", "print(f'{pairs_count} possible pairs of consecutive days:')\n", "print()\n", "\n", "# Count how many pairs contain a Sunday.\n", "sunday_count = 0;\n", "for pair in pairs:\n", " print(pair, end='')\n", " \n", " if 'Sunday' in pair:\n", " sunday_count += 1\n", " print(' contains Sunday!', end='')\n", "\n", " print()\n", " \n", "print()\n", "print(f'{sunday_count} pairs include a Sunday')\n", "\n", "p = sunday_count/pairs_count # probability of the 53rd Sunday\n", "\n", "print(f'Probability of including a Sunday = {p:.4f}')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "#### PROBLEM 3. A group of ten friends randomly sit around a circular table. Two of them, Romeo and Juliette, love each other dearly. What is the probability that they end up sitting together?" ] }, { "cell_type": "raw", "metadata": {}, "source": [ "We need to know how many unique ways (permulations) there are for n friends to sit in a circle. If they were sitting in a line, it would be n!. But if they sit in a circle, then for each seating order, we can rotate the friends around the table clockwise or counterclockwise by one person n times, but each time, they would still be seated in the same order. So the number of circular permutations is n!/n, or (n - 1)!. \n", "\n", "Romeo and Juliette can sit together two unique ways, either Romeo to Juliette's left, or vice versa. For each of those two ways, the remaining friends can sit 8! ways around the table. So the probability that Romeo and Juliette will sit together is [2 X 8!]/9!." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import math\n", "\n", "friends_count = 10\n", "lovers_count = 2\n", "lovers_ways = 2\n", "total_unique_circular_arrangements = math.factorial(friends_count - 1)\n", "remaining_friends_ways = math.factorial(friends_count - lovers_count)\n", "\n", "print(f' Total unique circular arrangements = {total_unique_circular_arrangements:,d}')\n", "print(f'Unique ways lovers can sit together = {lovers_ways:,d}')\n", "print(f'Total remaining friends ways to sit = {remaining_friends_ways:,d}')\n", "\n", "p = lovers_ways*remaining_friends_ways/total_unique_circular_arrangements\n", "\n", "print()\n", "print(f'Probability that the lovers will sit together = {p:.4f}')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "#### PROBLEM 4. How many sums of money can you obtain by choosing two coins from a box that contains a penny, a nickel, a dime, a quarter, and a half dollar?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The problem asks for the number of sums, not the unique amounts. It doesn't matter what order you add the coins, and since there is only one of each coin in the box, there are no repetitions. There are 5 coins and we choose 2. Use the scipy.special.binom function to compute the value of the binomial coefficient." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import scipy.special as special\n", "\n", "coin_count = 5\n", "choose_count = 2\n", "\n", "# Order doesn't matter, no repetitions.\n", "ways = int(special.binom(coin_count, choose_count))\n", "\n", "print(f'Ways to choose {choose_count} coins from {coin_count} coins = {ways}')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "#### PROBLEM 5. You have three empty boxes and seven balls. How many ways can you distribute the balls among the three boxes so that each box contains at least one ball?" ] }, { "cell_type": "raw", "metadata": {}, "source": [ "Label the boxes arbitrarily 1, 2, and 3, and let x1, x2, and x3 represent the number of balls put into the boxes. Then x1 + x2 + x3 = 7 with the added restrictions that each xi > 0.\n", "\n", "We can show the problem pictorially with 7 stars and 2 bars, where each star is a ball and the bars separate the stars into 3 groups. For example, the arrangement **|*|**** represents x1 = 2, x2 = 1, and x3 = 4. Ignoring the restrictions for now, how many ways can we arrange 7 stars among the 9 stars and bars? Let n = 7 balls and k = 3 boxes, and the formula to use is (n + k - 1) choose n.\n", "\n", "Now we count the bad arrangements which violate the restrictions. When an arrangement starts and ends with a bar, it represents x1 = 0 and x3 = 0 (-1 for a bad arrangement). There are 7 other ways for an arrangement to start with a bar (-7) representing only x1 = 0, and another 7 ways for an arrangement to end with a bar (-7) representing only x3 = 0. Finally, there are 6 ways for there to be two bars together internally in an arragement, such as ***||****, representing only x2 = 0 (-6), for a total of 21 bad arrangements." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import scipy.special as special\n", "\n", "n = 7 # count of balls\n", "k = 3 # count of boxes\n", "\n", "total_arrangements = int(special.binom(n + k - 1, n))\n", "bad_arrangements = 21\n", "\n", "print(f'Total ways to put {n} balls into {k} boxes: {total_arrangements}')\n", "print(f'Ways where each box has at least one ball: {total_arrangements - bad_arrangements}')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can verify our answers with Python code that enumerates all the possible arrangements. (Not required for the assignment.)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "total = 0 # total count of arrangements\n", "good = 0 # count of good arrangements\n", "bad = 0 # count of bad arrangements\n", "\n", "for x1 in range(0, 8):\n", " for x2 in range(0, 7 - x1 + 1):\n", " total += 1\n", " \n", " x3 = 7 - x1 - x2\n", " print(f'{total:2}: {x1:2}{x2:2}{x3:2}', end=' ')\n", " \n", " for _ in range(0, x1): print('*', end='') # stars for x1\n", " print('|', end='')\n", " for _ in range(0, x2): print('*', end='') # stars for x2\n", " print('|', end='')\n", " for _ in range(0, x3): print('*', end='') # stars for x3 \n", " \n", " if (x1*x2*x3 == 0):\n", " bad += 1\n", " print(' bad')\n", " else:\n", " good += 1\n", " print(' good')\n", "\n", "print()\n", "print(f'total count: {total}')\n", "print(f' good count: {good}')\n", "print(f' bad count: {bad}')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "#### PROBLEM 6. A class has six boys and nine girls. Any two boys will fight if they're next to each other. How many ways can the teacher line up the students so that no two boys stand next to each other?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "First compute the number of possible lineup patterns. To keep the boys separated, pair each boy with a girl to form a BG or GB pair. That leaves 3 girls. The merged lineup starts with either a boy or a girl.\n", "\n", "Then compute the number of placement of 6 pairs and 3 girls within the patterns." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Start with a girl: There are 9 choose 6 ways to arrange the GB pairs among\n", "# the 9 positions in a line of 6 GB pairs and 3 girls.\n", "import scipy.special\n", "start_with_girl = int(scipy.special.binom(9, 6))\n", "print(f'start_with_girl = {start_with_girl:3,d}')\n", "\n", "# Start with a boy: Put a BG pair at the head of the line. Then there are\n", "# 9 choose 5 ways to arrange the remaining 5 BG pairs among\n", "# the 9 positions in a line of 6 BG pairs and 3 girls.\n", "import scipy.special\n", "start_with_boy = int(scipy.special.binom(9, 5))\n", "print(f' start_with_boy = {start_with_boy:3,d}')\n", "\n", "patterns = start_with_boy + start_with_girl\n", "print(f' patterns = {patterns:3,d}')\n", "print()\n", "\n", "# Within each lineup pattern, there are 9! ways to place the girls \n", "# and 6! ways to place the boys.\n", "\n", "import math\n", "girl_placements = math.factorial(9)\n", "print(f'girl_placements = {girl_placements:7,d}')\n", "\n", "boy_placements = math.factorial(6)\n", "print(f' boy_placements = {boy_placements:7,d}')\n", "print()\n", "\n", "good_lineups = girl_placements*boy_placements*patterns\n", "print(f' good_lineups = {good_lineups:,d}')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "#### PROBLEM 7. A fastfood restaurant sells children's meal boxes. Each box randomly contains one of five different toys. All the toys are equally likely. What is the probability that if you buy five meal boxes, you will collect all five toys at once?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There are 5! ways to collect all 5 toys.\n", "With 5 meal boxes, there are 5^5 possible toy combinations.\n", "Therefore, the probability of collecting all 5 toys is 5!/5^5" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ways = 5*4*3*2*1\n", "combinations = 5**5\n", "probability = ways/combinations\n", "\n", "print(f' Ways to collect all five toys = {ways}')\n", "print(f' Possible toy combinations = {combinations:,d}')\n", "print(f'Probability of collecting all toys at once = {probability:.2f}')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "#### PROBLEM 8. You draw one card randomly from a standard deck of 52 playing cards (no jokers):\n", "\n", "\n", "\n", "#### What is the probability that Event A, B, or C will occur?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# This is a union of the probabilities of the three events,\n", "# so add the individual probilities and subtract the\n", "# probabilities of their intersections.\n", "\n", "# There are 13 heart cards:\n", "p_A = 13/52\n", "print(f'p_A = {p_A:.4f}')\n", "\n", "# Add 40 non-face cards:\n", "p_B = 40/52\n", "print(f'p_B = {p_B:.4f}')\n", "\n", "# Add each suit has cards 3, 6, and 9 divisible by 3, and there are 4 suits:\n", "p_C = 12/52\n", "print(f'p_C = {p_C:.4f}')\n", "print()\n", "\n", "# Subtract 10 cards are both hearts and non-face\n", "p_AB = 10/52\n", "print(f'p_AB = {p_AB:.4f}')\n", "\n", "# Subtract 3 cards are both hearts and divisible by 3:\n", "p_AC = 3/52\n", "print(f'p_AC = {p_AC:.4f}')\n", "\n", "# Subtract 12 cards that are non-face and divisible by 3:\n", "p_BC = 12/52\n", "print(f'p_BC = {p_BC:.4f}')\n", "print()\n", "\n", "# Add back 3 non-face heart cards divisible by 3 (counted twice):\n", "p_ABC = 3/52\n", "print(f'p_ABC = {p_ABC:.4f}')\n", "print()\n", "\n", "# Calculated probability:\n", "calculated_probability = p_A + p_B + p_C - p_AB - p_AC - p_BC + p_ABC\n", "print(f'Calculated probability = {calculated_probability}')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "#### PROBLEM 9. [20 points] Empirically verify the probability that you calculated in Problem 8 with a Python program that simulates drawing randomly from a deck of cards. Initialize a list of cards, each card with a suit and a value. For each trial, generate a random number 0 through 51 in order to pick a card from the list, and check whether any of the events occurred. Do one million trials. After trial 100; 1,000; 10,000; 100,000; and finally 1,000,000, print the proportion of the trials so far where Event A, B, or C occured. How well does the proportion approach the probability you calculated in Problem 8 as the number of trials increases? Determine approximately how many trials are needed for the proportion to match your calculated probability to 3 decimal places." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import random\n", "\n", "deck = []\n", "\n", "for v in range(1, 14):\n", " card = {'value': v, 'suit': 'club'}\n", " deck += [card]\n", " \n", "for v in range(1, 14):\n", " card = {'value': v, 'suit': 'diamond'}\n", " deck += [card]\n", " \n", "for v in range(1, 14):\n", " card = {'value': v, 'suit': 'heart'}\n", " deck += [card]\n", " \n", "for v in range(1, 14):\n", " card = {'value': v, 'suit': 'spade'}\n", " deck += [card]\n", "\n", "count = 0\n", "three_digit_trial = 0\n", "three_digit_probability = 0\n", "\n", "max_trials = 1_000_000\n", "\n", "for trial in range(1, max_trials + 1):\n", " card = random.choice(deck)\n", " \n", " event_A = card['suit'] == 'heart'\n", " event_B = card['value'] < 11;\n", " event_C = event_B and (card['value']%3 == 0)\n", " \n", " if event_A or event_B or event_C: count += 1\n", " p = count/trial\n", " \n", " if (three_digit_trial == 0) \\\n", " and (abs(p - calculated_probability) < 0.0001):\n", " three_digit_trial = trial\n", " three_digit_probability = p\n", " \n", " if (trial == 100) or (trial == 1000) or (trial == 10_000) \\\n", " or (trial == 100_000) or (trial == 1_000_000):\n", " p = count/trial\n", " print(f'Experimental probability after {trial:9,d} trials = {p}')\n", "\n", "print()\n", "print(f'Matched to 3 digits after {three_digit_trial:,d} trials:')\n", "print(f'Experimental: {three_digit_probability}')\n", "print(f' Calculated: {calculated_probability}')" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.7" } }, "nbformat": 4, "nbformat_minor": 4 }