Willys Flashcards Download
Become an Actuary › Exams › Flashcards › Exam P › Set Theory & Combinatorics
Exam P · ~10-12%

Exam P — Set Theory & Combinatorics Flashcards

Sample spaces, set operations and De Morgan, Kolmogorov axioms, inclusion-exclusion, equally likely outcomes, permutations, combinations, multinomial coefficients, the binomial theorem, and basic probability computed by counting.

34 cards9 topicsFree · fact-checked · LaTeX math
Tap card or press Space to flip
Answer

Import this deck

Download all 34 cards and import them into your flashcard app (JSON or CSV — works with Anki). Using the Willys app? No import needed — this deck is already built in (Settings → Library → Browse).

Download JSON Download CSV

Every deck is built into the Willys app

All of these decks — including the full practice problem banks — come built into Willys AI Flashcards & Quizzes for iPhone & iPad (Mac version coming soon), with FSRS + SM-2 spaced repetition, streaks, and exam-date cram mode. 14-day free trial, then $14.99. To load a deck in the app: Settings → Library → Browse, then pick your exam and deck.

Download on the App Store

More Exam P decks:

Common Traps Conditional Probability & Bayes Conditional Probability & Bayes Practice Continuous Distributions Continuous Distributions Practice Covariance, Sums & CLT

← All Exam P decks

