Lesson 10

Pascal's triangle is a remarkable combinatorial object. Below we will see how many interesting properties it has.

• Neighbors from above:  the value in a cell of the triangle is equal to the sum of the two neighbors from above this cell. This is a reformulation of the equality \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\).
  

  



• Calculating binomial coefficients:  can be calculated by gradually filling the triangle according to the rule \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\).
  

  

  
  

  cells = dict()  # cells[n, k] will keep n choose k
  
  for n in range(8):
      cells[n, 0] = 1
      cells[n, n] = 1
  
      for k in range(1, n):
          cells[n, k] = cells[n - 1, k - 1] + cells[n - 1, k]
  
  print(cells[7, 4])

  
  

  35
  



• Horizontal Symmetry:  \[\binom{n}{k}= \binom{n}{n-k}\ .\] That is, the triangle is symmetric about the vertical central line. This can be proven directly using the formula: \[\binom{n}{k}= \frac{n!}{k!(n-k)!}=\frac{n!}{(n-k)!k!}=\binom{n}{n-k}\ .\] Alternatively, it can be proven combinatorially: both represent the number of ways to divide \(n\) people into two teams, one with \(k\) members.


• Sum in a Row:  For any \(n \in \mathbb{Z}_{\ge 0}\) \[\binom{n}{0}+\binom{n}{1}+\dotsb+\binom{n}{n-1}+\binom{n}{n}=2^{n} \ .\] Let us verify this statement for the first few rows.
  

  

  
  This can be proven by induction on \(n\). The base case \(n=0\) holds. For the induction step \(n-1 \to n\), Pascal's rule shows that every element of row \(n-1\) appears twice in the sum of row \(n\).
  

  

  
  

  

  
  As usual, this equality can also be proven combinatorially: it simply counts the total number of subsets of an \(n\)-element set.


• Alternating Sum:  For any \(n \in \mathbb{Z}_{>0}\) \[\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}= 0 \ .\]
  

  

  
  For odd \(n\), this follows immediately from the symmetry of the triangle. In general, it is derived from the property of adjacent elements above.
  We now present a combinatorial proof based on the method of a distinguished element. We need to prove that for \(n>0\) \[\binom{n}{1}+\binom{n}{3}+\dotsb=\binom{n}{0}+\binom{n}{2}+\dotsb \ .\] In other words, a non-empty set (\(n>0\)) has an equal number of subsets of even and odd sizes. To prove this, we establish a one-to-one correspondence between even-sized and odd-sized subsets. Fix an arbitrary element \(x\) (here, the assumption \(n>0\) is critical).Every subset \(B\) not containing \(x\) is paired with \(B \cup \{x\}\). Clearly, in each pair, one subset has even size and the other has odd size. Let us demonstrate this with a toy example: suppose \(S=\{a, b, c, d\}\) (and \(x=a\)).
  

  



• Number of paths:  In each cell of Pascal's triangle, the number of paths to this cell from the top cell of the triangle is written, where the allowed moves are down-left or down-right. This is a direct consequence of the sum rule and the formula \[\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}.\] indeed, the last move to a cell comes from one of its two upper neighbors; thus, the number of paths to this cell is the sum of the numbers of paths to these two neighbors.
  

  

  
  In the diagram below, the number of ways to reach the highlighted cell is \[\binom{k+l}{k}=\binom{k+l}{l}\ .\] Indeed, from \(k+l\) steps, one must take \(k\) steps to the left (and, consequently, \(l\) steps to the right).