帕斯卡三角第n行第k项递推公式C(n,k)推导问询

Got it, let's break down why C(n,k) = [(n - k + 1)/k] * C(n,k-1) holds—you don't need to rely on the addition formula C(n,k)=C(n-1,k-1)+C(n-1,k) for this one; we can go straight back to the core definition of combinations, which makes this derivation straightforward.

Step 1: Start with the factorial definition of combinations #

First, remember that the combination C(n,k) (counting ways to choose k elements from n distinct elements) is defined using factorials as:

C(n,k) = n! / (k! * (n - k)!)

Similarly, C(n,k-1) looks like this:

C(n,k-1) = n! / ((k-1)! * (n - (k-1))!) = n! / ((k-1)! * (n - k + 1)!)

Step 2: Simplify the right-hand side of the recurrence #

Let's calculate [(n - k + 1)/k] * C(n,k-1) by substituting the definition of C(n,k-1):

[(n - k + 1)/k] * [n! / ((k-1)! * (n - k + 1)!))]

Now let's simplify term by term:

• Cancel out the (n - k + 1) terms in the numerator and denominator (since (n - k + 1)! = (n - k + 1) * (n - k)!)
• Replace k in the denominator with k * (k-1)! (because k! = k*(k-1)!)

After these substitutions, the expression becomes:

n! / (k * (k-1)! * (n - k)!) = n! / (k! * (n - k)!)

Which is exactly the definition of C(n,k)! That's the proof right there.

Bonus: Why this recurrence matters #

Unlike the addition formula (which builds combinations using smaller n values), this recurrence lets you compute C(n,k) starting from C(n,0) = 1 and iterating up to k. It's perfect for programming because it avoids calculating massive factorials directly (which can cause overflow even for moderately large n and k).

For example, to compute C(5,2):

• Start with C(5,0) = 1
• C(5,1) = [(5-1+1)/1] * C(5,0) = 5 * 1 = 5
• C(5,2) = [(5-2+1)/2] * C(5,1) = (4/2)*5 = 10
  Which matches the expected result.

内容的提问来源于stack exchange，提问作者sidda vinod reddy