What are Factorials?
- \( n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1 \), for \( n \geq 1 \).
- Convention: \( 0! = 1 \).
- Example: \( 5! = 120 \), \( 6! = 720 \).
- Counts the number of ways to order \( n \) distinct objects.
Counting Principle
- If task A can be done in \( m \) ways and for each, task B can be done in \( n \) ways, then A then B can be done in \( m \cdot n \) ways.
- For several independent steps, multiply the number of options for each step.
Permutations vs Combinations
| Feature | Permutation | Combination |
|---|---|---|
| Order matters? | Yes | No |
| Formula | \( P(n, k) = \frac{n!}{(n-k)!} \) | \( C(n, k) = \frac{n!}{k!(n-k)!} \) |
| Example | 3-letter arrangements from 4: \( P(4,3) = 24 \) | 2-person committees from 5: \( C(5,2) = 10 \) |
| Relation | \( P(n,k) = C(n,k) \cdot k! \) | |
Key Formulas & Identities
- \( n! \): arrangements of \( n \) distinct objects
- \( P(n, k) = \frac{n!}{(n-k)!} \)
- \( C(n, k) = \frac{n!}{k!(n-k)!} \)
- Symmetry: \( C(n, k) = C(n, n-k) \)
- Pascal identity: \( C(n, k) = C(n-1, k-1) + C(n-1, k) \)
- Relation: \( P(n, k) = C(n, k) \cdot k! \)
Arranging People: Standard Cases
- No restrictions: \( n! \) ways. Example: 6 people → \( 6! = 720 \).
- Alternate seating (equal boys/girls): \( 2 \cdot m! \cdot m! \) ways. Example: 5 boys & 5 girls → \( 2 \cdot 5! \cdot 5! = 28,800 \).
- Two together: \( (n-1)! \cdot 2 \). Example: 6 people, A & B together → \( 5! \cdot 2 = 240 \).
- Three together: \( (n-2)! \cdot 3! \). Example: 6 people, A,B,C together → \( 4! \cdot 6 = 144 \).
- Boy–girl couples (fixed): \( 5! \cdot 2^5 = 3,840 \).
- Boy–girl couples (any pairing): \( 5! \cdot 5! \cdot 2^5 = 460,800 \).
- Two not together: \( n! - (n-1)! \cdot 2 \). Example: 6 people, A & B not adjacent → \( 720 - 240 = 480 \).
Binomial Theorem & Pascal's Triangle
Pascal's Triangle (Rows
0–4)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
- Binomial coefficients: \( C(n, k) \) = entry in row \( n \), position \( k \).
- Coefficients of \( (a+b)^n \) are row \( n \) of Pascal's triangle.
Binomial Theorem (Expansion Formula)
- General: \( (a+b)^n = \sum_{k=0}^n C(n,k) a^{n-k} b^k \)
- General term: \( T_{k+1} = C(n,k) a^{n-k} b^k \)
- Example: \( (x+2)^3 = x^3 + 6x^2 + 12x + 8 \)
Finding Particular Terms & Degrees
- General term in \( (x+1)^n \): \( T_{k+1} = C(n,k) x^{n-k} \)
- Term with \( x^r \): set \( k = n-r \).
- Example: coefficient of \( x^3 \) in \( (x+1)^5 \): \( k=2 \), coefficient = \( C(5,2) = 10 \).
- Constant term: \( k=n \), coefficient = 1.
- General term in \( (x^3+x^2)^n \): \( T_{k+1} = C(n,k) x^{3n-k} \)
- To find \( x^r \): solve \( 3n-k = r \Rightarrow k=3n-r \).
- Example: term with \( x^{10} \) in \( (x^3+x^2)^5 \): \( k=5 \), coefficient = \( C(5,5) = 1 \).