Udemy | Introductory Programming Course | Math Prerequisite
Counting and Probability
Prerequisites for Programming and Algorithms
Counting is probably the most primitive form of math and something that is pretty intuitive to all of us. Hence, the two rules that I am going to refer to are the easiest ones if you have already gone through the sets and relations.
1. Basic Counting Principles
Counting Principles: Rule of Sum and Rule of Product
Let’s start with two basic principles of counting:
- Rule of Sum (Addition Rule):
The rule of sum says, that the number of ways to choose one element from one of two disjoint sets is the sum of the cardinalities of the sets.
For example, if you have 3 apples and 5 oranges, the number of ways to choose either an apple or an orange is 3 + 5 = 8. This rule applies when the sets are disjoint. - Rule of Product (Multiplication Rule):
The rule of the product says, that the number of ways to choose an ordered pair is the number of ways to choose the first element times the number of ways to choose the second element.
For example, if you have 4 shirts and 3 pairs of pants, the number of different outfits you can choose is 4 × 3 = 12. This rule is essential when dealing with sequential decisions.
2. Permutations
Permutations without Repetition
Permutations refer to the arrangement of objects where order matters. The formula for the number of ways to arrange n objects is n!
For example, 3 objects (A, B, C) can be arranged in 3! = 6 different ways: ABC, ACB, BAC, BCA, CAB, and CBA.
Permutations with Repetition
When some objects are repeated, the total number of permutations is reduced. The formula becomes
where k₁, k₂ are the frequencies of repeated elements.
K-Permutations
If you are only selecting k items from a set of n items, the number of permutations (where order matters) will be:
For example, choosing 2 items from a set of 4:
3. Combinations
Combinations without Repetition
Combinations refer to the selection of objects where the order doesn’t matter. The formula for choosing r elements from n is:
For example, if you choose 2 fruits from a set of 4 (apple, banana, cherry, and date), there are C(4,2)=6 ways to do so.
Combinations with Repetition
In cases where repetition is allowed, the formula becomes:
This applies in scenarios like choosing toppings for a pizza, where you can select the same topping multiple times.
4. Binomial Theorem
The Binomial Theorem provides a way to expand expressions of the form (a + b)ⁿ. The general formula is:
This theorem is highly useful in combinatorics and probability, allowing you to calculate coefficients in polynomial expansions. Pascal’s Triangle can help visualize the binomial coefficients that emerge from the theorem.
Binomial Expansion & Binomial Coefficient
The expansion involves terms with binomial coefficients C(n, k), which can be found in Pascal’s Triangle.
For example:
(a + b)² = a² + 2ab + b²
(a + b)³ = a³ + 3a²b + 3ab² + b³
The coefficients 1, 2, 1 and 1, 3, 3, 1 are the binomial coefficients C(n, k).
5. Probability Basics
Basic Probability Concepts
Probability quantifies how likely an event is to happen. The formula is:
For example, the probability of rolling a 4 on a six-sided die is P(4)=1/6.
Probability of Independent and Dependent Events
Independent events don’t affect each other’s outcomes, like tossing two coins. The probability of both heads is
P(H)×P(H)=1/2×1/2=1/4
Dependent events, on the other hand, have outcomes that influence one another. The formula for dependent events is:
Complementary Events
The probability of the complement of an event (the event not happening) is:
For example, the probability of not rolling a 4 on a die is P(¬4)=1−1/6=5/6.
Conditional Probability
The probability of an event given that another event has occurred is given by
In summary, understanding these counting principles and probability basics will help you tackle many problems in competitive programming, where calculating possibilities and likelihoods often play a key role.
