New Notes

Definition of Factorial

• Factorial Notation:
  • Represented by n!n!, where nn is a non-negative integer.
  • Defined as the product of all positive integers from nn down to 11: n!=n×(n−1)×(n−2)×…×1n! = n times (n-1) times (n-2) times ldots times 1
  • Special case: 0!=10! = 1 This is a convention used to maintain consistency in mathematical formulas.

---

Examples of Factorials

1. Basic Calculations:
   • 5!=5×4×3×2×1=1205! = 5 times 4 times 3 times 2 times 1 = 120
   • 3!=3×2×1=63! = 3 times 2 times 1 = 6
2. Worked Examples:
   • Calculate 8!/3!8! / 3!: 8!=8×7×6×5×4×3×2×18! = 8 times 7 times 6 times 5 times 4 times 3 times 2 times 1 8!3!=8×7×6×5×4×3!3!=8×7×6×5×4=6720frac{8!}{3!} = frac{8 times 7 times 6 times 5 times 4 times 3!}{3!} = 8 times 7 times 6 times 5 times 4 = 6720

---

Key Properties of Factorials

1. Recursive Formula:
   • Any factorial can be expressed in terms of the previous factorial: n!=n×(n−1)!n! = n times (n-1)!
2. Division of Factorials:
   • Simplification of expressions involving factorials: n!(n−k)!=n×(n−1)×…×(n−k+1)frac{n!}{(n-k)!} = n times (n-1) times ldots times (n-k+1)
   • Example: 7!5!=7×6=42frac{7!}{5!} = 7 times 6 = 42
3. Combination with Factorials:
   • Often used in permutations and combinations, where: (nr)=n!r!(n−r)!binom{n}{r} = frac{n!}{r!(n-r)!}

---

Applications of Factorials

1. Permutations:
   • The arrangement of nn items in sequence: P(n,r)=n!(n−r)!P(n, r) = frac{n!}{(n-r)!}
   • Example:
     • Number of ways to arrange 3 items out of 5: P(5,3)=5!(5−3)!=5×4×3×2×12×1=60P(5, 3) = frac{5!}{(5-3)!} = frac{5 times 4 times 3 times 2 times 1}{2 times 1} = 60
2. Combinations:
   • Selection of rr items from nn without regard to order: C(n,r)=n!r!(n−r)!C(n, r) = frac{n!}{r!(n-r)!}
   • Example:
     • Number of ways to choose 2 items from 4: C(4,2)=4!2!×(4−2)!=4×3×2×12×1×2×1=6C(4, 2) = frac{4!}{2! times (4-2)!} = frac{4 times 3 times 2 times 1}{2 times 1 times 2 times 1} = 6

---

Challenges with Large Factorials

• Factorials grow rapidly with nn, making them computationally intensive for large values.
• Examples:
  • 10!=3,628,80010! = 3,628,800
  • 20!=2,432,902,008,176,640,00020! = 2,432,902,008,176,640,000

---

Practical Problems and Solutions

1. Simplification:
   • To simplify large factorials, cancel common terms when dividing: n!(n−k)!=n×(n−1)×…×(n−k+1)frac{n!}{(n-k)!} = n times (n-1) times ldots times (n-k+1)
2. Factorial Representation:
   • Factorials can also be expressed in terms of repeated calculations: n!=n×(n−1)!n! = n times (n-1)!
3. Using Factorials in Binomial Expansions:
   • The coefficients in binomial expansion: (a+b)n=∑r=0n(nr)an−rbr(a+b)^n = sum_{r=0}^{n} binom{n}{r} a^{n-r} b^r

---

Worked Problems

Example 1: Factorial Simplification

Simplify:

9!7!frac{9!}{7!}

• Solution: Expand the factorials: 9!7!=9×8×7!7!=9×8=72frac{9!}{7!} = frac{9 times 8 times 7!}{7!} = 9 times 8 = 72

Example 2: Combination Problem

Find the number of ways to choose 3 items from 6 items.

• Solution: Use the combination formula: C(6,3)=6!3!×(6−3)!=6×5×43×2×1=20C(6, 3) = frac{6!}{3! times (6-3)!} = frac{6 times 5 times 4}{3 times 2 times 1} = 20

---

Exercises for Practice

1. Calculate the following:
   • 5!5!, 8!8!, 10!10!
2. Simplify:
   • 10!8!frac{10!}{8!}, 12!10!frac{12!}{10!}
3. Solve for nn:
   • n!(n−3)!=120frac{n!}{(n-3)!} = 120
4. Find the number of permutations of 4 items from 7:
   • P(7,4)P(7, 4)
