Combinatorics Overview

Overview

This lecture introduces combinatorics, focusing on methods to count and arrange objects, including permutations, arrangements, and combinations, with and without repetition.

Introduction to Combinatorics

• Combinatorics studies how many ways objects from a set can be arranged or selected.
• Combinatorial calculus is the math branch dealing with arrangements of collections.

Simple Permutations

• A simple permutation arranges n distinct objects in n boxes: the total ways is n × (n-1) × ... × 1 = n! (n factorial).
• For 4 objects, simple permutations = 4! = 24.
• Example: All possible anagrams of "Rome" (4 letters) total 24.

Permutations with Repetition

• When identical objects are present, divide total permutations by the factorial of identical object counts.
• Formula: n! / (k₁! × k₂! × ... × kᵣ!), where k₁, k₂ ... are the number of identical objects of each type.
• Example: For 7 balls (1 blue, 1 green, 3 purple, 2 orange), permutations = 7! / (3! × 2!) = 420.
• Example: "MAMMA" anagrams = 5! / (3! × 2!) = 10.

Simple Arrangements (Arrangements without Repetition)

• Arrangements (denoted Dₙₖ) of n objects in k boxes, order matters: Dₙₖ = n × (n-1) × ... × (n-k+1).
• Simplified: Dₙₖ = n! / (n-k)!.
• Example: For "ROME", arranging 2 out of 4 letters: D₄₂ = 4! / 2! = 12.

Simple Combinations

• Combinations count groups of k objects chosen from n, order does not matter.
• Formula: Cₙₖ = Dₙₖ / k! = n! / (k! × (n-k)!).
• The result Cₙₖ is called the binomial coefficient ("n choose k").
• Example: "ROME", 2-letter combinations = 12 / 2 = 6.

Arrangements with Repetition

• Arrangements with repetition allow objects to be reused: number of ways is nᵏ.
• Example: 4 marbles in 3 boxes, each marble can be chosen again: total = 4³ = 64.
• For "ROME", 2-letter arrangements with repetition = 4² = 16.

Key Terms & Definitions

• Permutation — an arrangement of all the elements of a set.
• Factorial (n!) — product of all positive integers up to n.
• Permutation with repetition — arrangement where some objects repeat, accounting for identical items.
• Arrangement (Disposition) — ordered selection of k objects from n without reuse.
• Combination — selection of k objects from n where order does not matter.
• Binomial coefficient (Cₙₖ) — the number of ways to choose k objects from n, not considering order.

Action Items / Next Steps

• Practice problems: Calculate permutations, arrangements, and combinations for different n and k values.
• Review definitions and formulas for factorial, arrangements, and combinations.