Combinations without repetition are a crucial concept in counting problems. They help us determine how many ways we can select items from a group when order doesn't matter. This topic builds on permutations, but focuses on selection rather than arrangement.

Understanding combinations is key for solving real-world problems in fields like probability, statistics, and genetics. We'll explore how to calculate combinations using formulas and tools like Pascal's Triangle, and compare them to permutations to grasp their unique properties.

Combinations and their characteristics

Definition and Key Properties

• Combinations select objects from a set without regard to order
• Each object can be selected only once, with no repetitions allowed
• Number of combinations always less than or equal to permutations for the same set
• Used to determine ways to select a subset from a larger set without order consideration
• Notation represented as C(n,r) or (n choose r)
  • n represents total number of objects
  • r represents number of objects chosen
• Form the basis for many advanced concepts in probability theory, statistics, and combinatorics

Examples and Applications

• Selecting a committee of 3 people from a group of 10 (120 possible combinations)
• Choosing 5 cards from a standard 52-card deck (2,598,960 possible combinations)
• Picking winning lottery numbers (6 numbers from 49 in many lotteries)
• Fundamental in calculating probabilities of events in games of chance
• Used in biology for studying genetic combinations and population diversity
• Applied in chemistry for molecular structure analysis and reaction possibilities

Combinations using binomial coefficients

Calculating Combinations

• Binomial coefficient C(n,r) or (n choose r) represents number of ways to choose r objects from n objects
• Formula for calculating combinations $C(n,r) = \frac{n!}{r!(n-r)!}$
• Binomial coefficient symmetric property $C(n,r) = C(n, n-r)$
• Can be expressed as a product of factors $C(n,r) = \frac{n * (n-1) * ... (n-r+1)}{r!}$
• For large n and r values, use logarithms or specialized algorithms to avoid overflow errors

Pascal's Triangle and Binomial Coefficients

• Pascal's Triangle generates binomial coefficients
• Each number sum of two numbers directly above it
• Rows of Pascal's Triangle correspond to n in C(n,r)
• Positions in each row correspond to r
• Example: Row 4 of Pascal's Triangle (1, 4, 6, 4, 1)
  • Represents C(4,0), C(4,1), C(4,2), C(4,3), C(4,4)
• Useful for quickly finding small binomial coefficients

Permutations vs Combinations

Key Differences

• Permutations involve arrangements where order matters
• Combinations involve selections where order doesn't matter
• Number of permutations always greater than or equal to combinations for same set
• Permutation formula includes factorial in numerator only
• Combination formula has factorials in both numerator and denominator
• Relationship between permutations and combinations $P(n,r) = C(n,r) r!$

Problem-Solving Indicators

• Key phrases in word problems indicate permutation or combination
• Permutation indicators
  • "arrange" (arrange books on a shelf)
  • "order" (order of finish in a race)
  • "sequence" (possible PIN combinations)
• Combination indicators
  • "select" (select committee members)
  • "choose" (choose lottery numbers)
  • "group" (group students for a project)
• Example scenarios
  • Permutation: Arranging 5 people in a line (120 ways)
  • Combination: Selecting 3 people from a group of 5 for a committee (10 ways)

Applications of combinations

Probability and Statistics

• Calculate number of ways to select a sample from a population
• Fundamental in calculating binomial probabilities
  • Number of ways to choose successes from fixed number of trials
• Used in survey sampling, experimental design, and hypothesis testing
• Essential for polynomial expansion coefficients using binomial theorem
• Applied in calculating probabilities in games of chance (poker hands, lottery odds)
• Used in statistical inference and confidence interval calculations

Other Fields and Applications

• Computer Science
  • Algorithms for generating all possible subsets of a set
  • Applications in cryptography and optimization problems
  • Used in analysis of algorithm complexity
• Genetics
  • Calculate probability of inheriting certain traits
  • Study allele frequencies in population genetics
  • Analyze genetic diversity and mutation possibilities
• Chemistry
  • Determine possible molecular structures
  • Analyze potential reaction pathways
• Economics
  • Portfolio selection in financial mathematics
  • Game theory and strategic decision-making models