Sum of Squares of a Row of Pascal’s Triangle 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}.$$

Sum of a Row of Pascal’s Triangle 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.

Symmetry in Pascal’s Triangle 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}.$$

Pascal’s Triangle and Pascal’s Identity 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.

Multinomial Coefficients 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 …

Multinomial Coefficients Read More »

Binomial Coefficients and Combinations 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.

$k$-to-$1$ Correspondences 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 …

$k$-to-$1$ Correspondences Read More »

Counting Permutations 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.

Counting the Power Set of a Finite Set 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.