Discrete Math: Combinations & Permutations Complete Formula Cheat Sheet

What Are Combinations & Permutations?

Combinations and Permutations are fundamental counting principles in discrete mathematics used to determine the number of ways to select or arrange objects from a set. Permutations consider the order of arrangement (ABC ≠ BAC), while Combinations ignore order (ABC = BAC = CAB). These concepts are essential for probability, statistics, computer science algorithms, and solving real-world counting problems.

Core Concepts & Principles

Fundamental Counting Principle

If there are m ways to do one thing and n ways to do another, then there are m × n ways to do both.

Key Distinctions

Essential Terminology

• n: Total number of objects in the set
• r: Number of objects being selected/arranged
• n!: n factorial = n × (n-1) × (n-2) × … × 1
• 0!: Defined as 1 by convention

Core Formulas & Applications

Basic Factorials

Permutation Formulas

1. Permutations of n Distinct Objects

Formula: P(n,n) = n! When to Use: Arranging all objects from a set Example: Ways to arrange 5 books = 5! = 120

2. Permutations of r Objects from n Objects

Formula: P(n,r) = n!/(n-r)! When to Use: Selecting and arranging r objects from n total objects Example: Ways to arrange 3 books from 7 books = 7!/(7-3)! = 7!/4! = 210

3. Permutations with Repetition

Formula: n^r When to Use: Objects can be repeated in arrangements Example: 4-digit PIN codes = 10^4 = 10,000

4. Permutations of Objects with Identical Elements

Formula: n!/(n₁! × n₂! × … × nₖ!) When to Use: Some objects are identical Example: Arrangements of MISSISSIPPI = 11!/(1! × 4! × 4! × 2!) = 34,650

Combination Formulas

1. Combinations of r Objects from n Objects

Formula: C(n,r) = n!/[r!(n-r)!] When to Use: Selecting objects where order doesn’t matter Example: Choose 3 students from 10 = C(10,3) = 120

2. Combinations with Repetition

Formula: C(n+r-1,r) = (n+r-1)!/[r!(n-1)!] When to Use: Objects can be repeated in selections Example: Ways to choose 3 scoops from 5 ice cream flavors = C(7,3) = 35

Step-by-Step Problem Solving Process

Phase 1: Problem Analysis

1. Identify the Question Type

   • Are we arranging (permutation) or selecting (combination)?
   • Does order matter?
   • Can objects be repeated?

2. Define Variables

   • n = total number of objects
   • r = number of objects being selected/arranged

Phase 2: Formula Selection

3. Choose Appropriate Formula

   • Review the formula comparison table
   • Consider special cases (repetition, identical objects)

4. Apply the Formula

   • Substitute values carefully
   • Calculate step by step

Phase 3: Verification

5. Check Your Answer
   • Does the result make logical sense?
   • Try a smaller example to verify approach

Formula Comparison Table

Advanced Techniques & Special Cases

Circular Permutations

Formula: (n-1)! When to Use: Objects arranged in a circle Example: 6 people around a table = (6-1)! = 120

Derangements

Formula: D(n) = n! × Σ(k=0 to n) [(-1)ᵏ/k!] When to Use: Permutations where no object is in its original position Example: 4 people return wrong hats = D(4) = 9

Stirling Numbers of the Second Kind

Formula: S(n,k) = (1/k!) × Σ(j=0 to k) [(-1)^(k-j) × C(k,j) × j^n] When to Use: Ways to partition n objects into k non-empty subsets

Catalan Numbers

Formula: Cₙ = C(2n,n)/(n+1) When to Use: Various combinatorial structures (binary trees, parentheses)

Common Problem Types & Solutions

Type 1: Selection Problems (Combinations)

Keywords: Choose, select, committee, team, group Strategy: Use C(n,r) = n!/[r!(n-r)!]

Example: Choose 5 cards from 52-card deck Solution: C(52,5) = 52!/(5!×47!) = 2,598,960

Type 2: Arrangement Problems (Permutations)

Keywords: Arrange, order, sequence, lineup, rank Strategy: Use P(n,r) = n!/(n-r)!

Example: Arrange 3 books from 8 available books Solution: P(8,3) = 8!/(8-3)! = 8!/5! = 336

