Combinatorics

https://www.youtube.com/watch?v=jAcbcWV9CyE Similar to the question of summing a row of Pascal’s triangle, we can consider summing the squares of the entires of a row of Pascal’s triangle. By a combinatorial argument involving cats and dogs, we show that $$binom{n}{0}^2+binom{n}{1}^2+cdots+binom{n}{n}^2=binom{2n}{n}.$$

https://www.youtube.com/watch?v=1Ovnz74AasA If one takes the sum of a row of entries in Pascal’s triangle, one finds that $$binom{n}{0}+binom{n}{1}+cdots+binom{n}{n}=2^n.$$ In this video, we prove this remarkable combinatorial identity in two ways: by forming a committee and substituting numbers into the binomial theorem.

https://www.youtube.com/watch?v=fHZ7FniqPr4 If Pascal’s triangle is drawn out, one is immediately faced with the fact that the numbers in a row read the same from left to right as right to left. Since the entries of Pascal’s triangle are binomial coefficents, this observation is equivalent to the combinatorial identity $$binom{n}{k}=binom{n}{n-k}.$$

https://www.youtube.com/watch?v=Cwo2ua3H1pE Pascal’s triangle is a famous structure in combinatorics and mathematics as a whole. It can be interpreted as counting the number of paths on a grid, which is intimately linked with binomial coeffcients, otherwise known as combinations. This leads to a relationship between binomial coefficients, called Pascal’s identity, via a technique called double counting.

https://www.youtube.com/watch?v=3aacb7OVb44 One interpretation of multinomial coefficients is that we have a collection of subcollections of items, where items within the same subcollection are indistinguishable but items in different subcollections are distinguishable. The goal is to find the number of ways of permuting the overarching collection. We derive this formula using the formula for combinations and

https://www.youtube.com/watch?v=6vkFP5pPePo The most ubiquitous expressions in combinatorics are combinations, otherwise known as binomial coefficients. These count the number of subsets with a particular cardinality of some finite set. In this video, we derive the formula for combinations using the formula for counting permutations and the $k$-to-$1$ correspondence principle.

https://www.youtube.com/watch?v=Hq2vp_0eUyQ A powerful idea in combinatorics is to produce a map from one finite set to another in such a way that the preimage of every element of the range has a uniform number of elements. This is called a $k$-to-$1$ correspondence. An example of where this comes in handy is in proving the formula

https://www.youtube.com/watch?v=SxKnHqFIvvE Given a finite set of $n$ elements, in how many ways can we form an ordered $k$-tuple of distinct elements from that set? This question and its answer gives rise to the concept of permutations. We solve the problem using the strong multiplication principle, otherwise known as the product rule, in this video.

https://www.youtube.com/watch?v=MW7_7OAe330 If we know that the cardinality of a finite set is $n$, what is the cardinality of its power set? It turns out that there is a simple formula, which is $2^n$. We prove this fact in this video using the weak multiplication principle and bijection principle from combinatorics.

https://www.youtube.com/watch?v=mhZ2I4Q5R28 Suppose there are at least six people at a party. If two of them have met before, we call them “friends,” and if two of them have not met before, we call them “strangers.” In an amazing twist of fate, it turns out that there will always exist three people who are pairwise all