Chapter 3 Set Theory and Counting Principles
3.1 Learning goals
After this chapter, you should be able to:
- use set notation and operations to describe collections and events;
- interpret unions, intersections, complements, and differences;
- solve two-set and three-set counting problems;
- select and apply appropriate general counting rules;
- distinguish permutations from combinations;
- use binomial and multinomial coefficients in counting problems.
3.2 Set Theory
Probability begins by translating verbal descriptions into events. Words such as or, and, not, at least one, and neither have exact set meanings. Learning this language now prevents many errors later in conditional probability and random variables.
3.2.1 Sets, elements, and subsets
A set is a collection of distinct objects called elements. We write \(x\in A\) when \(x\) belongs to \(A\) and \(x\notin A\) otherwise. The empty set, denoted \(\varnothing\), contains no elements.
\(A\) is a subset of \(B\), written \(A\subseteq B\), if every element of \(A\) also belongs to \(B\). The sets are equal when they contain exactly the same elements.
For example, if \(A=\{1,3,5,\ldots\}\) is the set of positive odd integers and \(B=\{1,2,3,\ldots\}\) is the set of positive integers, then \(A\subseteq B\). A subset relationship means containment; it does not mean that the two sets have the same size.
3.2.2 Set operations
Let \(S\) denote the universal set currently under discussion.
For sets \(A\) and \(B\):
- the union \(A\cup B\) contains elements in \(A\) or \(B\) or both;
- the intersection \(A\cap B\) contains elements common to both sets;
- the complement \(A^c\) contains elements of \(S\) that are not in \(A\);
- the difference \(A-B=A\cap B^c\) contains elements in \(A\) but not in \(B\).
The word “or” is inclusive in probability: \(A\cup B\) includes the overlap. By contrast, “\(A\) but not \(B\)” removes that overlap.
Sets \(A\) and \(B\) are disjoint (or mutually exclusive) when \(A\cap B=\varnothing\). They cannot occur together.
De Morgan’s laws translate “not” applied to a combined event:
\[ (A\cup B)^c=A^c\cap B^c, \qquad (A\cap B)^c=A^c\cup B^c. \]
“Not in either \(A\) or \(B\)” means “not in \(A\) and not in \(B\).” Meanwhile, “not in both” means at least one of \(A\) and \(B\) fails to occur.
Example: translating set notation
Let \(S=\{1,2,3,4,5,6\}\), \(A=\{1,2,3\}\), and \(B=\{2,4,6\}\). Then
\[ A\cap B=\{2\},\qquad A\cup B=\{1,2,3,4,6\},\qquad A-B=\{1,3\}, \]
and \(A^c=\{4,5,6\}\). Notice that \(A\cap B\) satisfies both descriptions, while \(A\cup B\) collects every value satisfying at least one.
Check your understanding
If \(A\subseteq B\), determine \(A\cap B\) and \(A\cup B\).
Solution. Every element of \(A\) is already in \(B\), so \(A\cap B=A\) and \(A\cup B=B\).3.2.3 Venn diagram thinking
A Venn diagram represents sets as regions inside a universal set. Shading makes unions, intersections, complements, and equivalent set expressions visible at a glance.
Example: verifying De Morgan’s laws
Use set membership and Venn diagrams to verify
\[ (A\cup B)^c=A^c\cap B^c, \qquad (A\cap B)^c=A^c\cup B^c. \]
Show solution and Venn diagrams
For the first identity, an element is in \((A\cup B)^c\) precisely when it is in neither \(A\) nor \(B\). That means it belongs to both \(A^c\) and \(B^c\), hence to \(A^c\cap B^c\).
For the second identity, an element is outside \(A\cap B\) when it fails to belong to at least one of the sets. It must therefore be in \(A^c\) or \(B^c\), hence in \(A^c\cup B^c\).
3.2.4 Relationships involving sets
For arbitrary sets \(A,B,C\):
- Commutative and idempotent laws \[A\cup B=B\cup A,\quad A\cap B=B\cap A,\quad A\cup A=A,\quad A\cap A=A.\]
- Subset absorption: if \(A\subseteq B\), then \[A\cup B=B,\qquad A\cap B=A.\]
- Empty-set laws \[\varnothing\subseteq A,\quad A\cup\varnothing=A,\quad A\cap\varnothing=\varnothing,\quad A-\varnothing=A.\]
- Distributive laws \[A\cap(B\cup C)=(A\cap B)\cup(A\cap C),\] \[A\cup(B\cap C)=(A\cup B)\cap(A\cup C).\]
- Containment chain \[A\cap B\subseteq A\subseteq A\cup B,\qquad A\cap B\subseteq B\subseteq A\cup B.\]
- De Morgan’s laws \[(A\cup B)^c=A^c\cap B^c,\qquad (A\cap B)^c=A^c\cup B^c.\]
These identities are the algebra of events. They allow a complicated verbal description to be rewritten into an equivalent form that is easier to visualize or calculate.
3.3 Counting Principles
3.3.1 Counting finite sets
Counting with Venn diagrams is based on partitioning sets into non-overlapping regions. For a three-set problem, work from the inside outward:
- enter the count in \(A\cap B\cap C\);
- subtract it from each reported pairwise intersection;
- use the set totals to obtain the three “only” regions;
- add the seven interior regions, then subtract from the population total to find “none.”
For finite sets, the inclusion–exclusion rules are
\[ n(A\cup B)=n(A)+n(B)-n(A\cap B) \]
and
\[ \begin{aligned} n(A\cup B\cup C) ={}&n(A)+n(B)+n(C)\\ &-n(A\cap B)-n(A\cap C)-n(B\cap C)\\ &+n(A\cap B\cap C). \end{aligned} \]
Pairwise overlaps are subtracted because they were counted twice. The triple overlap is then added back because the subtraction removed it too many times.
Worked example: health-risk profiles
Among 40,000 patients, let \(A\) denote smokers, \(B\) heavy drinkers, and \(C\) people with a sedentary lifestyle. Suppose
\[ \begin{array}{c|ccccccc} \text{Region}&A&B&C&A\cap B&A\cap C&B\cap C&A\cap B\cap C\\ \hline n&29{,}000&25{,}000&30{,}000&22{,}000&24{,}000&20{,}000&20{,}000. \end{array} \]
Start with 20,000 in the center. The pairwise-only regions are therefore \(2{,}000\), \(4{,}000\), and \(0\). The single-set-only regions are \(3{,}000\) in \(A\), \(3{,}000\) in \(B\), and \(6{,}000\) in \(C\). Hence
\[n(A\cup B\cup C)=38{,}000,\]
so 2,000 patients have none of the three characteristics. Also, the number who smoke but do not drink heavily is
\[n(A\cap B^c)=3{,}000+4{,}000=7{,}000.\]
The important technique is not memorizing a picture. It is decomposing a complicated event into mutually exclusive minimal regions and then adding only the regions requested.
Worked example: market campaign
A company surveys 15,000 people. Let \(L\) be those who used its product last year and \(T\) those who used it this year. Suppose \(n(L)=4{,}500\), \(n(T)=7{,}500\), and \(n(L\cap T)=4{,}000\).
\[n(L\cup T)=4{,}500+7{,}500-4{,}000=8{,}000.\]
Therefore 7,000 used the product in neither year, 500 used it only last year, and 3,500 used it only this year. The overlap is subtracted once because it appears in both marginal totals.
Exercises: Counting finite sets
Exercise 1 — Product use before and after a campaign. A manufacturer surveys 15,000 people. Of these, 4,500 used its product last year, 7,500 used it this year, and 4,000 used it in both years. Determine the number who:
- used the product in at least one of the two years;
- used it in neither year;
- used it last year but not this year;
- used it this year but not last year.
Show solution to Exercise 1
Let \(L\) and \(T\) represent product use last year and this year. By inclusion–exclusion,
\[n(L\cup T)=4500+7500-4000=8000.\]
Therefore: (1) 8,000 used the product in at least one year; (2) \(15000-8000=7000\) used it in neither year; (3) \(4500-4000=500\) used it only last year; and (4) \(7500-4000=3500\) used it only this year.Exercise 2 — Student characteristics. A university surveys 5,000 students. Let \(E\) denote participation in extracurricular activities, \(D\) a double major, and \(J\) a part-time job. Suppose
\[n(E)=2600,\quad n(D)=1200,\quad n(J)=2500,\] \[n(E\cap D)=400,\quad n(E\cap J)=1000,\quad n(D\cap J)=300,\]
and \(n(E\cap D\cap J)=200\). Find: (a) double majors with neither \(E\) nor \(J\); (b) double majors with exactly one of \(E\) and \(J\); (c) students with neither \(E\) nor \(J\).
Show solution to Exercise 2
Start with the triple intersection. The parts of \(D\cap E\) and \(D\cap J\) outside the center contain \(400-200=200\) and \(300-200=100\) students. Thus:
- \(1200-200-100-200=700\);
- \(200+100=300\);
- \(5000-n(E\cup J)=5000-(2600+2500-1000)=900\).
Exercise 3 — Disease symptoms. Among 1,000 patients, everyone has at least one of symptoms \(A,B,C\). Suppose \(n(A\cup B)=900\), \(n(A\cup C)=900\), \(n(B\cup C)=800\), and \(n(A)=650\), \(n(B)=500\), \(n(C)=550\). Find: (a) \(n(A\cap B)\); (b) \(n((A\cup B)\cap C^c)\); (c) \(n(A\cap B\cap C)\).
Show solution to Exercise 3
For (a), \[n(A\cap B)=650+500-900=250.\]
For (b), everyone outside \(C\) must belong to \(A\cup B\), so \[n((A\cup B)\cap C^c)=n(C^c)=1000-550=450.\]
Also, \(n(A\cap C)=300\) and \(n(B\cap C)=250\). If \(x=n(A\cap B\cap C)\), inclusion–exclusion gives \[1000=650+500+550-250-300-250+x,\] so (c) \(x=100\).Exercise 4 — Insurance products. An insurance agent offers auto (\(A\)), homeowners (\(H\)), and renters (\(R\)) coverage, with \(H\cap R=\varnothing\). Suppose 17% buy none, 64% buy auto, twice as many buy homeowners as renters, 35% buy two products, and 11% buy homeowners but not auto. Find the percentage buying both auto and renters coverage.
Show solution to Exercise 4
Let \(x\) be the percentage in \(A\cap R\). Because \(H\) and \(R\) are mutually exclusive, the clients with two products are in \(A\cap H\) or \(A\cap R\). Hence \(n(A\cap H)=35-x\).
The union contains \(100-17=83\%\). The 64% with auto and the 11% with homeowners only leave \(83-64-11=8\%\) with renters only. Therefore \[H=(35-x)+11=46-x,\qquad R=x+8.\] Since \(H=2R\), \[46-x=2(x+8),\] which gives \(x=10\%\).Exercise 5 — Television audiences. Of 100 viewers, 34 watched CBS, 15 watched NBC, and 10 watched ABC. The three pairwise intersection counts are 7, 6, and 5, while 4 watched all three. A separate group of 18 watched HGTV and none of CBS, NBC, or ABC. How many watched none of the four channels?
Show solution to Exercise 5
For the first three channels, inclusion–exclusion gives \[34+15+10-7-6-5+4=45.\]
The 18 HGTV viewers are disjoint from that group, so \(45+18=63\) watched at least one of the four channels. Thus \(100-63=37\) watched none.3.3.2 General counting rules
Probability questions with equally likely outcomes often reduce to
\[ \mathbb{P}(A)=\frac{n(A)}{n(S)}. \]
The challenge is usually not the division; it is counting \(n(A)\) and \(n(S)\) correctly. Before choosing a formula, write one typical outcome in words and ask what would make another outcome different.
- Use the addition principle for alternative, non-overlapping cases.
- Use the multiplication principle when one complete outcome is assembled through successive choices.
- Use a permutation when selected objects occupy distinct positions or roles.
- Use a combination when only membership in the selected group matters.
- Check whether objects may be selected again, whether some objects are identical, or whether the easiest route is to count the complement.
Do not decide from the words and or or alone. “Choose a stock and a bond” describes successive choices and suggests multiplication. “Choose a stock or a bond” suggests addition only if the two cases cannot overlap. Always identify what one complete outcome looks like.
Addition principle
If alternatives are mutually exclusive and contain \(n_1,n_2,\ldots,n_k\) possibilities, the total number of possibilities is
\[n_1+n_2+\cdots+n_k.\]
Use this principle when the possible outcomes have been split into separate cases and every outcome belongs to exactly one case. The word or suggests addition only when the alternatives cannot overlap. If overlap is possible, first make the cases disjoint or use inclusion–exclusion.
Example: selecting one insurance product
An insurer offers 4 life products and 3 disability products. If a client chooses exactly one product, there are
\[4+3=7\]
choices. The cases are disjoint because the client chooses a life product or a disability product, not both.
Example: overlapping investment lists
A research platform lists 18 equity funds and 12 income funds, with 5 appearing in both lists. The number appearing on at least one list is not \(18+12\). It is
\[18+12-5=25,\]
because the five overlapping funds would otherwise be counted twice.
Multiplication principle
If an outcome is produced through \(k\) successive stages and stage \(i\) has \(n_i\) choices for every preceding choice, then the number of complete outcomes is
\[n_1n_2\cdots n_k.\]
Use this principle when every complete outcome contains one choice from each of several stages. Think of a tree diagram: each stage creates new branches, and a complete outcome is one full path through the tree.
Addition combines separate groups of complete outcomes. Multiplication constructs each complete outcome from several components. This distinction is more reliable than memorizing “or means add” and “and means multiply.”
Example: constructing a benefit package
A company offers 3 health plans, 4 life-insurance levels, and 2 deductible options. A complete package contains one choice from each category, so there are
\[3\times4\times2=24\]
packages. We multiply because the choices are successive components of the same package.
Example: claim identification numbers
A claim identifier contains two letters followed by four digits. If repetition is allowed, there are
\[26^2\times10^4=6{,}760{,}000\]
identifiers. If letters and digits may not repeat, the count becomes
\[26\times25\times10\times9\times8\times7=3{,}276{,}000.\]
The number of available choices decreases at each stage when repetition is forbidden.
Factorials and arrangements
For a positive integer \(n\),
\[n!=n(n-1)(n-2)\cdots2\cdot1,\]
with \(0!=1\). The quantity \(n!\) counts the ways to arrange \(n\) distinct objects in order.
For example, five different risk reports can be placed in \(5!=120\) different orders. The convention \(0!=1\) makes the permutation and combination formulas work at their boundary values.
Permutations: order matters
A permutation is an ordered selection. The number of ways to select and arrange \(r\) distinct objects from \(n\) distinct objects, without replacement, is
\[ \operatorname{Perm}(n,r)=n(n-1)\cdots(n-r+1)=\frac{n!}{(n-r)!}. \]
Use a permutation when the positions have different meanings—first versus second, president versus treasurer, or first claim reviewed versus second claim reviewed. There are \(n\) choices for the first position, \(n-1\) for the second, and so on until \(r\) positions have been filled.
Example: ranking investment proposals
An investment committee must rank its top three proposals from eight candidates. Because first, second, and third places are different roles,
\[\operatorname{Perm}(8,3)=8\times7\times6=336.\]
Changing the order changes the ranking, so this is not a combination.
Combinations: order does not matter
A combination is an unordered selection. The number of ways to choose \(r\) objects from \(n\) distinct objects, without replacement, is
\[ \binom{n}{r}=\frac{n!}{r!(n-r)!}. \]
Use a combination when rearranging the selected objects does not create a new outcome. Each group of \(r\) objects appears \(r!\) times among the permutations—once for every internal ordering. Dividing by \(r!\) removes this overcounting.
The following identities are useful both computationally and conceptually:
\[ \binom n0=\binom nn=1,\qquad \binom n1=\binom n{n-1}=n,\qquad \binom nr=\binom n{n-r}. \]
The last identity says that choosing the \(r\) objects that enter a group is equivalent to choosing the \(n-r\) objects that stay outside it. This symmetry often reveals a shorter solution.
The quickest diagnostic is the swap test. Imagine selecting Ahmed and Fatima. If “Ahmed then Fatima” and “Fatima then Ahmed” are different outcomes, use a permutation. If both descriptions represent the same selected pair, use a combination.
Example: audit sample
An actuary selects 4 claims from 12 for an audit. The order in which the claims are selected does not change the final sample, so
\[\binom{12}{4}=495.\]
Repetition and repeated objects
Two related situations require different formulas:
- If \(r\) successive selections are made from \(n\) options with replacement and order matters, there are \(n^r\) sequences.
- If \(n\) objects contain groups of identical objects of sizes \(n_1,\ldots,n_k\), where \(n_1+\cdots+n_k=n\), the number of distinct arrangements is \[\frac{n!}{n_1!\cdots n_k!}.\]
For example, the letters in RISK have \(4!=24\) arrangements. The letters in LOSS have only
\[\frac{4!}{2!}=12\]
distinct arrangements because exchanging the two identical S’s produces no new word.
The same formula applies to any sequence with prescribed category counts. For example, a four-digit output containing one 0, one 5, and two 9s has
\[\frac{4!}{1!1!2!}=12\]
distinct orders. If four independent digits are generated uniformly from \(0\) through \(9\), there are \(10^4\) equally likely sequences, so the probability of this exact composition is \(12/10^4\).
Complement principle
Use complement counting when the unwanted outcomes are much easier to count than the desired outcomes:
\[n(A)=n(S)-n(A^c).\]
For example, the number of four-digit PINs containing at least one zero is easier to obtain by subtracting the PINs with no zero:
\[10^4-9^4=3{,}439.\]
The direct method would require several overlapping cases depending on the number and positions of the zeros.
Division principle
Use the division principle when a construction counts every final outcome the same number of times. If a procedure produces \(N\) descriptions and each final outcome has exactly \(d\) descriptions, the number of distinct outcomes is \(N/d\).
The combination formula is an important application: ordered selection produces \(\operatorname{Perm}(n,r)\) descriptions of groups, but each unordered group is described by its \(r!\) possible orders. Therefore
\[\binom nr=\frac{\operatorname{Perm}(n,r)}{r!}.\]
Multinomial principle
Use the multinomial principle when \(n\) distinct objects must be divided into labelled groups of specified sizes \(n_1,\ldots,n_k\), where \(n_1+\cdots+n_k=n\):
\[\binom{n}{n_1,n_2,\ldots,n_k}=\frac{n!}{n_1!n_2!\cdots n_k!}.\]
For example, assigning 10 analysts to labelled teams of sizes 4, 3, and 3 can be done in
\[\frac{10!}{4!3!3!}=4{,}200\]
ways. The group labels matter, but order within each group does not.
A related selection rule applies when the population itself is divided into types. If a portfolio contains \(n_1\) available stocks, \(n_2\) available bonds, and \(n_3\) available sukuk, then the number of portfolios containing exactly \(r_1,r_2,r_3\) of the three types is
\[ \binom{n_1}{r_1}\binom{n_2}{r_2}\binom{n_3}{r_3}. \]
We choose within each category and multiply because all category choices are required to construct one portfolio.
Binomial and multinomial theorems
For a nonnegative integer \(n\), the binomial theorem is
\[ (x+y)^n=\sum_{r=0}^{n}\binom nr x^{n-r}y^r. \]
More generally, if \(r_1+\cdots+r_k=n\), the coefficient of \(x_1^{r_1}\cdots x_k^{r_k}\) in \((x_1+\cdots+x_k)^n\) is
\[ \binom{n}{r_1,\ldots,r_k}=\frac{n!}{r_1!\cdots r_k!}. \]
Why do counting coefficients appear in algebra? In expanding \((x+y)^n\), we choose either \(x\) or \(y\) from each of \(n\) factors. A term \(x^{n-r}y^r\) is produced whenever exactly \(r\) factors contribute \(y\), and there are \(\binom nr\) ways to choose those factors.
For example,
\[ (x+y)^4=x^4+4x^3y+6x^2y^2+4xy^3+y^4. \]
The coefficient 6 counts the ways to choose the two factors that contribute \(y\). Similarly, the coefficient of \(xy^2\) in \((1+x+y)^4\) is
\[ \frac{4!}{1!1!2!}=12, \]
because the four factors must contribute one \(1\), one \(x\), and two \(y\) terms.
The multinomial coefficient has two complementary interpretations: it counts arrangements containing repeated types, and it counts ways to divide labelled positions among categories of prescribed sizes. Recognizing both interpretations makes many probability problems much easier.
Combinations with repetition
Use combinations with repetition when \(r\) selections are made from \(n\) categories, repetition is allowed, and order does not matter. The number of selections is
\[\binom{n+r-1}{r}.\]
For example, choosing 6 funds from 4 fund categories when several funds may come from the same category is equivalent to solving
\[x_1+x_2+x_3+x_4=6,\qquad x_i\ge0.\]
There are
\[\binom{4+6-1}{6}=\binom96=84\]
possible category allocations. This method is often called stars and bars.
A practical decision guide
| Ask this question | If the answer is yes | Typical count |
|---|---|---|
| Are these disjoint alternative cases? | Add the case counts | \(n_1+\cdots+n_k\) |
| Is one outcome built through successive stages? | Multiply the stage counts | \(n_1\cdots n_k\) |
| Do selected objects occupy distinct positions? | Use a permutation | \(n!/(n-r)!\) |
| Does only the selected group matter? | Use a combination | \(\binom nr\) |
| Are selections replaced and does order matter? | Use sequences with repetition | \(n^r\) |
| Are selections replaced but order irrelevant? | Use combinations with repetition | \(\binom{n+r-1}{r}\) |
| Are unwanted outcomes easier to count? | Count the complement | \(n(S)-n(A^c)\) |
| Is every final outcome counted equally many times? | Divide by that multiplicity | \(N/d\) |
| Are distinct objects split among labelled groups? | Use a multinomial coefficient | \(n!/(n_1!\cdots n_k!)\) |
Before using a formula, describe what would make two outcomes different. If swapping two selected objects creates a new outcome, order matters; otherwise it does not.
Worked applications
The following examples illustrate how the principles combine. Before opening a solution, identify the sample space, decide whether order matters, and write the intended numerator and denominator.
Example — Selecting coins. A purse contains three distinct nickels, one dime, and two distinct quarters. Three coins are selected simultaneously without replacement. What is the probability that their value is at least 35 cents?
Show solution
Because the three coins are selected as a group, order is irrelevant. All \(\binom63=20\) three-coin subsets are equally likely. A total of at least 35 cents requires at least one quarter. Count the complement: among the four non-quarter coins there are \(\binom43=4\) subsets. Hence
\[ \mathbb{P}(\text{at least 35 cents}) =1-\frac{\binom43}{\binom63} =\frac{16}{20}=0.8. \]
This example combines combinations with complement counting.Example — A 6-from-49 lottery. A ticket contains 6 distinct numbers selected from 1 through 49. Find the probability of matching all six winning numbers, and the probability of matching exactly three.
Show solution
There are \(\binom{49}{6}=13{,}983{,}816\) equally likely winning sets. Only one matches all six ticket numbers, so
\[ \mathbb{P}(\text{all six})=\frac{1}{\binom{49}{6}}. \]
To match exactly three, choose 3 of the 6 ticket numbers and 3 of the 43 numbers not on the ticket:
\[ \mathbb{P}(\text{exactly three}) =\frac{\binom63\binom{43}{3}}{\binom{49}{6}} =\frac{246{,}820}{13{,}983{,}816} \approx0.01765. \]
The phrase exactly three requires both parts: three matches and three nonmatches.Example — Full house in poker. Five cards are dealt from a standard 52-card deck. What is the probability of a full house: three cards of one rank and two cards of another rank?
Show solution
There are \(\binom{52}{5}\) possible hands. For a full house:
- choose the rank of the triple: \(13\) ways;
- choose 3 of its 4 suits: \(\binom43\) ways;
- choose a different rank for the pair: \(12\) ways;
- choose 2 of its 4 suits: \(\binom42\) ways.
Therefore
\[ \mathbb{P}(\text{full house}) =\frac{13\binom43\,12\binom42}{\binom{52}{5}} =\frac{3{,}744}{2{,}598{,}960} \approx0.001441. \]
We multiply because all four decisions are required. Choosing the triple rank first prevents double-counting the roles of the two ranks.Example — Two nonstandard dice. One ordinary die and a die with faces \(\{2,3,4,6,7,9\}\) are rolled. What is the probability that their sum is at least 10?
Show solution
The outcome is an ordered pair, one result from each die. There are \(6\times6=36\) equally likely pairs. Counting favorable pairs gives 14, so
\[ \mathbb{P}(\text{sum}\ge10)=\frac{14}{36}=\frac7{18}. \]
This is multiplication rather than a combination: the pair \((3,7)\) identifies results from different dice and is not interchangeable with \((7,3)\).R implementation
## [1] 120## [1] 336## [1] 495## [1] 10000## [1] 12## [1] 3439# multinomial allocation and combinations with repetition
factorial(10) / (factorial(4) * factorial(3) * factorial(3))## [1] 4200## [1] 84## [1] 1 4 6 4 1## [1] 12## [1] 7.151124e-08## [1] 0.0176504## [1] 0.001440576Exercises: general counting rules
Exercise 1 — Travel alternatives. A student can travel from Doha to a conference using 4 direct flights or 3 direct bus services. How many direct travel choices are available?
Show solution to Exercise 1
The flight and bus alternatives are disjoint, so the addition principle gives \(4+3=7\) choices.Exercise 2 — Policy design. An insurer offers 5 coverage limits, 3 deductibles, and 2 payment frequencies. How many policies can be formed by choosing one option of each type?
Show solution to Exercise 2
The three choices are successive components of one policy. The multiplication principle gives \(5\times3\times2=30\) policies.Exercise 3 — Officer assignments. From 10 students, how many ways can a president, vice-president, and treasurer be appointed?
Show solution to Exercise 3
The roles are distinct, so order matters: \[\operatorname{Perm}(10,3)=10\times9\times8=720.\]Exercise 4 — Claims committee. How many five-claim samples can be selected from 20 distinct claims?
Show solution to Exercise 4
Only membership in the sample matters, so \[\binom{20}{5}=15{,}504.\]Exercise 5 — Security code. A code has three distinct letters followed by two distinct digits. How many codes are possible if no character may repeat within its part?
Show solution to Exercise 5
There are \(26\times25\times24\) letter sequences and \(10\times9\) digit sequences. Hence \[26\times25\times24\times10\times9=1{,}404{,}000.\]Exercise 6 — Portfolio selection. A portfolio must contain 3 stocks selected from 8 and 2 bonds selected from 6. How many portfolios are possible?
Show solution to Exercise 6
Order does not matter within either asset class. Choose the stocks and bonds independently: \[\binom{8}{3}\binom{6}{2}=56\times15=840.\]Exercise 7 — At least one claim from Qatar. A database contains 7 claims from Qatar and 13 from other countries. How many five-claim samples contain at least one claim from Qatar?
Show solution to Exercise 7
The complement—selecting all five claims from the 13 other-country claims—is easier to count. Therefore \[\binom{20}{5}-\binom{13}{5}=15{,}504-1{,}287=14{,}217.\]Exercise 8 — Allocating analysts. Twelve analysts are assigned to labelled teams A, B, and C with 5, 4, and 3 analysts respectively. How many assignments are possible?
Show solution to Exercise 8
The teams are labelled and order within a team is irrelevant, so the multinomial principle gives \[\frac{12!}{5!4!3!}=27{,}720.\]Exercise 9 — Repeated asset categories. A six-position portfolio records only how many assets belong to each of five sectors. A sector may be used repeatedly and order is irrelevant. How many sector-count profiles are possible?
Show solution to Exercise 9
This is a combination with repetition: distribute 6 identical positions among 5 sector categories. \[\binom{5+6-1}{6}=\binom{10}{6}=210.\]Exercise 10 — Prescribed digits. How many six-digit sequences contain exactly two 1s, three 4s, and one 7?
Show solution to Exercise 10
The positions are divided among repeated digit types. The multinomial count is \[ \frac{6!}{2!3!1!}=60. \]Exercise 11 — A binomial coefficient. Find the coefficient of \(x^3y^5\) in \((x+y)^8\) and explain its counting meaning.
Show solution to Exercise 11
We choose the 5 of the 8 factors that contribute \(y\); the remaining 3 contribute \(x\). Thus the coefficient is \[ \binom85=\binom83=56. \]Exercise 12 — Exactly four lottery matches. A ticket contains 6 numbers selected from 1 through 49. What is the probability of matching exactly 4 of the 6 winning numbers?
Show solution to Exercise 12
Choose the 4 matching numbers from the 6 ticket numbers and the 2 nonmatching numbers from the other 43: \[ \mathbb{P}(\text{exactly four}) =\frac{\binom64\binom{43}{2}}{\binom{49}{6}} \approx0.0009686. \]Exercise 13 — Claims by type. An audit file contains 8 motor claims, 6 property claims, and 5 health claims. How many seven-claim samples contain exactly 3 motor, 2 property, and 2 health claims?