Type 3: Restriction Problems

Strategy: Use complementary counting or case-by-case analysis

Example: Arrange 5 people where 2 specific people must sit together Solution: Treat the 2 as one unit: 4! × 2! = 48

Type 4: Distribution Problems

Strategy: Consider whether objects/recipients are distinguishable

Example: Distribute 10 identical balls into 3 distinct boxes Solution: C(10+3-1,3-1) = C(12,2) = 66

Common Challenges & Solutions

Challenge 1: Confusing Permutations vs Combinations

Problem: Students mix up when order matters Solution:

• Ask: “Would swapping two items create a different outcome?”
• If yes → Permutation; If no → Combination

Challenge 2: Factorial Calculation Errors

Problem: Large factorials are difficult to compute Solutions:

• Use factorial properties: n!/k! = n×(n-1)×…×(k+1)
• Cancel common terms before multiplying
• Use calculator or software for large values

Challenge 3: Repetition vs Non-Repetition

Problem: Unclear when repetition is allowed Solution:

• Read problem carefully for keywords like “distinct,” “different,” or “replacement”
• Default assumption is usually no repetition unless stated

Challenge 4: Complex Restriction Problems

Problem: Multiple constraints make direct counting difficult Solutions:

• Use inclusion-exclusion principle
• Break into cases
• Use complementary counting (total – excluded)

Calculation Best Practices

Efficient Computation Methods

1. Cancel Before Multiplying

   C(10,3) = 10!/(3!×7!) = (10×9×8)/(3×2×1) = 120
   

2. Use Symmetry Property

   C(n,r) = C(n,n-r)
   Example: C(20,17) = C(20,3) = 1140
   

3. Pascal’s Triangle Identity

   C(n,r) = C(n-1,r-1) + C(n-1,r)
   

Memory Aids & Patterns

Combination Properties

• C(n,0) = C(n,n) = 1
• C(n,1) = C(n,n-1) = n
• C(n,r) = C(n,n-r)

Permutation Properties

• P(n,0) = 1
• P(n,1) = n
• P(n,n) = n!

Quick Reference Formulas

Essential Formulas Card

Calculator Shortcuts

Real-World Applications

Computer Science Applications

• Algorithm Analysis: Counting sort comparisons
• Cryptography: Key generation and analysis
• Data Structures: Binary tree configurations
• Network Theory: Path counting

Probability & Statistics

• Sample Spaces: Total possible outcomes
• Probability Calculations: Favorable outcomes
• Hypothesis Testing: Combinatorial distributions
• Quality Control: Sampling methods

Business & Economics

• Portfolio Selection: Investment combinations
• Production Planning: Resource allocation
• Market Research: Survey design
• Operations Research: Optimization problems

Practice Problem Categories

Beginner Level

1. Basic factorial calculations
2. Simple permutations and combinations
3. Distinguishing between P and C
4. Small number calculations

Intermediate Level

1. Problems with restrictions
2. Repetition allowed scenarios
3. Circular arrangements
4. Distribution problems

Advanced Level

1. Multiple constraint problems
2. Inclusion-exclusion applications
3. Derangement problems
4. Complex combinatorial structures

Resources for Further Learning

Textbooks & References

• “Discrete Mathematics and Its Applications” by Kenneth Rosen
• “A Walk Through Combinatorics” by Miklos Bona
• “Introductory Combinatorics” by Richard Brualdi

Online Resources

• Khan Academy: Probability and Combinatorics
• MIT OpenCourseWare: Mathematics for Computer Science
• Wolfram MathWorld: Combinatorics section
• OEIS: Online Encyclopedia of Integer Sequences

Practice Platforms

• Art of Problem Solving (AoPS): Competition math problems
• Project Euler: Mathematical programming challenges
• Brilliant.org: Interactive combinatorics courses
• Coursera/edX: Discrete mathematics courses

Software Tools

• Wolfram Alpha: Formula verification and calculation
• Python: Combinatorics libraries (math, itertools)
• R: Statistical computing with combinatorial functions
• MATLAB: Mathematical computing platform

This comprehensive cheat sheet provides all essential formulas, techniques, and problem-solving strategies for mastering combinations and permutations in discrete mathematics.