Combinatorics

The binomial coefficient denoted by $n \choose k$ is the number of ways to choose k objects from n objects. Its formula is the following: $n \choose k$ = $\frac{n!}{k!(n-k)!}$, why is this even the case? How did people come up with this? Let us find out together. So we want to find the number of ways we can pick $k$ objects our of $n$ objects, let’s say we have the set $\{1,2,3, …, n\}$, and we are trying to pick $k$ of them and if $k = 2$ it doesn’t matter we pick 1,2 or 2,1 those are the same, which basically means we don’t care about the ordering of choice....

Formally: The generating function of an infinite sequence $(a_0, a_1, \ldots)$ is represented by the power series: $$ \sum_{n=0}^\infty a_nx^n $$ Informally: Consider a sequence of numbers $(a_0, a_1, \ldots)$. We want to encode this sequence within a function, expressed as: $$ a_0x^0 + a_1x^1 + a_2x^2 + \ldots + a_nx^n = \displaystyle\sum_{n=0}^\infty a_nx^n $$ Example of Sequence $(1, 1, 1, 1, \ldots )$: $$ 1x^0 + 1x^1 + 1x^2 + \ldots + 1x^n = \displaystyle\sum_{n=0}^\infty x^n = \frac{1}{1 - x} $$ You may ask why the equation $\displaystyle\sum_{n=0}^\infty x^n = \frac{1}{1 - x}$ holds....