Combinatorics
Generalized basic principle of counting
Variations of the basic counting principle
With/without repetitions and with order, without repetitions and without order are pretty much obvious, see explanations in Discrete math course, lecture 15
Explanation for “with repetitions, without order”
Choosing k elements out of a set of size n is the same as creating a multiset of total size k. This can be written as
Which in turn is equal to the number of solutions to the equation:
This can be interpreted as stars and bars problem with n-1 bars and k stars.
Catalan numbers
Lattice paths
”Good” Lattice paths
…TO BE CONTINUED (you can also see Discrete math course, lecture 18)