Basics of Counting

Counting is a fundamental concept in mathematics, particularly in discrete mathematics. It involves determining the number of ways an event can occur or the number of elements in a set. Understanding basic counting principles is crucial for solving problems in combinatorics and probability.

The Sum Rule

The Sum Rule states that if there are 'n' ways to do one thing and 'm' ways to do another, and these two things cannot be done at the same time, then there are n + m ways to choose one of the actions.

For example, if a student can choose a project from one of two lists, where the first list has 10 projects and the second list has 15 projects, and no project is on both lists, then the student has 10 + 15 = 25 projects to choose from.

The Product Rule

The Product Rule states that if there are 'n' ways to do one thing and 'm' ways to do another, then there are n * m ways to do both actions. This rule applies when the choice of the first action does not affect the number of choices for the second action.

For instance, if a restaurant offers 5 appetizers and 10 main courses, a customer can choose an appetizer and a main course in 5 * 10 = 50 different ways.

Generalized Product Rule

This rule extends the product rule to more than two actions. If there are n1 ways to perform the first action, n2 ways to perform the second action, ..., and nk ways to perform the kth action, then there are n1 * n2 * ... * nk ways to perform all k actions in sequence.

Consider a scenario where a person needs to choose an outfit consisting of a shirt, a pair of pants, and a pair of shoes. If there are 3 shirts, 4 pairs of pants, and 2 pairs of shoes, the total number of different outfits is 3 * 4 * 2 = 24.

Pigeonhole Principle

The Pigeonhole Principle is a simple yet powerful counting principle. It states that if you have more pigeons than pigeonholes, then at least one pigeonhole must contain more than one pigeon.

Basic Pigeonhole Principle

If 'n' items are put into 'm' containers, with n > m, then at least one container must contain more than one item.

Example: If there are 13 people in a room, at least two of them must share the same birth month. Here, the people are the 'items' (n=13) and the months are the 'containers' (m=12).

Generalized Pigeonhole Principle

If 'n' items are put into 'm' containers, then at least one container must contain at least ceil(n/m) items. The ceiling function, ceil(x), gives the smallest integer greater than or equal to x.

Example: If 30 students are assigned to 5 advisors, then at least one advisor must have at least ceil(30/5) = 6 students. If 35 students are assigned to 5 advisors, at least one advisor must have at least ceil(35/5) = 7 students.

Permutations and Combinations

These are techniques used to count the number of ways to arrange or select items from a set. The key difference lies in whether the order of selection matters.

Permutations

A permutation is an arrangement of objects in a specific order. The number of permutations of 'n' distinct objects taken 'r' at a time is denoted by P(n, r) or nPr.

The formula for permutations is: P(n, r) = n! / (n-r)!

Where '!' denotes the factorial (e.g., 5! = 5 * 4 * 3 * 2 * 1).

Example: How many ways can 3 students be selected from a group of 5 to be president, vice-president, and secretary? Here, order matters. P(5, 3) = 5! / (5-3)! = 5! / 2! = (5 * 4 * 3 * 2 * 1) / (2 * 1) = 60.

Combinations

A combination is a selection of objects where the order does not matter. The number of combinations of 'n' distinct objects taken 'r' at a time is denoted by C(n, r) or nCr or (n choose r).

The formula for combinations is: C(n, r) = n! / (r! * (n-r)!)

Example: How many ways can a committee of 3 people be selected from a group of 5? Here, order does not matter. C(5, 3) = 5! / (3! * (5-3)!) = 5! / (3! * 2!) = (5 * 4 * 3 * 2 * 1) / ((3 * 2 * 1) * (2 * 1)) = 10.

Permutations with Repetition

If you have 'n' objects where there are n1 identical objects of type 1, n2 identical objects of type 2, ..., nk identical objects of type k, then the number of distinct permutations of these n objects is n! / (n1! * n2! * ... * nk!).

Example: How many distinct permutations are there of the letters in the word "MISSISSIPPI"? Here, n=11. M appears 1 time, I appears 4 times, S appears 4 times, P appears 2 times. So, the number of permutations is 11! / (1! * 4! * 4! * 2!) = 39,916,800 / (1 * 24 * 24 * 2) = 34,650.

