Combinations are a fundamental concept in probability and statistics, helping us count and analyze different ways to select items from a group. They're essential for calculating probabilities in various scenarios, from lotteries to quality control.

Understanding combinations allows us to solve complex problems involving selection without order. This knowledge is crucial for tackling real-world applications in sampling, data analysis, and decision-making processes across multiple fields.

Fundamental counting principle

• The fundamental counting principle is a foundational concept in combinatorics that helps determine the total number of possible outcomes or arrangements in a given situation
• It states that if there are $n_1$ ways to perform a first task, $n_2$ ways to perform a second task, and so on up to $n_k$ ways to perform the $k$-th task, then there are $n_1 \times n_2 \times \ldots \times n_k$ ways to perform all $k$ tasks together

Multiplication rule

• The multiplication rule is a direct application of the fundamental counting principle
• It is used when there are multiple independent events or choices, and the total number of possible outcomes is the product of the number of possibilities for each event or choice
  • For example, if there are 3 types of pizza crusts and 5 types of toppings, the total number of possible pizza combinations is $3 \times 5 = 15$

Permutations vs combinations

• Permutations and combinations are two important counting techniques that arise from the fundamental counting principle
• Permutations consider the order of elements, while combinations do not
  • For example, when arranging the letters "A", "B", and "C", the permutations "ABC" and "ACB" are considered different, while the combination "A, B, C" is the same as "A, C, B"

Combinations formula

• The combinations formula is used to calculate the number of ways to choose $r$ items from a set of $n$ items, where the order of selection does not matter
• The formula is denoted as $\binom{n}{r}$ or $C(n, r)$ and is calculated as $\frac{n!}{r!(n-r)!}$, where $n!$ represents the factorial of $n$

Binomial coefficients

• Binomial coefficients, also known as "n choose r", are the coefficients that appear in the expansion of the binomial $(x + y)^n$
• They are equivalent to the number of combinations of $n$ items taken $r$ at a time and are denoted as $\binom{n}{r}$

Factorials in combinations

• Factorials play a crucial role in the combinations formula
• The factorial of a non-negative integer $n$, denoted as $n!$, is the product of all positive integers less than or equal to $n$
  • For example, $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$

Choosing r from n

• "Choosing r from n" is another way to describe the process of selecting $r$ items from a set of $n$ items, where the order of selection does not matter
• This is precisely what the combinations formula calculates
  • For example, choosing 2 students from a group of 5 to form a committee can be calculated using $\binom{5}{2} = \frac{5!}{2!(5-2)!} = 10$

Combinations with repetition

• Combinations with repetition, also known as multicombinations, involve selecting items from a set where each item can be chosen multiple times
• The formula for combinations with repetition is $\binom{n+r-1}{r}$, where $n$ is the number of distinct items and $r$ is the number of items being chosen

Multisets

• A multiset is a collection of items where duplicates are allowed
• Combinations with repetition can be thought of as counting the number of multisets of size $r$ that can be formed from a set of $n$ distinct elements
  • For example, if we have the letters "A", "B", and "C", and we want to create 3-letter combinations with repetition, some possible multisets are "AAA", "ABB", and "ACC"

Combinations with unlimited repetition

• In some cases, there may be no limit to the number of times an item can be repeated in a combination
• The formula for combinations with unlimited repetition is $\binom{n+r-1}{r}$, where $n$ is the number of distinct items and $r$ is the number of items being chosen
  • For example, if we have 3 types of fruits and want to create a 5-piece fruit basket with unlimited repetition, we can calculate the number of possible combinations using $\binom{3+5-1}{5} = \binom{7}{5} = 21$

Probability using combinations

• Combinations are often used in probability calculations when the order of events or selections does not matter
• The probability of a specific combination occurring can be found by dividing the number of favorable combinations by the total number of possible combinations

Probability of combinations

• To find the probability of a specific combination occurring, first calculate the number of favorable combinations using the combinations formula
• Then, divide this number by the total number of possible combinations
  • For example, if we have a standard 52-card deck and want to find the probability of drawing 2 hearts from 5 cards, we can calculate $\frac{\binom{13}{2} \times \binom{39}{3}}{\binom{52}{5}} \approx 0.1314$

Combinations in probability formulas

• Many probability formulas involve combinations, particularly when dealing with independent events or sampling without replacement
• The hypergeometric distribution, which models the probability of obtaining a specific number of successes in a fixed number of draws from a population without replacement, uses combinations in its probability mass function
  • The formula is $P(X = k) = \frac{\binom{K}{k} \times \binom{N-K}{n-k}}{\binom{N}{n}}$, where $N$ is the population size, $K$ is the number of successes in the population, $n$ is the number of draws, and $k$ is the number of successes in the drawn sample

Combinations in binomial expansion

• The binomial theorem is a formula that expands powers of binomial expressions, such as $(x + y)^n$
• Combinations play a crucial role in the binomial expansion, as they determine the coefficients of each term in the expanded expression

Binomial theorem

• The binomial theorem states that for any real numbers $x$ and $y$ and any non-negative integer $n$, the expansion of $(x + y)^n$ is given by:
  • $(x + y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k = \binom{n}{0} x^n y^0 + \binom{n}{1} x^{n-1} y^1 + \ldots + \binom{n}{n} x^0 y^n$

Pascal's triangle

• Pascal's triangle is a triangular array of numbers in which each number is the sum of the two numbers directly above it
• The numbers in Pascal's triangle are the binomial coefficients $\binom{n}{k}$, where $n$ represents the row number (starting from 0) and $k$ represents the position within the row (also starting from 0)
  • For example, the fourth row of Pascal's triangle (1, 4, 6, 4, 1) contains the binomial coefficients for the expansion of $(x + y)^4$

Combinations as coefficients

• In the binomial expansion, the coefficients of each term are the combinations $\binom{n}{k}$, where $n$ is the power of the binomial and $k$ is the exponent of the second variable ($y$)
• These coefficients determine the number of ways to choose $k$ items from $n$ items, which corresponds to the number of ways to select the second variable ($y$) in each term of the expansion
  • For example, in the expansion of $(x + y)^5$, the term $\binom{5}{2} x^3 y^2$ has a coefficient of $\binom{5}{2} = 10$, meaning there are 10 ways to choose 2 $y$'s from the 5 total variables

Combinations in real-world applications

• Combinations have numerous real-world applications in various fields, including probability, statistics, and combinatorics
• They are used to solve problems involving counting, sampling, and probability calculations

Lotteries and combinations

• Lotteries often involve selecting a combination of numbers from a larger pool
• The probability of winning a lottery can be calculated using combinations
  • For example, in a lottery where 6 numbers are chosen from 49, the probability of winning the jackpot is $\frac{1}{\binom{49}{6}} \approx 1.4 \times 10^{-7}$, or about 1 in 13,983,816

Combinations in sampling

• Combinations are used in statistical sampling when the order of selection is not important
• When sampling without replacement, the number of possible samples of size $r$ from a population of size $n$ is given by $\binom{n}{r}$
  • For example, if a quality control inspector needs to select 3 items from a batch of 20 to test for defects, there are $\binom{20}{3} = 1,140$ possible samples

Combinations in quality control

• In quality control, combinations are used to determine the probability of accepting or rejecting a batch of items based on the number of defective items found in a sample
• The hypergeometric distribution, which uses combinations, is often employed in these calculations
  • For example, if a batch of 1000 items has 50 defective items, and a sample of 30 is taken, the probability of finding exactly 2 defective items in the sample is $P(X = 2) = \frac{\binom{50}{2} \times \binom{950}{28}}{\binom{1000}{30}} \approx 0.2388$