Combinatorial Analysis and Axioms of Probability: Study Notes

Combinatorial Analysis

Combinations and Binomial Coefficients

Combinatorial analysis is fundamental in probability and statistics, providing methods to count arrangements and selections of objects. A combination is a selection of items where order does not matter. The number of ways to choose r objects from n distinct objects is given by the binomial coefficient:

• Formula: $\displaystyle \binom{n}{r} = \frac{n!}{r!(n-r)!}$

• Example: The number of ways to choose 3 students from a group of 10 is $\binom{10}{3} = 120$.

Binomial coefficients appear in the binomial theorem:

• Binomial Theorem: $$(x + y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}$$

• Example: $(x + y)^3 = y^3 + 3xy^2 + 3x^2y + x^3$

Combinatorial Identity: $\displaystyle \binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$

Multinomial Coefficients and Theorem

When dividing n distinct items into r groups of sizes $n_1, n_2, ..., n_r$ (with $n_1 + n_2 + ... + n_r = n$), the number of ways is given by the multinomial coefficient:

• Formula: $\displaystyle \binom{n}{n_1, n_2, ..., n_r} = \frac{n!}{n_1! n_2! \cdots n_r!}$

• Example: Dividing 10 officers into groups of 5, 2, and 3: $\frac{10!}{5!2!3!} = 2520$

The multinomial theorem generalizes the binomial theorem:

• Multinomial Theorem: $$(x_1 + x_2 + \cdots + x_r)^n = \sum_{n_1 + \cdots + n_r = n} \binom{n}{n_1, ..., n_r} x_1^{n_1} \cdots x_r^{n_r}$$

• Example: $(x_1 + x_2 + x_3)^2 = x_1^2 + x_2^2 + x_3^2 + 2x_1x_2 + 2x_1x_3 + 2x_2x_3$

Counting Integer Solutions

To count the number of nonnegative integer solutions to $x_1 + x_2 + ... + x_r = n$:

• Formula: $\displaystyle \binom{n + r - 1}{r - 1}$

• Example: Number of nonnegative integer solutions to $x_1 + x_2 = 3$ is $\binom{4}{1} = 4$

For positive integer solutions ($x_i > 0$): $\displaystyle \binom{n-1}{r-1}$

Summary Table: Key Counting Formulas

Situation	Formula	Example
Permutations of n items	$n!$	Arranging 5 books: $5! = 120$
Combinations (choose r from n)	$\binom{n}{r}$	Choose 2 from 4: $\binom{4}{2} = 6$
Multinomial division	$\binom{n}{n_1, ..., n_r}$	Divide 6 into 2,2,2: $\frac{6!}{2!2!2!} = 90$
Nonnegative integer solutions to $x_1 + ... + x_r = n$	$\binom{n + r - 1}{r - 1}$	$x_1 + x_2 + x_3 = 4$: $\binom{6}{2} = 15$

Axioms of Probability

Sample Space and Events

A sample space (S) is the set of all possible outcomes of an experiment. An event is any subset of the sample space. Events can be combined using set operations:

• Union (E ∪ F): Event that either E or F (or both) occur.

• Intersection (EF or E ∩ F): Event that both E and F occur.

• Complement (Ec): Event that E does not occur.

• Mutually Exclusive: Events E and F are mutually exclusive if $EF = \emptyset$ (cannot both occur).

Venn diagrams are often used to visualize these relationships.

Set Algebra Laws

• Commutative: $E \cup F = F \cup E$, $EF = FE$

• Associative: $(E \cup F) \cup G = E \cup (F \cup G)$, $(EF)G = E(FG)$

• Distributive: $(E \cup F)G = EG \cup FG$

• DeMorgan's Laws:

  • $(\bigcup_{i=1}^n E_i)^c = \bigcap_{i=1}^n E_i^c$

  • $(\bigcap_{i=1}^n E_i)^c = \bigcup_{i=1}^n E_i^c$

Axioms of Probability

Probability is a function P(E) defined on events E in a sample space S, satisfying:

1. Nonnegativity: $0 \leq P(E) \leq 1$

2. Normalization: $P(S) = 1$

3. Additivity: For any sequence of mutually exclusive events $E_1, E_2, ...$, $P(\bigcup_{i=1}^\infty E_i) = \sum_{i=1}^\infty P(E_i)$

From these axioms, several important results follow:

• Probability of the null event: $P(\emptyset) = 0$

• Complement Rule: $P(E^c) = 1 - P(E)$

• Monotonicity: If $E \subset F$, then $P(E) \leq P(F)$

• Union of Two Events: $P(E \cup F) = P(E) + P(F) - P(EF)$

• Inclusion-Exclusion Principle: For events $E_1, ..., E_n$: $$P\left(\bigcup_{i=1}^n E_i\right) = \sum_{i=1}^n P(E_i) - \sum_{i

Equally Likely Outcomes

If a finite sample space S has N equally likely outcomes, then for any event E:

• Probability: $P(E) = \frac{\text{number of outcomes in } E}{N}$

• Example: Probability of sum 7 when rolling two dice: $P = \frac{6}{36} = \frac{1}{6}$

Examples and Applications

• Birthday Problem: Probability that in a group of n people, no two share a birthday: $$P = \frac{365 \cdot 364 \cdots (365 - n + 1)}{365^n}$$ For n ≥ 23, this probability is less than 0.5.

• Matching Problem: Probability that no one gets their own hat when N hats are randomly returned: $$P = 1 - \frac{1}{2!} + \frac{1}{3!} - \cdots + (-1)^N \frac{1}{N!}$$For large N,$P \approx e^{-1} \approx 0.368$.

• Poker Hands: Probability of a straight: $$P = \frac{10(4^5 - 4)}{\binom{52}{5}} \approx 0.0039$$Probability of a full house:$$P = \frac{13 \cdot 12 \cdot \binom{4}{2} \cdot \binom{4}{3}}{\binom{52}{5}} \approx 0.0014$$

Summary Table: Probability Rules

Rule	Formula	Example
Complement	$P(E^c) = 1 - P(E)$	If $P(E) = 0.7$, $P(E^c) = 0.3$
Union (2 events)	$P(E \cup F) = P(E) + P(F) - P(EF)$	See above
Inclusion-Exclusion (3 events)	$P(E \cup F \cup G) = P(E) + P(F) + P(G) - P(EF) - P(EG) - P(FG) + P(EFG)$	See above
Equally likely outcomes	$P(E) = \frac{|E|}{|S|}$	Rolling a 6 on a die: $P = 1/6$

Additional info:

• Some advanced combinatorial identities and proofs (e.g., inclusion-exclusion, multinomial theorem) are left as exercises but are foundational for probability theory.

• Venn diagrams are a powerful tool for visualizing set operations and probability relationships.

• Many probability problems can be solved by careful counting and application of the basic axioms and rules above.