Search Results

26 results for “combinatorics”

Formulae (26)

Binomial Theorem

(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k

Expands any power of a binomial into a sum of terms.

Statistics & ProbabilityIntermediate

Combinations

\binom{n}{r} = \frac{n!}{r!(n-r)!}

Number of ways to choose r items from n (order irrelevant).

Statistics & ProbabilityIntermediate

Permutations

P(n,r) = \frac{n!}{(n-r)!}

Number of ordered arrangements of r items from n.

Statistics & ProbabilityBasic

Factorial

n! = n\times(n-1)\times\cdots\times 2\times 1

Product of all positive integers up to n.

Probability & CombinatoricsBasic

Permutations

P(n,r) = \frac{n!}{(n-r)!}

Number of ordered arrangements of r items from n.

Probability & CombinatoricsBasic

Combinations

C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}

Number of unordered selections of r items from n.

Probability & CombinatoricsBasic

Factorial

n! = n \times (n-1) \times \cdots \times 2 \times 1

Product of all positive integers up to n.

Probability & CombinatoricsBasic

Permutations with Repetition

n^r

Ordered arrangements of r items from n when repetition is allowed.

Probability & CombinatoricsIntermediate

Permutations of a Multiset

\frac{n!}{n_1! n_2! \cdots n_k!}

Arrangements of n items where some are identical.

Probability & CombinatoricsBasic

Classical Probability

P(A) = \frac{\text{favorable outcomes}}{\text{total outcomes}}

Probability of an event with equally likely outcomes.

Probability & CombinatoricsBasic

Complement Rule

P(A') = 1 - P(A)

Probability that an event does not occur.

Probability & CombinatoricsIntermediate

Addition Rule

P(A \cup B) = P(A) + P(B) - P(A \cap B)

Probability that A or B occurs.

Probability & CombinatoricsBasic

Multiplication Rule (Independent)

P(A \cap B) = P(A) \cdot P(B)

Probability of both independent events occurring.

Probability & CombinatoricsIntermediate

Conditional Probability

P(A|B) = \frac{P(A \cap B)}{P(B)}

Probability of A given that B has occurred.

Probability & CombinatoricsAdvanced

Bayes Theorem

P(A|B) = \frac{P(B|A)\,P(A)}{P(B)}

Reverses conditional probabilities using prior knowledge.

Probability & CombinatoricsIntermediate

Expected Value

E[X] = \sum_{i} x_i\, p_i

Long-run average value of a random variable.

Probability & CombinatoricsIntermediate

Variance of a Random Variable

Var(X) = E[X^2] - (E[X])^2

Measures the spread of a random variable around its mean.

Probability & CombinatoricsIntermediate

Binomial Probability

P(X=k) = \binom{n}{k} p^k (1-p)^{n-k}

Probability of k successes in n independent trials.

Probability & CombinatoricsAdvanced

Poisson Probability

P(X=k) = \frac{\lambda^k e^{-\lambda}}{k!}

Probability of k events in a fixed interval given average rate λ.

Probability & CombinatoricsIntermediate

Geometric Probability

P(X=k) = (1-p)^{k-1} p

Probability that the first success occurs on trial k.

Probability & CombinatoricsAdvanced

Normal Distribution PDF

f(x) = \frac{1}{\sigma\sqrt{2\pi}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}

Bell-curve probability density function.

Probability & CombinatoricsBasic

Odds

Odds = \frac{P(A)}{1 - P(A)}

Ratio of the probability of an event to its non-occurrence.

Probability & CombinatoricsIntermediate

Pigeonhole Principle

\lceil n/k \rceil

If n items go into k containers, some container holds at least this many.

Probability & CombinatoricsAdvanced

Inclusion-Exclusion (3 sets)

|A\cup B\cup C| = |A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|

Counts the union of overlapping sets without double counting.

Probability & CombinatoricsAdvanced

Catalan Number

C_n = \frac{1}{n+1}\binom{2n}{n}

Counts many recursive structures such as balanced parentheses.

Probability & CombinatoricsAdvanced

Stars and Bars

\binom{n+k-1}{k-1}

Ways to distribute n identical items into k distinct groups.