Pascal's Triangle - ergodic reader

#cs/cp #math/discrete #flashcards/math ## Pascal's Triangle Each element is equal to the sum of its two parents. Its a historically interesting visual that has many properties in different areas of math. The triangle can evaluate $\binom{n}{k}$. The triangle is 0-indexed by row and column. For example $\binom{5}{3} = \frac{5!}{3!2} = 10$ can be found at row 5 column 3. Its also used to compute [[Lucas' Theorem]] in $O(\log_{p}(n))$ time. $\begin{array}{c} 1 \\ 1 \quad 1 \\ 1 \quad 2 \quad 1 \\ 1 \quad 3 \quad 3 \quad 1 \\ 1 \quad 4 \quad 6 \quad 4 \quad 1 \\ 1 \quad 5 \quad 10 \quad \textbf{10} \quad 5 \quad 1 \\ 1 \quad 6 \quad 15 \quad 20 \quad 15 \quad 6 \quad 1 \\ 1 \quad 7 \quad 21 \quad 35 \quad 35 \quad 21 \quad 7 \quad 1 \end{array}$ %%--%% ## What is the Combination Formula? %%?%% N choose k is the number of sets of $n$ items taken $k$ at a time. Or it is the number of ways we can choose $k$ balls, order doesn't matter, from a pool of $n$ distinct balls. $ \binom{n}{k} = \frac{n!}{k!(n-k)!} $ Note that the rows sum to $2^n$ since that would represent every possible subset of size $0 \dots n$ i.e. $\sum_{k=0}^{n}\binom{n}{k} = 2^n$.  %%--%% ## Number of Distinct Paths to Each Square Overlay Pascal's Triangle on a chess board with a rook at the corner. A square, rotated 90 degrees, is formed in the triangle. The numbers for each square represent the number of distinct paths to that square. This extends to rectangles too. The total number of moves will be $m + n$. Each move is ordered and distinct. We need to choose which of these ordered moves will be ones to the right, while the others will be downward moves. For an $MxN$ grid, the $ \text{Total Number of Paths = }\binom{m + n}{n} = \binom{m + n}{m} $ The same applies with assigning downward movements. %%--%% ## What is Pascal's Formula %%?%% Notice the RHS of the equation is simply the parents of a given number in the triangle. $ \binom{n}{k} = \binom{n-1}{k - 1} + \binom{n-1}{k} $  %%--%% %%--%% ## The Binomial Theorem Coefficients Formula %%?%% Each row of numbers of pascal's triangle are the coefficients to $(x+y)^n$. $ (x+y)^n = \sum_{k=0}^{n} \binom{n}{k}x^{n-k}y^k $ Where the coefficients $\alpha_{i}\dots\alpha_{n}$ follow $\alpha_{k} = \binom{n}{k}$.  %%--%%