AcademyProbability
Academy
Counting Principles
Level 1 - Math II (Physics) topic page in Probability.
Principle
Counting principles find how many outcomes an event contains before probabilities are assigned. The main decision is whether order matters and whether repeated choices are allowed.
Notation
\(n!\)
factorial: n(n-1)(n-2)...1 for a non-negative integer n, with 0!=1
\({}^nP_r\)
permutations: ordered selections of r objects from n
\(\binom{n}{r}\)
combinations: unordered selections of r objects from n
\(\binom{n}{n_1,n_2,\ldots,n_k}\)
multinomial coefficient for groups of sizes n_1 through n_k
\(n_1+\cdots+n_k=n\)
the group sizes add to the total number of objects
Method
Step 1: Decide whether choices are sequential
If a process has stages, multiply the number of options at each stage.
Step 2: Decide whether order matters
Role assignments, codes, and routes usually have order. Committees and hands of cards are usually unordered.
Step 3: Decide whether repeats are allowed
Rolling dice allows repeated values. Arranging distinct objects without replacement does not.
Step 4: Choose the formula
Use permutations for ordered selections without replacement, combinations for unordered selections, and multinomial coefficients for arranging repeated groups.
Ordered without replacement
\[n(n-1)\cdots(n-r+1)=\frac{n!}{(n-r)!}\]
Remove ordering from r selected objects
\[\binom{n}{r}=\frac{{}^nP_r}{r!}=\frac{n!}{r!(n-r)!}\]
Repeated groups
\[\binom{n}{n_1,n_2,\ldots,n_k}=\frac{n!}{n_1!n_2!\cdots n_k!}\]
Rules
Multiplication principle
\[N=N_1N_2\cdots N_k\]
Permutation
\[{}^nP_r=\frac{n!}{(n-r)!}\]
Combination
\[\binom{n}{r}=\frac{n!}{r!(n-r)!}\]
Multinomial
\[\binom{n}{n_1,n_2,\ldots,n_k}=\frac{n!}{n_1!n_2!\cdots n_k!}\]
The multinomial denominator contains one factorial for each group size.
Examples
Question
A signal can travel through 3 first-stage routes and then 4 second-stage routes. How many two-stage routes are possible?
Answer
Use the multiplication principle:
\[3\cdot4=12.\]
Checks
- Cards dealt into a hand are unordered unless positions or roles are specified.
- Role assignments are ordered because president then secretary differs from secretary then president.
- Factorial arguments must be non-negative integers.
- Do not divide by \(r!\) when the order of the selected objects matters.