## Pascal's Triangle Patterns |
RobinJin |
---|---|

I understand that we derived two of the patterns on pascal's triangle in lecture but I am a little confused as to in what kinds of problems would we use these patterns. I would really appreciate it if someone could clarify this for me. Thanks! |

weisbart: Feb. 1, 2015, 3:48 p.m. |
---|

I'll give you two viewpoints with regards to the Pascal triangle patterns. The first is simply aesthetics. We see this triangle come up when we look at binomial expansions. We notice patterns within it. Why do these patterns exist? Is there a good reason that these patterns should be true? By using only "simple" counting techniques (simple as opposed to something algebraic or analytic that requires harder mathematical machinery), we are able to determine that these patterns are actually valid and we can understand why they appear. That's kind of beautiful! \[\] Of course, that's still not enough of a reason to study them. We have a very limited amount of time and so everything we do, regardless of how pretty, must have an application as well. The first pattern that we study, namely \[{n\choose k} + {n\choose k+1} = {n+1\choose k+1},\] shows us how to get the tree in the first place without actually calculating the coefficients directly. It gives us another way to see that the combinatorially determined values are the same as the algebraically determined values. \[\] The second pattern has lots of applications. Remember that the second pattern is the equality \[{k\choose k} +{k+1\choose k} + {k+2\choose k} + \cdots + {n\choose k} = {n+1\choose k+1}.\] This is a vast generalization of the handshake question which states that \[1 + 2 + 3 + \cdots + n = {n+1\choose 2}\] since \[1 + 2 + 3 + \cdots + n = {1\choose 1} + {2\choose 1} + {3\choose 1} + \cdots + {n\choose 1}.\] The fact that it is a generalization is important in itself, but it is directly useful. \[\] I gave an application in the book that I like. This formula can give us a nice way of computing a sum of the form \[\sum_{k=1}^n p(k),\] where $p(k)$ is a polynomial. For example, it gives us a way of deriving the formula \[\sum_{k=1}^n k^2 = 1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}.\] But there are still other applications. \[\] The point is that sums of binomial coefficients come up unexpectedly in lots of difficult counting problems and so it is of real value to be able to calculate these sums. Here is a problem that is *relatively* straightforward that is an application: Alice, Bob, Cindy, Dave, and Erin are to take their places in line for a photo. There are 20 chairs in which they can sit. Alice will not sit next to either of Bob, Cindy, Dave, or Erin, and she will always sit to the right of them. How many ways can they line up for a photo? |