Counting & Probability
Instructions
For each problem, briefly explain/justify how you obtained your answer. Brief explanations are necessary for full credit even if you have the correct numerical answer. Your answers may include summations, products, factorials, exponentials, or combinations—you don’t need to calculate a single numeric value unless stated otherwise.
Problem 1 — Seating Arrangements
How many ways can 10 (distinct) people be seated in a row if:
(a) there are no restrictions on the seating arrangement?
(b) persons A and B must sit next to each other?
(c) there are 5 adults and 5 children, and no two adults nor two children can sit next to each other?
(d) there are 5 married couples and each couple must sit together?
Problem 2 — Zoo Exhibit
At the local zoo, a new exhibit consisting of 3 different species of birds and 3 different species of reptiles is to be formed from a pool of 8 bird species and 6 reptile species. How many exhibits are possible if:
(a) there are no additional restrictions on which species can be selected?
(b) 2 particular bird species cannot be placed together (e.g., they have a predator-prey relationship)?
(c) 1 particular bird species and 1 particular reptile species cannot be placed together?
Problem 3 — Programming Classes (Inclusion-Exclusion)
A university is offering 3 programming classes: one in Java, one in C++, and one in Python. The classes are open to any of the 100 students at the university. There are:
- 27 students in the Java class
- 28 students in the C++ class
- 20 students in the Python class
- 12 students in both Java and C++
- 5 students in both Java and Python
- 8 students in both C++ and Python
- 2 students in all three classes
(a) If a student is chosen randomly, what is the probability that the student is not in any of the 3 programming classes?
(b) If a student is chosen randomly, what is the probability that the student is taking exactly one of the three programming classes?
(c) If two different students are chosen randomly, what is the probability that at least one of the chosen students is taking at least one of the programming classes? Find a numerical answer.
Problem 4 — Investment Strategies
You have $20 million that must be invested among 4 possible companies. Each investment must be in integral units of $1 million. The minimal investments are $1, $2, $3, and $4 million dollars, respectively for companies 1, 2, 3, and 4. How many different investment strategies are available if:
(a) an investment must be made in each company?
(b) investments must be made in at least 3 of the 4 companies?
Problem 5 — Sorted Arrays
Consider an array x of integers with k elements, where each entry has a distinct integer value between 1 and n, inclusive, and the array is sorted in increasing order. In other words, 1 ≤ x[i] ≤ n for all i = 0, 1, 2, …, k−1, and x[0] < x[1] < … < x[k−1].
How many such sorted arrays are possible?
Problem 6 — Poker Hands
Assuming all possible poker hands (5 cards from a standard 52-card deck) are equally likely, what is the probability of being dealt:
(a) a flush? (All 5 cards are of the same suit. Note: straight flushes are also counted as flushes.)
(b) two pairs? (Cards have numeric values a, a, b, b, c, where a, b, and c are all distinct.)
(c) four of a kind? (Cards have numeric values a, a, a, a, b, where a and b are distinct.)
Problem 7 — Robot on a Grid
A robot lives on an n × m grid (with n rows and m columns). The robot starts in cell (1, 1) and can take steps either right or down only. How many distinct paths can the robot take to cell (n, m) if:
(a) there are no additional constraints?
(b) the robot must start by moving to the right?
(c) the robot changes direction exactly 3 times? (Moving down twice in a row is not a direction change, but switching from down to right is. For example, [down, right, right, down] has two direction changes.)
Problem 8 — Rolling Dice
We roll a six-sided die six times. What is the probability that:
(a) we will roll two different numbers thrice (three times) each?
(b) we will roll exactly one number exactly three times?
Problem 9 — Binary String Transmission
A binary string containing M 0’s and N 1’s (in arbitrary order, where all orderings are equally likely) is sent over a network. What is the probability that the first r bits of the received message contain exactly k 1’s?
Problem 10 — Email Distribution
We send out 20 distinguishable emails to 12 distinct users, where each email is equally likely to go to any of the 12 users (some users may receive no email). What is the probability that the 20 emails are distributed such that there are 4 users who receive exactly 2 emails each and 3 users who receive exactly 4 emails each?
Problem 11 — Password Hacking
A hacker has a list of n distinct password candidates, only one of which will successfully log her into a secure system.
(a) If she tries passwords at random, deleting those that do not work, what is the probability that her first successful login will be exactly on her k-th try?
(b) Now say the hacker tries passwords at random but does not delete previously tried passwords. She stops after her first successful login. What is the probability that her first successful login will be exactly on her k-th try?
Problem 12 — Hashing
Suppose that m strings are hashed (randomly) into N buckets, assuming that all Nm arrangements are equally likely. Find the probability that exactly k strings are hashed to the first bucket.
Problem 13 — Degenerate Binary Search Trees (Extra Credit)
To get good performance from binary search trees (BST), we must consider the probability of producing completely degenerate BSTs (where each node has at most one child).
(a) If the integers 1 through n are inserted in arbitrary order into a BST (where each possible order is equally likely), what is the probability (as an expression in terms of n) that the resulting BST will have completely degenerate structure?
(b) Using your expression from part (a), determine the smallest value of n for which the probability of forming a completely degenerate BST is less than 0.001 (i.e., 0.1%).