Combinatorial Probability and Counting Techniques in Statistics

Combinatorial Probability and Counting Techniques

Introduction

This chapter explores the foundational counting principles and combinatorial methods essential for probability calculations in statistics. These techniques allow us to systematically count possible outcomes in experiments, which is crucial for determining probabilities in complex scenarios.

Counting Techniques

Fundamental Theorem of Counting (Multiplication Principle)

The Multiplication Principle states that if an experiment can be broken into stages, where the first stage has N(A) outcomes and the second stage has N(B) outcomes for each outcome of the first stage, then the total number of outcomes is N(A) × N(B).

• Key Point: This principle generalizes to more than two stages: multiply the number of outcomes at each stage.

• Example: If you have 3 shirts and 4 pants, you can make 3 × 4 = 12 outfits.

Application Example: User ID Generation

Suppose a website generates an 11-digit user ID using digits 0-9. What is the probability that the first digit is 7 and the last is 9?

• Total possible IDs: $10^{11}$

• IDs with first digit 7 and last digit 9: $1 \times 10^9 \times 1 = 10^9$

• Probability: $\frac{10^9}{10^{11}} = 0.01$

Application Example: Drawing Balls from Boxes

Given 4 boxes (A, B, C, D), each with balls numbered 1-4, drawing one ball from each box:

• Total outcomes: $4 \times 4 \times 4 \times 4 = 256$

• Outcomes with exactly one ball numbered 2: Calculate by choosing which box gives the '2' and others not '2'.

• Probability for specific numbers: For first two balls being '2' and '1', only one way for each, so $1 \times 1 \times 4 \times 4 = 16$ outcomes.

Permutations and Combinations

Factorial Notation

The factorial of a non-negative integer n, denoted n!, is the product of all positive integers up to n. By definition, $0! = 1$.

• Formula: $n! = n \times (n-1) \times \cdots \times 2 \times 1$

Ordered Sampling

• With Replacement: Selecting r objects from n, order matters, objects can repeat. Number of ways: $n^r$

• Without Replacement: Selecting r objects from n, order matters, no repeats. Number of ways: $\frac{n!}{(n-r)!}$

Permutations

A permutation is an ordered arrangement of objects. The number of ways to arrange r objects from n distinct objects is:

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

• Example Calculations:

  • $8P2 = \frac{8!}{6!} = 56$

  • $5P3 = \frac{5!}{2!} = 60$

  • $9P7 = \frac{9!}{2!} = 181440$

  • $11P1 = 11$

Permutations with Repetitions

When some objects are identical, the number of distinct arrangements is reduced. For a word with repeated letters, the formula is:

• Formula: $\frac{n!}{n_1! n_2! \cdots n_k!}$ where $n_1, n_2, \ldots, n_k$ are counts of each repeated letter.

• Example: For "LOL", $\frac{3!}{2!1!} = 3$

Permutations in Circular Arrangements (Round Table)

Arranging n objects around a circle (e.g., a round table) has $(n-1)!$ distinct arrangements due to rotational symmetry.

• With restrictions: Additional constraints (e.g., alternating boys and girls, couples together) further reduce the number of arrangements.

Permutations in Linear Arrangements (Chairs in a Row)

Arranging n objects in a row has $n!$ possible arrangements. Restrictions (e.g., alternating, groups together) modify the count.

Special Permutation Problems

• Words with all letters used: For a word with all unique letters, number of arrangements is $n!$.

• With constraints: For example, if two letters must be together, treat them as a block; if never together, subtract arrangements where they are together from the total.

Combinations

Unordered Selection

• Without Replacement: Number of ways to choose r objects from n (order does not matter): $nC_r = \frac{n!}{r!(n-r)!}$

• With Replacement: Number of ways to choose r objects from n with replacement: $\frac{(n+r-1)!}{r!(n-1)!}$

Binomial Coefficient

The binomial coefficient $nC_r$ counts the number of combinations and appears in the binomial theorem.

• Example Calculations:

  • $7C5 = 21$

  • $6C1 = 6$

  • $10C10 = 1$

  • $0C0 = 1$

  • $7C2 = 21$

Application Example: Dressing Combinations

If you have 8 coats (4 blue, 4 black), 5 jeans, and 4 shoes, and must wear one of each:

• Total ways: $8 \times 5 \times 4 = 160$

• Ways with blue coat: $4 \times 5 \times 4 = 80$

• Probability of blue coat: $\frac{80}{160} = 0.5$

Application Example: Army Line-up

Choosing 5 archers from 15, 3 swordsmen from 10, and 2 knights from 5:

• Ways: $15C5 \times 10C3 \times 5C2$

Partitions and Multinomial Coefficients

Partitions

Partitioning n objects into k disjoint subsets of specified sizes is a common combinatorial problem. The order within subsets does not matter.

Multinomial Coefficient

The number of ways to partition n objects into k groups of sizes $r_1, r_2, ..., r_k$ (where $r_1 + r_2 + ... + r_k = n$) is:

• Formula: $\frac{n!}{r_1! r_2! \cdots r_k!}$

Application Example: Assigning Workers to Jobs

Assigning 6 workers to jobs A (2), B (3), C (1):

• Ways: $\frac{6!}{2!3!1!} = 60$

Application Example: Dividing a Deck

Dividing 26 cards into two subsets of 13:

• Ways: $\frac{26!}{13!13!}$

Application Example: Choosing a Group with Constraints

Choosing 5 people from 5 graduates and 7 undergraduates, with at least 3 undergraduates:

• Ways: Sum the combinations for 3, 4, and 5 undergraduates chosen, with the rest graduates.

Application Example: Password Arrangements

Arranging a 10-character password with 2 '1's, 3 '2's, 3 'A's, and 2 '!':

• Ways: $\frac{10!}{2!3!3!2!}$

Application Example: Assigning Officers to Tasks

Assigning 10 officers to 3 tasks (5, 2, 3):

• Ways: $\frac{10!}{5!2!3!}$