Counting and Probability

Principle of Inclusion and Exclusion

This principle is a method for counting the number of elements in the union of several sets. It states that to find the total number of elements in the union of sets, one must add the sizes of the individual sets and then subtract the sizes of their pairwise intersections, add back the sizes of triple intersections, and so on, alternating between addition and subtraction.

Additive Counting Principle

This principle states that if there are a ways to do something and b ways to do another thing, and these two things cannot happen at the same time (they are mutually exclusive), then there are a+b ways to do either.

Example:

If you can choose between 2 soups and 3 main dishes for lunch, there are 2+3=5 lunch choices.

Multiplicative Counting Principle

This principle states that if there are a ways to do something and b ways to do another thing independently, then there are a×b ways to do both.

Example:

If there are 5 types of burgers and 3 types of drinks, there are 5×3=15 possible burger-drink pairings.

Pigeonhole Principle Example

If you have 7 socks in a drawer with 3 different colors, the pigeonhole principle guarantees that at least two socks will be of the same color, because there are more socks (7) than colors (3).

Permutation of n Distinct Objects

A permutation of n distinct objects is an arrangement, or an ordering, of these objects in a specific sequence. The total number of permutations of n distinct objects is n! (n factorial).

Repeated Permutation vs. Permutation of Distinct Objects

Repeated permutation allows for the repeated use of objects in arrangements, unlike permutations of distinct objects where each object is used exactly once. For instance, arranging two letters from the set {A, B} with repetition could give AA, AB, BA, BB.

Combination of r Objects from n Distinct Objects

A combination involves selecting r objects from a set of n distinct objects without regard to the order of the objects. The number of such combinations is given by C(n,r)=n!/r!(n−r)!.

Repeated Combination vs. Repeated Permutation

Repeated combination refers to choosing r objects from n types with unlimited repetition allowed, without considering the order of selection. In contrast, repeated permutation involves arranging r objects from n types with repetition, where order does matter. Repeated combinations are fewer because order does not distinguish different selections.

Binomial Theorem

It states that (x+y)^n=∑k=0..n C(n,k)*x^(n−k)*y^k, where C(n,k) is the number of combinations of n objects taken k at a time.

Event and Sample Space

An event is any collection of outcomes from a probability experiment. The sample space is the set of all possible outcomes of that experiment.

Probability of an Event

It's the measure of the likelihood that an event will occur, calculated as the ratio of the number of favorable outcomes to the number of all possible outcomes in the sample space.

Example of Two Independent Events

Rolling a 3 on a die and flipping a tail on a coin are independent events. The probability of both occurring is the product of their individual probabilities, e.g., 1/6×1/2=1/12.

Conditional Probability

It's the probability of an event A occurring given that another event B has already occurred. The formula is P(A|B)=P(B)P(A∩B), where P(A∩B) is the probability of both A and B occurring.

Tree Diagram

It provides a graphical representation of all possible outcomes of an experiment or a series of experiments, showing how different branches represent different possible outcomes and their probabilities.

Random Variable and Expectation

A random variable is a variable whose value depends on the outcomes of a random phenomenon. The expectation (or expected value) of a random variable is the long-term average value of repetitions of the experiment it represents, calculated as ∑[XiP(Xi)], where Xi are the values the random variable can take, and P(Xi) are their respective probabilities.

Stochastic Process

It's a collection of random variables representing the evolution