  ## Counting Surjections in Combinatorics

https://www.youtube.com/watch?v=ZXIsCe3EZKE Given two finite sets, we might wonder how many surjections exist that map from one to the other. It turns out that this question, and a generalization, can be answered using the principle of inclusion-exclusion (PIE). Moreover, if the output codomain has more elements than the input domain, then the number of surjections is … ## Counting Derangements in Combinatorics

https://www.youtube.com/watch?v=NkFbv1jxcdE Derangements are permutations with no fixed points, meaning no element gets mapped to itself. We use the principle of inclusion-exclusion to derive as simple as possible a formula for the number of derangements of a given finite set. Amazingly, it turns out that, as the number of elements goes to infinity, the fraction of … ## Euler’s Totient Function Formula

https://www.youtube.com/watch?v=Kl9WH5Eev2o Euler’s totient formula tells us the number of positive integers less than or equal to a given positive integer that are relatively prime to the latter. This is an important function in combinatorics and number theory. The function can be computed in a fairly simple fashion if we know the list of distinct prime … ## Principle of Inclusion-Exclusion (PIE)

https://www.youtube.com/watch?v=fl2eoGBIT70 Given two finite sets, we can find the cardinality of their union by adding the two individual cardinalities and subtracting the cardinality of the intersection. But how can we find the cardinality of the union of $n$ finite sets? This is the general principle of inclusion-exclusion, otherwise known as PIE. We state this general … ## Vandermonde’s Identity

https://www.youtube.com/watch?v=-yLJ8G_i_vM If we have $m$ cats and $n$ dogs, in how many ways can we choose $k$ of the animals? By iterating through the possible combinations of dogs and cats, we can derive a combinatorial identity, which is called Vandermonde’s identity. We derive this identity here using the described combinatorial or committee-forming proof. ## Hockey Stick Identity

https://www.youtube.com/watch?v=hk98kUxk-V0 The hockey stick identity in combinatorics tells us that if we take the sum of the entries of a diagonal in Pascal’s triangle, then the answer will be another entry in Pascal’s triangle that forms a hockey stick shape with the diagonal. Although proofs by induction or Pascal’s identity are possible, we show a …