5. Compute the number of combinations of 5 items from 10:
   • C(10,5)C(10, 5)

---

Conclusion

• Factorial notation simplifies the expression of large products.
• Widely used in probability, statistics, and algebra for permutations and combinations.
• Mastery of factorial properties and simplifications is critical for solving advanced mathematical problems.

Introduction to Arrangements

• Arrangements involve organizing a set of distinct items in a specific order.
• The concept of arrangements is a fundamental part of permutations in mathematics.
• Order of items is critical in arrangements; changing the order creates a different arrangement.

---

Key Concepts

Factorial Notation in Arrangements

• The total number of arrangements of nn distinct items in a line is given by: n!=n×(n−1)×(n−2)×…×1n! = n times (n-1) times (n-2) times ldots times 1
  • Example:
    • For 4 items: 4!=4×3×2×1=244! = 4 times 3 times 2 times 1 = 24

Arranging a Subset of Items

• To arrange rr items from nn distinct items, use the formula: P(n,r)=n!(n−r)!P(n, r) = frac{n!}{(n-r)!}
  • Example:
    • For 3 items selected from 5: P(5,3)=5!(5−3)!=5×4×3×2×12×1=60P(5, 3) = frac{5!}{(5-3)!} = frac{5 times 4 times 3 times 2 times 1}{2 times 1} = 60

---

Worked Examples

Example 1: Basic Arrangement

• Find the number of ways to arrange 3 books labeled AA, BB, and CC on a shelf.Solution:
  • Using the factorial method: 3!=3×2×1=63! = 3 times 2 times 1 = 6
  • Arrangements: ABC,ACB,BAC,BCA,CAB,CBAABC, ACB, BAC, BCA, CAB, CBA.

Example 2: Arranging Subsets

• Find the number of ways to arrange 2 letters from A,B,C,DA, B, C, D.Solution:
  • Using the formula P(n,r)P(n, r): P(4,2)=4!(4−2)!=4×3×2×12×1=12P(4, 2) = frac{4!}{(4-2)!} = frac{4 times 3 times 2 times 1}{2 times 1} = 12

---

Applications of Arrangements

Arranging Items with Restrictions

• Sometimes arrangements involve specific conditions, such as fixing the position of one or more items.

Worked Example with Restrictions:

• Arrange the letters A,B,C,DA, B, C, D such that AA is always at the start.
  • Fix AA in the first position, then arrange B,C,DB, C, D: 3!=63! = 6
  • Total arrangements: ABCD,ABDC,ACBD,ACDB,ADBC,ADCBABCD, ABDC, ACBD, ACDB, ADBC, ADCB.

---

Special Cases in Arrangements

Items with Repetition

• If items are repeated, divide the total arrangements by the factorial of the repeated items: Total Arrangements=n!k1!⋅k2!⋅…text{Total Arrangements} = frac{n!}{k_1! cdot k_2! cdot ldots}
  • Example:
    • For the word MISSISSIPPIMISSISSIPPI: Total Letters=11,M=1, I=4, S=4, P=2text{Total Letters} = 11, quad M=1, , I=4, , S=4, , P=2 Arrangements=11!1!⋅4!⋅4!⋅2!text{Arrangements} = frac{11!}{1! cdot 4! cdot 4! cdot 2!}

Circular Arrangements

• For nn items in a circle: Total Arrangements=(n−1)!text{Total Arrangements} = (n-1)!

---

Practice Problems

1. Basic Factorial Calculation:
   • Find 5!5! and 7!7!.
2. Subsets of Arrangements:
   • Calculate P(6,3)P(6, 3).
3. Word Arrangements:
   • How many ways can the letters of BANANABANANA be arranged?
4. Restricted Arrangements:
   • In how many ways can 5 people sit if two specific people must sit together?

---

Summary

• Arrangements are the ordered organization of items, governed by factorial notation and permutation formulas.
• Key distinctions include handling repetitions and applying restrictions.
• Practice builds familiarity with scenarios like arranging subsets or solving problems with restrictions.

Definition of Permutations

• Permutations:
  • The arrangement of a set of items where the order matters.
  • Example: The arrangements of the letters A,B,CA, B, C are ABC,BAC,CAB,ACB,BCA,CBAABC, BAC, CAB, ACB, BCA, CBA.
• Notation:
  • Represented as P(n,r)P(n, r) or nPr^nP_r.
  • nn: Total number of items.
  • rr: Number of items to arrange.
