✦ScienexySCIENCE KNOWLEDGE LIBRARY
General science · SCI-FORM-ALG-050

Binomial Coefficient Recurrence Relation

The binomial coefficient recurrence relation expresses a binomial coefficient as the sum of two adjacent binomial coefficients from the preceding row of Pascal's triangle.

\(C(n, k) = C(n - 1, k - 1) + C(n - 1, k)\)

What this formula means

Definition

The binomial coefficient recurrence relation expresses a binomial coefficient as the sum of two adjacent binomial coefficients from the preceding row of Pascal's triangle.

Interpretation

The number of ways to select k objects from n objects equals the number of selections that include a particular object plus the number of selections that exclude that object.

Mathematical Significance

This recurrence is the mathematical foundation of Pascal's triangle and provides an efficient method for calculating binomial coefficients without directly evaluating factorial expressions.

Special Cases

  • C(n, 0) = 1 for every nonnegative integer n.

  • C(n, n) = 1 for every nonnegative integer n.

  • For 1 ≤ k ≤ n - 1, the recurrence combines two coefficients from row n - 1.

  • Binomial coefficients satisfy the symmetry relation C(n, k) = C(n, n - k).

Scientific principle

Principle

Every selection of k objects from n objects either contains a specified object or does not contain it.

Derivation

  • Consider a collection of n distinct objects and choose one particular object.

  • Count the selections of k objects that include the particular object. The remaining k - 1 objects must be selected from the other n - 1 objects, giving C(n - 1, k - 1) possibilities.

  • Count the selections that exclude the particular object. All k selected objects must come from the remaining n - 1 objects, giving C(n - 1, k) possibilities.

  • These two cases are mutually exclusive and cover every possible selection of k objects.

  • Add the two counts to obtain C(n, k) = C(n - 1, k - 1) + C(n - 1, k).

Final Result

C(n, k) = C(n - 1, k - 1) + C(n - 1, k)

Variables and their meanings

C(n, k)

The number of ways to choose k objects from n distinct objects; also written as the binomial coefficient (n choose k).

N

Total number of available objects, where n is a nonnegative integer.

K

Number of objects selected, where 0 ≤ k ≤ n.

C(n 1, k 1)

Number of selections that include a specified object.

C(n 1, k)

Number of selections that exclude the specified object.

SI units and conversions

Si Unit

Not applicable; binomial coefficients are dimensionless counting numbers.

Dimensional Formula

Dimensionless.

Explanation

A binomial coefficient counts combinations and therefore has no physical unit or dimension.

Conditions of use

  • The parameters n and k must be integers satisfying 1 ≤ k ≤ n - 1 for the interior recurrence.

  • The boundary values C(n, 0) = 1 and C(n, n) = 1 must be supplied.

  • The objects being counted are treated as distinct.

  • The selection order does not matter.

Limitations and assumptions

  • The recurrence calculates combinations, not permutations in which order matters.

  • The standard recurrence requires valid integer indices.

  • Boundary cases must be handled separately to avoid invalid indices.

  • The recurrence is mathematically equivalent to the factorial definition but may require previously calculated coefficients.

Step-by-step worked examples

ProblemGivenSolutionAnswer

Calculate C(5, 2) using the recurrence relation.

N

5

K

2

Recurrence

C(n, k) = C(n - 1, k - 1) + C(n - 1, k)

  • Apply the recurrence: C(5, 2) = C(4, 1) + C(4, 2).

  • Calculate C(4, 1) = 4.

  • Calculate C(4, 2) = C(3, 1) + C(3, 2) = 3 + 3 = 6.

  • Substitute the values: C(5, 2) = 4 + 6.

  • Therefore, C(5, 2) = 10.

C(5, 2) = 10.

Calculate C(6, 3) using Pascal's recurrence relation.

N

6

K

3

  • Apply the recurrence: C(6, 3) = C(5, 2) + C(5, 3).

  • Using the previous row of Pascal's triangle, C(5, 2) = 10 and C(5, 3) = 10.

  • Add the two coefficients: C(6, 3) = 10 + 10.

  • Therefore, C(6, 3) = 20.

C(6, 3) = 20.

Real-world applications

  • Constructing Pascal's triangle and generating binomial coefficients.

  • Calculating the number of possible groups or selections in combinatorics.

  • Expanding powers of binomial expressions using the binomial theorem.

  • Developing efficient dynamic programming algorithms for combination calculations.

  • Solving probability problems involving selections from finite sets.

Formula Meaning

Definition

The binomial coefficient recurrence relation expresses a binomial coefficient as the sum of two adjacent binomial coefficients from the preceding row of Pascal's triangle.

Interpretation

The number of ways to select k objects from n objects equals the number of selections that include a particular object plus the number of selections that exclude that object.

Mathematical Significance

This recurrence is the mathematical foundation of Pascal's triangle and provides an efficient method for calculating binomial coefficients without directly evaluating factorial expressions.

Special Cases

  • C(n, 0) = 1 for every nonnegative integer n.

  • C(n, n) = 1 for every nonnegative integer n.

  • For 1 ≤ k ≤ n - 1, the recurrence combines two coefficients from row n - 1.

  • Binomial coefficients satisfy the symmetry relation C(n, k) = C(n, n - k).

Sources and further reading

No source has been supplied for this item yet. Treat the claim as needing editorial verification.

← Back to Formula Hub · Suggest a correction or source