Browse all 34 cards as a list
  1. Sample spaces & events
    What is a **sample space** $S$ and an **event** in a probability model?
    The sample space $S$ is the set of all possible outcomes of a random experiment. An event is any subset $A\subseteq S$. A single outcome $\omega\in S$ is an elementary (or simple) event, and $S$ itself is the certain event while $\emptyset$ is the impossible event.
  2. Set operations
    Define the three set operations **union**, **intersection**, and **complement** for events $A,B\subseteq S$.
    Union: $A\cup B=\{\omega:\omega\in A \text{ or } \omega\in B\}$ (at least one occurs). Intersection: $A\cap B=\{\omega:\omega\in A \text{ and } \omega\in B\}$ (both occur). Complement: $A^{c}=\{\omega\in S:\omega\notin A\}$ (A does not occur).
  3. Set operations
    State **De Morgan's laws** for two events.
    $(A\cup B)^{c}=A^{c}\cap B^{c}$ and $(A\cap B)^{c}=A^{c}\cup B^{c}$. In words: the complement of a union is the intersection of the complements, and vice versa. They generalize to $\left(\bigcup_{i}A_{i}\right)^{c}=\bigcap_{i}A_{i}^{c}$.
  4. Set operations
    What does it mean for events $A$ and $B$ to be **mutually exclusive** (disjoint)?
    They cannot both occur, i.e. $A\cap B=\emptyset$, so $\Pr(A\cap B)=0$. For disjoint events the addition rule simplifies to $\Pr(A\cup B)=\Pr(A)+\Pr(B)$. Disjoint is not the same as independent.
  5. Axioms
    State the three **Kolmogorov axioms** of probability.
    1) Non-negativity: $\Pr(A)\geq 0$ for every event $A$. 2) Normalization: $\Pr(S)=1$. 3) Countable additivity: for pairwise disjoint $A_{1},A_{2},\ldots$, $\Pr\!\left(\bigcup_{i=1}^{\infty}A_{i}\right)=\sum_{i=1}^{\infty}\Pr(A_{i})$.
  6. Axioms
    Using the axioms, derive the **complement rule** and the value of $\Pr(\emptyset)$.
    Since $A$ and $A^{c}$ are disjoint with $A\cup A^{c}=S$, additivity gives $\Pr(A)+\Pr(A^{c})=\Pr(S)=1$, so $\Pr(A^{c})=1-\Pr(A)$. Taking $A=S$ gives $\Pr(\emptyset)=1-\Pr(S)=0$.
  7. Axioms
    If $A\subseteq B$, what can you say about $\Pr(A)$ versus $\Pr(B)$, and why?
    Monotonicity: $\Pr(A)\leq\Pr(B)$. Write $B=A\cup(B\cap A^{c})$ as a disjoint union, so $\Pr(B)=\Pr(A)+\Pr(B\cap A^{c})\geq\Pr(A)$ because the second term is $\geq 0$. A corollary is that every probability satisfies $0\leq\Pr(A)\leq 1$.
  8. Inclusion-exclusion
    State the **addition rule** (inclusion–exclusion for two events) $\Pr(A\cup B)$.
    $\Pr(A\cup B)=\Pr(A)+\Pr(B)-\Pr(A\cap B)$. The intersection is subtracted once because it is counted in both $\Pr(A)$ and $\Pr(B)$. If $A\cap B=\emptyset$ the last term is $0$.
  9. Inclusion-exclusion
    State **inclusion–exclusion** for three events $\Pr(A\cup B\cup C)$.
    $\Pr(A\cup B\cup C)=\Pr(A)+\Pr(B)+\Pr(C)-\Pr(A\cap B)-\Pr(A\cap C)-\Pr(B\cap C)+\Pr(A\cap B\cap C)$. Pattern: add singles, subtract pairwise intersections, add back the triple intersection.
  10. Inclusion-exclusion
    In a group, $\Pr(A)=0.5$, $\Pr(B)=0.4$, and $\Pr(A\cap B)=0.2$. Find $\Pr(A\cup B)$ and $\Pr(A^{c}\cap B^{c})$.
    Addition rule: $\Pr(A\cup B)=0.5+0.4-0.2=0.7$. By De Morgan, $\Pr(A^{c}\cap B^{c})=\Pr\!\big((A\cup B)^{c}\big)=1-\Pr(A\cup B)=1-0.7=0.30$.
  11. Inclusion-exclusion
    An insurer's policyholders carry coverages $A$, $B$, $C$ with $\Pr(A)=\Pr(B)=\Pr(C)=0.30$, each pairwise intersection $=0.10$, and $\Pr(A\cap B\cap C)=0.05$. What fraction carry **at least one** coverage?
    By inclusion–exclusion, $\Pr(A\cup B\cup C)=3(0.30)-3(0.10)+0.05=0.90-0.30+0.05=0.65$. So $65\%$ carry at least one coverage (and $35\%$ carry none).
  12. Inclusion-exclusion
    With the coverages from the previous card ($\Pr$ each $=0.30$, pairwise $=0.10$, triple $=0.05$), what fraction carry **exactly one** coverage?
    The 'exactly one' count for three events is $\sum\Pr(\text{single})-2\sum\Pr(\text{pairwise})+3\Pr(\text{triple})$. $=3(0.30)-2(3)(0.10)+3(0.05)=0.90-0.60+0.15=0.45$. So $45\%$ carry exactly one coverage.
  13. Equally likely & counting
    When are outcomes **equally likely**, and how is $\Pr(A)$ computed in that case?
    When $S$ is finite and every outcome has the same probability $1/|S|$. Then for any event $A$, $\Pr(A)=\frac{|A|}{|S|}=\frac{\text{number of favorable outcomes}}{\text{total number of outcomes}}$. This reduces probability to a counting problem.
  14. Permutations
    How many **arrangements** (orderings) are there of $n$ distinct objects, and why?
    $n!=n\cdot(n-1)\cdots 2\cdot 1$. The first position has $n$ choices, the next $n-1$, and so on by the multiplication principle, giving the product $n!$. By convention $0!=1$.
  15. Permutations
    Define the number of **permutations** of $r$ objects chosen from $n$ distinct objects, ${}_{n}P_{r}$.
    ${}_{n}P_{r}=\frac{n!}{(n-r)!}=n(n-1)\cdots(n-r+1)$. Order matters: it counts ordered selections (arrangements) of size $r$ from $n$ distinct items without replacement.
  16. Combinations
    Define the **combination** (binomial coefficient) $\binom{n}{r}$ and state its symmetry property.
    $\binom{n}{r}=\frac{n!}{r!\,(n-r)!}=\frac{{}_{n}P_{r}}{r!}$, the number of unordered subsets of size $r$ from $n$ distinct items. Symmetry: $\binom{n}{r}=\binom{n}{n-r}$. Also $\binom{n}{0}=\binom{n}{n}=1$.
  17. Combinations
    How many ways can a committee of $4$ be chosen from $10$ people? Compute the number.
    Order does not matter, so use a combination: $\binom{10}{4}=\frac{10!}{4!\,6!}=\frac{10\cdot 9\cdot 8\cdot 7}{4\cdot 3\cdot 2\cdot 1}=\frac{5040}{24}=210$.
  18. Equally likely & counting
    A bag has $6$ red and $4$ blue chips. Draw $3$ without replacement. Find $\Pr(\text{exactly }2\text{ red})$.
    Equally likely subsets of size $3$: total $\binom{10}{3}=120$. Favorable: choose $2$ reds and $1$ blue, $\binom{6}{2}\binom{4}{1}=15\cdot 4=60$. $\Pr=\frac{60}{120}=0.50$.
  19. Multinomial & partitions
    How many distinct arrangements of the letters in **MISSISSIPPI** are there?
    There are $11$ letters with repeats $\text{M}{:}1,\ \text{I}{:}4,\ \text{S}{:}4,\ \text{P}{:}2$. Use the multinomial (permutations of a multiset): $\frac{11!}{1!\,4!\,4!\,2!}=\frac{39{,}916{,}800}{1\cdot 24\cdot 24\cdot 2}=\frac{39{,}916{,}800}{1152}=34{,}650$.
  20. Multinomial & partitions
    State the **multinomial coefficient** that counts arrangements of $n$ items in $k$ groups of sizes $n_{1},\ldots,n_{k}$ (with $\sum n_{i}=n$).
    $\binom{n}{n_{1},n_{2},\ldots,n_{k}}=\frac{n!}{n_{1}!\,n_{2}!\cdots n_{k}!}$. It counts the ways to partition $n$ distinct objects into labeled groups of the given sizes (equivalently, distinct orderings of a multiset). When $k=2$ this reduces to $\binom{n}{n_{1}}$.
  21. Multinomial & partitions
    In how many ways can $12$ distinct claims be split into three **labeled** teams of sizes $5$, $4$, and $3$? Compute it.
    Use the multinomial coefficient: $\frac{12!}{5!\,4!\,3!}=\frac{479{,}001{,}600}{120\cdot 24\cdot 6}=\frac{479{,}001{,}600}{17{,}280}=27{,}720$.
  22. Multinomial & partitions
    How many ways are there to partition $9$ distinct objects into three **unlabeled** groups of $3$ each? Compute it.
    First count labeled groups: $\frac{9!}{3!\,3!\,3!}=\frac{362{,}880}{216}=1680$. Because the three groups are the same size and **unlabeled**, divide by $3!=6$ for the interchangeable group labels: $\frac{1680}{6}=280$.
  23. Binomial theorem
    State the **binomial theorem** for $(x+y)^{n}$.
    $(x+y)^{n}=\displaystyle\sum_{k=0}^{n}\binom{n}{k}x^{k}y^{n-k}$. The coefficient of the $x^{k}y^{n-k}$ term is the binomial coefficient $\binom{n}{k}$, the number of ways to choose which $k$ of the $n$ factors contribute an $x$.
  24. Binomial theorem
    Use the binomial theorem to evaluate $\displaystyle\sum_{k=0}^{n}\binom{n}{k}$ and $\displaystyle\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}$.
    Set $x=y=1$ in $(x+y)^{n}$: $\sum_{k=0}^{n}\binom{n}{k}=2^{n}$ (total number of subsets of an $n$-set). Set $x=-1,\ y=1$: $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}=(-1+1)^{n}=0$ for $n\geq 1$.
  25. Binomial theorem
    Find the coefficient of $x^{3}$ in the expansion of $(2x+3)^{5}$.
    General term: $\binom{5}{k}(2x)^{k}(3)^{5-k}$. For $x^{3}$ take $k=3$: $\binom{5}{3}(2)^{3}(3)^{2}=10\cdot 8\cdot 9=720$. So the coefficient of $x^{3}$ is $720$.
  26. Binomial theorem
    **Pascal's rule:** express $\binom{n}{k}$ in terms of $\binom{n-1}{\cdot}$ coefficients.
    $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$. Interpretation: of the $n$ items, fix one special item; subsets of size $k$ either contain it ($\binom{n-1}{k-1}$ ways) or do not ($\binom{n-1}{k}$ ways). This is the rule that builds Pascal's triangle.
  27. Permutations
    Five people are seated in a row at random. Find $\Pr(\text{two specific people sit together})$.
    Total arrangements: $5!=120$. Glue the two specified people into one block (treat as a single unit): $4!$ orders of the $4$ units, times $2!$ internal orders $=24\cdot 2=48$ favorable. $\Pr=\frac{48}{120}=0.40$.
  28. Equally likely & counting
    A standard $52$-card deck deals a $5$-card hand. Find $\Pr(\text{four of a kind})$.
    Total hands: $\binom{52}{5}=2{,}598{,}960$. Count four-of-a-kind hands: choose the rank that appears four times ($13$ ways), then the $5$th card from the remaining $48$ cards. Favorable $=13\cdot 48=624$, so $\Pr=\frac{624}{2{,}598{,}960}\approx 0.000240$.
  29. Equally likely & counting
    From a lot of $20$ items, $5$ are defective. A sample of $4$ is drawn without replacement. Find $\Pr(\text{exactly one defective})$.
    Total samples: $\binom{20}{4}=4845$. Favorable: $1$ defective and $3$ good, $\binom{5}{1}\binom{15}{3}=5\cdot 455=2275$. $\Pr=\frac{2275}{4845}\approx 0.4696$.
  30. Equally likely & counting
    In a room of $5$ people, find the probability that **at least two share a birthday** (ignore leap years; assume $365$ equally likely days).
    Use the complement (all distinct): $\Pr(\text{all distinct})=\frac{365\cdot 364\cdot 363\cdot 362\cdot 361}{365^{5}}\approx 0.97286$. $\Pr(\text{at least one match})=1-0.97286\approx 0.0271$.
  31. Equally likely & counting
    Why is computing **'at least one'** usually easier through the complement, and what is the rule?
    Directly summing the disjoint cases (exactly $1$, exactly $2$, …) is tedious, but 'at least one' is the complement of 'none.' For independent trials, $\Pr(\text{at least one})=1-\Pr(\text{none})=1-\prod_{i}\Pr(\text{not occurring on trial }i)$.
  32. Equally likely & counting
    A multiple-choice question has $5$ choices; a student answers $8$ such questions purely at random. Find $\Pr(\text{at least one correct})$.
    Each question is correct with probability $1/5$, wrong with $4/5$, independently. 'At least one correct' is the complement of 'all wrong': $\Pr(\text{all wrong})=\left(\frac{4}{5}\right)^{8}=\frac{65536}{390625}\approx 0.1678$. $\Pr(\text{at least one correct})=1-0.1678\approx 0.8322$.
  33. Equally likely & counting
    Two fair six-sided dice are rolled. Using the sample space of $36$ equally likely ordered pairs, find $\Pr(\text{sum}=7)$ and $\Pr(\text{sum}=7\text{ or }11)$.
    Sum $=7$: pairs $(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)$ — $6$ outcomes, so $\Pr=\frac{6}{36}=\frac{1}{6}$. Sum $=11$: $(5,6),(6,5)$ — $2$ outcomes. These are disjoint from 'sum $=7$', so $\Pr(7\text{ or }11)=\frac{6+2}{36}=\frac{8}{36}=\frac{2}{9}\approx 0.2222$.
  34. Multinomial & partitions
    How many distinct ways can the $11$-letter sequence in card 'MISSISSIPPI' be arranged so that it **begins with M**? (Reuse the multiset arrangement idea.)
    Fix M in the first position; arrange the remaining $10$ letters $\text{I}{:}4,\ \text{S}{:}4,\ \text{P}{:}2$: $\frac{10!}{4!\,4!\,2!}=\frac{3{,}628{,}800}{24\cdot 24\cdot 2}=\frac{3{,}628{,}800}{1152}=3150$. (Equivalently $34{,}650\times\frac{1}{11}=3150$, since by symmetry $1$ of every $11$ arrangements starts with the single M.)