Combinatorics Flashcards
Arithmetic progression
A sequence where the difference between any two consecutive numbers is the same
An arithmetic progression is defined by…
Its first element and the common difference between elements
Finding the nth element (arithmetic progression)
a1 + (n – 1)d
Sum of elements (arithmetic progression)
S = 1 + 2 + 3 + … + 100
Reverse order of summands: 100 + 99 + 98 + … + 1
Add the equalities: 2S = 101, 101, 101, …
So S = 101 * 100 / 2 = 5050
Geometric progression
A sequence where the ratio between any two consecutive elements is the same
A geometric progression is defined by…
Its first element and the common ratio between elements
Finding the nth element (geometric progression)
g1 * r^(n-1)
Sum of elements (geometric progression)
Sn = g1(1 - r^n / 1 - r), r ≠ 1
Sum of decreasing progression (geometric progression)
S∞= g1 / 1 - r, |r| < 1
Pigeonhole principle
If n items are divided into m groups, and n > m, then some groups contain more than one item
Rule of product
- In a refectory the student can choose one of five starters and one of three main courses. What is the total number of possible meals?
- Let the set of starters = {s1, …, s5} and set of main courses = {m1, m2, m3}
- Set of possible meals = Cartesian product SxM = 5 * 3 = 15
Rule of sum
A vending machine offers five types of coffee and three types of tea. The total number of options = 5 + 3 = 8
A word is a sequence of letters of length between 1 and 5. How many words are there?
k=5, n1=26, n2=262…
Number of words = 26 + 26^2 + 26^3 + 26^4 + 26^5
Permutation
Number of possible rearrangements of n different objects
Number of permutations
n * P_(n - 1)
