Lesson 2

Let us begin by recalling some recurrence relations we have already encountered.

• Permutations with repetition.  Let \(T(n, k)\) be the number of words of length \(k\) over the alphabet \([n]\). The first position can be filled with any of \(n\) symbols, and the remaining task is to count the number of words of length \(k-1\). Thus, \[T(n, 0)=1, \quad T(n, k)=nT(n, k-1) \ .\] Therefore, \[\begin{align*}T(n,k)&=nT(n,k-1)=\\&=n^{2}T(n,k-2)=\\&\vdots\\&=n^{k}T(n,0)=n^{k} \ .\end{align*}\]


• Permutations without repetition.  The first position can be filled with any of \(n\) elements, and the remaining task is to form a queue of length \(k-1\) from the remaining \(n-1\) elements. Thus, \[\begin{equation*}P(n,0)=1, \quad P(n,k)=nP(n-1,k-1)\ .\end{equation*}\] Therefore, \[\begin{align*}P(n,k)&=nP(n-1,k-1)=\\&=n(n-1)P(n-2,k-2)=\\&=n(n-1)(n-2)P(n-3,k-3)=\dotsb=\\&=n(n-1)\dotsb(n-k+1)P(n-k,0)=\\&=\frac{n!}{(n-k)!}\ .\end{align*}\]


• Combinations without repetition.  Let \(C(n,k)\) be the number of \(k\)-element subsets of \([n]\). All such subsets can naturally be divided into two classes: those containing \(n\) and those not containing it. Thus, \[\begin{align*}C(n,0)&=1,\\ C(n,n)&=1,\\ C(n,k)&=C(n-1,k-1)+C(n-1,k) \ .\end{align*}\] The solution to this recurrence relation is known to be \[C(n,k)=\binom{n}{k}=\frac{n!}{k!(n-k)!}.\]


• Combinations with repetition.  Let \(R(n,k)\) be the number of ways to divide \(k\) identical coins among \(n\) people. These ways can naturally be divided into two classes:
  • The first person receives exactly zero coins. Then the remaining coins need to be distributed among the other people: \(R(n-1,k)\).
  
  
  • The first person receives at least one coin. This means we can preallocate one coin to them and then distribute the remaining coins: \(R(n, k-1)\).
  
  

  Therefore, \[R(n,k)=R(n-1,k)+R(n,k-1) \ .\] The initial conditions are: \(R(n,0)=1\) and \(R(0,k)=0\) for \(k>0\). The solution to this recurrence relation is known to be \[\binom{n+k-1}{n-1}=\binom{n+k-1}{k}\ .\]

  At this point, it is worth recalling grid or lattice paths. Let \(D(n,k)\) denote the number of paths from the point \((0,0)\) to the point \((n,k)\) (as usual, each step moves one unit up or to the right). The point \((n,k)\) can be reached either from \((n-1,k)\) or \((n,k-1)\), so \[D(n,k)=D(n-1,k)+D(n,k-1) \ .\] This is the same recurrence relation, but its solution is slightly different: \[\binom{n+k}{n}=\binom{n+k}{k}\] (out of \(n+k\) moves, we need to choose \(n\) moves to the right). The difference lies in the initial conditions: \(D(n,0)=D(0,k)=1\).

  Another perspective on combinations with repetition allows us to derive a new non-trivial identity. The first person can be given from zero to \(k\) coins, and the remaining coins are then distributed among the other \(n-1\) people. Hence, \[R(n,k)=\sum_{i=0}^{k}R(n-1,k-i)\ .\] While it is unclear how to simplify such a recurrence relation, we already know that its solution is \(R(n,k)=\binom{n+k-1}{n-1}=\binom{n+k-1}{k}\). Let us write this recurrence relation in terms of binomial coefficients: \[\binom{n+k-1}{n-1}=\sum_{i=0}^{k}\binom{n+k-i-2}{n-2}\ .\] Let \(N=n+k-2\) and \(m=n-2\). As \(i\) increases from \(0\) to \(k\), the upper index of the binomial coefficient decreases from \(n+k-2=N\) to \(n-2=m\). In these new variables, this formula becomes: \[\binom{N+1}{m+1}=\sum_{j=m}^{N}\binom{j}{m}\ .\] This identity is known as the summation formula for the upper index: in the sum, the lower index of the binomial coefficient remains unchanged, while the upper index grows. The combinatorial interpretation of this formula: to choose a subset of size \(m+1\) from \(\{0,1,\dotsc, N\}\), we can first fix its maximum element \(j\) and then choose \(m\) elements from \(\{0,1,\dotsc,j-1\}\).