• Formula for Permutations:P(n,r)=n!(n−r)!P(n, r) = frac{n!}{(n – r)!}
  • n!n!: The factorial of nn, defined as n×(n−1)×⋯×1n times (n – 1) times dots times 1.
  • (n−r)!(n – r)!: Factorial of the difference between nn and rr.

---

Properties of Factorials

1. Base Case:
   • 0!=10! = 1: This is a convention to simplify factorial-based formulas.
   • Explanation: A single item has exactly one way to be selected.
2. Simplification:
   • For any integer n>0n > 0: n!=n×(n−1)!n! = n times (n – 1)!

---

Worked Examples

Example 1: Calculating Permutations

Find the number of permutations of 3 items from a total of 8.

• Solution:
  • Using the formula: P(8,3)=8!(8−3)!=8×7×6×5!5!P(8, 3) = frac{8!}{(8 – 3)!} = frac{8 times 7 times 6 times 5!}{5!}
  • Cancel 5!5!: P(8,3)=8×7×6=336P(8, 3) = 8 times 7 times 6 = 336

---

Example 2: Permutations of All Items

Find the number of ways to arrange 6 items.

• Solution:
  • Since all items are being arranged: P(6,6)=6!(6−6)!=6!0!=6!P(6, 6) = frac{6!}{(6 – 6)!} = frac{6!}{0!} = 6!
  • Calculate: 6!=6×5×4×3×2×1=7206! = 6 times 5 times 4 times 3 times 2 times 1 = 720

---

Special Cases in Permutations

Case 1: Repeated Items

• If there are repeated items, divide by the factorial of the number of repetitions to avoid overcounting.
• Formula:Permutations with Repetition=n!p1!×p2!×⋯×pk!text{Permutations with Repetition} = frac{n!}{p_1! times p_2! times dots times p_k!}
  • p1,p2,…,pkp_1, p_2, dots, p_k: Number of repeated items in each group.
• Example:
  • Arrange the letters of “AAB”.
  • Total letters = 3, repeated AA = 2.
  • Permutations: 3!2!=62=3 (AAB, ABA, BAA).frac{3!}{2!} = frac{6}{2} = 3 , (text{AAB, ABA, BAA}).

---

Case 2: Circular Permutations

• For items arranged in a circle:Permutations=(n−1)!text{Permutations} = (n – 1)!
• Example:
  • Arrange 4 people in a circle: Permutations=(4−1)!=3!=6.text{Permutations} = (4 – 1)! = 3! = 6.

---

Applications of Permutations

1. Codes and Passwords:
   • Used to calculate possible combinations of codes.
   • Example:
     • A password consists of 3 letters chosen from A,B,C,D,EA, B, C, D, E, followed by 2 digits chosen from 1,2,3,4,51, 2, 3, 4, 5.
     • Total permutations: P(5,3)×P(5,2)=60×20=1200.P(5, 3) times P(5, 2) = 60 times 20 = 1200.
2. Seating Arrangements:
   • Calculating arrangements of people in rows or around tables.

---

Common Mistakes in Permutations

1. Misidentifying Order:
   • Ensure that the problem specifies the order of arrangement for permutations.
   • Example: Arranging books on a shelf (order matters).
2. Confusing with Combinations:
   • Permutations consider the arrangement order, while combinations do not.
3. Handling Repeated Items:
   • Always divide by factorials of repeated items to avoid overcounting.

---

Exercises

1. Find the number of permutations:
   • P(7,4)P(7, 4),
   • P(10,3)P(10, 3),
   • Arrange 6 books on a shelf.
2. A security code consists of 2 letters followed by 3 digits. How many codes can be generated if:
   • No repetition is allowed?
   • Letters and digits can repeat?
3. Find the number of arrangements of the letters in “BANANA”.

---

Summary

• Permutations involve arranging items where order matters.
• Formula: P(n,r)=n!(n−r)!P(n, r) = frac{n!}{(n – r)!}
• Applications range from seating arrangements to generating codes and solving complex counting problems.

Introduction

• Combinations:
  • A way to select items from a group where the order of selection does not matter.
  • Commonly used in problems where arrangement or sequence is irrelevant.
• Key Difference from Permutations:
  • In permutations, the arrangement matters.
  • In combinations, only the selection matters.

---

General Formula for Combinations

1. Formula:C(n,r)=n!r!⋅(n−r)!C(n, r) = frac{n!}{r! cdot (n-r)!}
   • C(n,r)C(n, r): Number of combinations (read as “n choose r”).
   • n!n!: Factorial of the total number of items.
   • r!r!: Factorial of the selected items.
   • (n−r)!(n-r)!: Factorial of the remaining items.