Inclusion-Exclusion Principle

The Inclusion-Exclusion Principle is a counting technique used to find the number of elements in the union of two or more sets. It corrects for overcounting that occurs when simply adding the sizes of the sets.

For Two Sets

For two sets A and B, the number of elements in their union is given by: |A ∪ B| = |A| + |B| - |A ∩ B|. We add the sizes of the sets and then subtract the size of their intersection to avoid counting the common elements twice.

Example: In a class of 30 students, 15 like Math, 20 like Science, and 8 like both Math and Science. How many students like Math or Science? |M ∪ S| = |M| + |S| - |M ∩ S| = 15 + 20 - 8 = 27.

For Three Sets

For three sets A, B, and C, the principle is extended: |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|. We add the individual sets, subtract the pairwise intersections, and then add back the intersection of all three sets.

Example: Suppose in a survey of 100 people, 40 liked Coffee, 30 liked Tea, 50 liked Juice. 15 liked Coffee and Tea, 20 liked Coffee and Juice, 10 liked Tea and Juice, and 5 liked all three. How many liked at least one of the beverages? |C ∪ T ∪ J| = 40 + 30 + 50 - 15 - 20 - 10 + 5 = 130 - 45 + 5 = 90.

Mathematical Induction

Mathematical induction is a proof technique used to establish that a given statement or formula is true for all natural numbers (or all integers greater than or equal to some starting integer). It's like dominoes falling: if you can knock over the first one, and each falling domino knocks over the next, then all dominoes will fall.

Steps of Mathematical Induction

1. Base Case (or Basis Step): Prove that the statement P(n) is true for the smallest value of n (usually n=1 or n=0).
2. Inductive Hypothesis: Assume that the statement P(k) is true for some arbitrary integer k ≥ the base case.
3. Inductive Step: Prove that if P(k) is true, then P(k+1) must also be true.

Example Proof

Prove that the sum of the first n positive integers is n(n+1)/2. That is, prove P(n): 1 + 2 + 3 + ... + n = n(n+1)/2.

1. Base Case: For n=1, the left side is 1. The right side is 1(1+1)/2 = 1(2)/2 = 1. So, P(1) is true.
2. Inductive Hypothesis: Assume P(k) is true for some integer k ≥ 1. That is, assume 1 + 2 + ... + k = k(k+1)/2.
3. Inductive Step: We need to show that P(k+1) is true, meaning 1 + 2 + ... + k + (k+1) = (k+1)((k+1)+1)/2 = (k+1)(k+2)/2.

   Starting with the left side of P(k+1):

   1 + 2 + ... + k + (k+1)

   = (1 + 2 + ... + k) + (k+1)

   By the inductive hypothesis, we can replace (1 + 2 + ... + k) with k(k+1)/2:

   = k(k+1)/2 + (k+1)

   Now, find a common denominator and simplify:

   = k(k+1)/2 + 2(k+1)/2

   = (k(k+1) + 2(k+1)) / 2

   = (k+1)(k + 2) / 2

   This is the right side of P(k+1). Thus, P(k+1) is true.

Since the base case is true and the inductive step holds, the statement P(n) is true for all positive integers n by the principle of mathematical induction.

Discrete Probability

Probability is the measure of the likelihood that an event will occur. In discrete probability, we deal with outcomes that are countable and finite or countably infinite.

Basic Concepts

• Experiment: A process with an observable outcome.
• Sample Space (S): The set of all possible outcomes of an experiment.
• Event (E): A subset of the sample space.
• Probability of an Event P(E): The ratio of the number of favorable outcomes to the total number of possible outcomes, assuming all outcomes are equally likely. P(E) = |E| / |S|.

Properties of Probability

• 0 ≤ P(E) ≤ 1 for any event E.
• P(S) = 1 (The probability of the entire sample space is 1).
• If E1, E2, ..., Ek are mutually exclusive events (they cannot occur at the same time), then P(E1 ∪ E2 ∪ ... ∪ Ek) = P(E1) + P(E2) + ... + P(Ek).

