CO16 Counting subsets aka Combinations via binomial coefficients

An s-Combination is a subset of size s. The number of s-combinations of a set with t elements is a binomial coefficient read "t choose s". We give the definition, a formula and its proof, several examples, a recurrence relation with its proof, and briefly explain why we call the triangle of binomial coefficients the Karaji-Jia triangle (as opposed to the common Pascal's triangle). Subscribe @Shahriari for more undergraduate Math videos.
00:00 Introduction
00:30 Definition: s-combinations, subsets of size s
02:11 Definition: "t choose s", binomial coefficients
02:52 Example of binomial coefficients
03:50 Special cases: "n choose 0", "n choose n", "n choose 1"
04:56 Formula for binomial coefficients
05:33 Proof of the formula
10:29 Example: Balls & Boxes
12:08 Example: Deal 13 cards to each of 4 players. What is the probability that each get exactly 3 picture cards?
17:03 Example: Number of ways of pairing 8 people into 4 couples
22:40 Example: Number of NE paths on a grid
28:26 Lemma: "n choose k" is equal to "n choose n-k"
29:00 Proof of Lemma
31:29 Recurrence relation for binomial coefficients
31:51 Proof of recurrence relation
33:27 Triangle of Binomial Coefficients
34:52 Pascal's Triangle or Karaji's triangle or Jia's triangle
35:59 Karaji's triangle
36:54 Jia's triangle

A series of lectures on introductory Combinatorics. This full course is based on my book
Shahriar Shahriari, An Invitation to Combinatorics, Cambridge University Press, 2022.

For an annotated list of available videos for Combinatorics see

Shahriar Shahriari is the William Polk Russell Professor of Mathematics at Pomona College, in Claremont, CA, U.S.A.