2. Properties:
   • C(n,r)=C(n,n−r)C(n, r) = C(n, n-r): Choosing rr items from nn is the same as leaving n−rn-r items out.
   • C(n,0)=1C(n, 0) = 1: There is only one way to choose nothing.
   • C(n,n)=1C(n, n) = 1: There is only one way to choose all items.

---

Worked Examples

Example 1: Basic Combination

• Find the number of ways to choose 3 items from 5 items.
  • Solution: C(5,3)=5!3!⋅(5−3)!=1206⋅2=10C(5, 3) = frac{5!}{3! cdot (5-3)!} = frac{120}{6 cdot 2} = 10

Example 2: Team Selection

• A team of 4 is chosen from 6 players. Find the total number of teams.
  • Solution: C(6,4)=6!4!⋅2!=72024⋅2=15C(6, 4) = frac{6!}{4! cdot 2!} = frac{720}{24 cdot 2} = 15

Example 3: Complement Property

• Verify C(10,3)=C(10,7)C(10, 3) = C(10, 7).
  • Solution:
    • C(10,3)=10!3!⋅7!=120C(10, 3) = frac{10!}{3! cdot 7!} = 120.
    • C(10,7)=10!7!⋅3!=120C(10, 7) = frac{10!}{7! cdot 3!} = 120.

---

Applications of Combinations

1. Selecting Groups

• Problem:
  • A committee of 5 people is to be chosen from 10 members. How many ways can this be done?
  • Solution: C(10,5)=10!5!⋅5!=252C(10, 5) = frac{10!}{5! cdot 5!} = 252

2. Subset Selection

• Problem:
  • How many subsets of size 3 can be formed from a set of 7 items?
  • Solution: C(7,3)=7!3!⋅4!=35C(7, 3) = frac{7!}{3! cdot 4!} = 35

3. Combinatorial Proofs

• Property:
  • Show that C(n,r)+C(n,r+1)=C(n+1,r+1)C(n, r) + C(n, r+1) = C(n+1, r+1).
  • Proof: Expand the combinations using factorials and verify equality.

---

Special Cases in Combinations

1. Zero and All Selection:
   • C(n,0)=1C(n, 0) = 1: Only one way to choose nothing.
   • C(n,n)=1C(n, n) = 1: Only one way to choose everything.
2. Repetition in Selection:
   • When items can be repeated, a different formula is used (not covered under simple combinations).

---

Advanced Examples

Example 4: Conditional Selection

• A group of 7 includes 4 men and 3 women. Find the number of ways to choose 2 men and 2 women.
  • Solution: C(4,2)⋅C(3,2)=4!2!⋅2!⋅3!2!⋅1!=6⋅3=18C(4, 2) cdot C(3, 2) = frac{4!}{2! cdot 2!} cdot frac{3!}{2! cdot 1!} = 6 cdot 3 = 18

Example 5: Combined Groups

• A committee of 5 is formed from 6 doctors and 4 engineers. Find the number of ways if at least 3 must be engineers.
  • Solution:
    • Case 1: 3 engineers, 2 doctors: C(4,3)⋅C(6,2)=4⋅15=60C(4, 3) cdot C(6, 2) = 4 cdot 15 = 60
    • Case 2: 4 engineers, 1 doctor: C(4,4)⋅C(6,1)=1⋅6=6C(4, 4) cdot C(6, 1) = 1 cdot 6 = 6
    • Total: 60+6=6660 + 6 = 66

---

Visual Representation

• Use Pascal’s triangle for combinations:
  • Each row corresponds to nn.
  • Each entry is C(n,r)C(n, r).
  • Example for n=4n = 4: C(4,0),C(4,1),C(4,2),C(4,3),C(4,4)=1,4,6,4,1C(4, 0), C(4, 1), C(4, 2), C(4, 3), C(4, 4) = 1, 4, 6, 4, 1

---

Practice Problems

1. Calculate:
   • C(8,3)C(8, 3),
   • C(12,5)C(12, 5).
2. Solve:
   • How many ways can 4 books be chosen from 10 books?
   • How many groups of 3 students can be formed from a class of 15?
3. Prove:
   • C(n,r)=C(n,n−r)C(n, r) = C(n, n-r).
   • ∑r=0nC(n,r)=2nsum_{r=0}^{n} C(n, r) = 2^n.

---

Summary

• Combinations provide a systematic way to count selections without considering the order.
• The formula: C(n,r)=n!r!⋅(n−r)!C(n, r) = frac{n!}{r! cdot (n-r)!} simplifies calculations and supports real-world problem-solving in grouping and selections.
• Mastery of combinations requires understanding their properties and relationships, such as symmetry and Pascal’s triangle.