Example: Rolling a Die

Experiment: Rolling a fair six-sided die.

Sample Space (S): {1, 2, 3, 4, 5, 6}. So, |S| = 6.

Event E: Rolling an even number. E = {2, 4, 6}. So, |E| = 3.

Probability P(E) = |E| / |S| = 3 / 6 = 1/2.

Conditional Probability

The probability of an event A occurring given that another event B has already occurred. It is denoted by P(A|B).

Formula: P(A|B) = P(A ∩ B) / P(B), provided P(B) > 0.

Example: What is the probability of rolling a 4 on a die given that the outcome is an even number? Let A be the event of rolling a 4. A = {4}. Let B be the event of rolling an even number. B = {2, 4, 6}. A ∩ B = {4}. P(A) = 1/6, P(B) = 3/6 = 1/2. P(A ∩ B) = 1/6. P(A|B) = P(A ∩ B) / P(B) = (1/6) / (1/2) = 1/3.

Independent Events

Two events A and B are independent if the occurrence of one does not affect the probability of the other occurring. Mathematically, A and B are independent if P(A ∩ B) = P(A) * P(B).

Equivalently, if P(B) > 0, A and B are independent if P(A|B) = P(A).

Example: Tossing a coin twice. The outcome of the first toss is independent of the outcome of the second toss.

Bayes' Theorem

Bayes' Theorem is a fundamental theorem in probability theory that describes how to update the probability of a hypothesis based on new evidence. It relates conditional probabilities.

The Theorem

If A and B are events such that P(B) > 0, then Bayes' Theorem states:

P(A|B) = [ P(B|A) * P(A) ] / P(B)

Where:

• P(A|B) is the posterior probability: the probability of hypothesis A given evidence B.
• P(B|A) is the likelihood: the probability of evidence B given hypothesis A.
• P(A) is the prior probability: the initial probability of hypothesis A.
• P(B) is the probability of the evidence: the total probability of evidence B occurring.

Expanded Form of Bayes' Theorem

Often, the probability of the evidence P(B) needs to be calculated using the law of total probability. If A1, A2, ..., An form a partition of the sample space (i.e., they are mutually exclusive and their union is the entire sample space), then:

P(B) = P(B|A1)P(A1) + P(B|A2)P(A2) + ... + P(B|An)P(An)

So, Bayes' Theorem can be written as:

P(Ai|B) = [ P(B|Ai) * P(Ai) ] / [ Σ P(B|Aj)P(Aj) ] (sum over all j)

Example: Medical Diagnosis

Suppose a rare disease affects 1 in 1000 people (P(D) = 0.001). A test for the disease is 99% accurate for people who have the disease (P(T+|D) = 0.99) and 98% accurate for people who do not have the disease (meaning it gives a false positive 2% of the time, so P(T+|¬D) = 0.02).

We want to find the probability that a person actually has the disease given that they tested positive, P(D|T+).

We have:

• Prior probability of disease: P(D) = 0.001
• Probability of no disease: P(¬D) = 1 - P(D) = 0.999
• Likelihood of positive test given disease: P(T+|D) = 0.99
• Likelihood of positive test given no disease: P(T+|¬D) = 0.02

First, calculate the probability of testing positive, P(T+), using the law of total probability:

P(T+) = P(T+|D)P(D) + P(T+|¬D)P(¬D)

P(T+) = (0.99 * 0.001) + (0.02 * 0.999)

P(T+) = 0.00099 + 0.01998 = 0.02097

Now, apply Bayes' Theorem:

P(D|T+) = [ P(T+|D) * P(D) ] / P(T+)

P(D|T+) = (0.99 * 0.001) / 0.02097

P(D|T+) = 0.00099 / 0.02097 ≈ 0.0472

This means that even with a positive test, there is only about a 4.72% chance the person actually has the disease. This is because the disease is so rare, most positive results come from the larger group of healthy people getting a false positive.