Negative Binomial Coefficients

Combinatorics · Axiom Academy

LESSON Negative Binomial Coefficients Extending the Binomial Theorem beyond non-negative integers 1. Generalizing Binomial Coefficients The standard binomial coefficient is defined for non-negative integers n and k: But we can extend this definition to any real (or complex) value of n by using the falling factorial notation: where n^(k) = n(n-1)(n-2)...(n-k+1) is the falling factorial This definition works for any value of n, including negative integers! 2. The Negative Binomial Formula When n is a negative integer (-n), we can derive a beautiful relationship. Let's compute C(-n,k): Expanding the falling factorial: Factor out (-1)^k from the numerator: This relates negative binomial coefficients to standard ones! Using the generalized binomial theorem, we can expand (1+x)^(-n) as an infinite series: Substituting our formula for C(-n,k): This is the geometric series! Valid for |x| < 1. 4. Combinations with Repetition There's a beautiful combinatorial interpretation of C(n+k-1,k) - it counts the number of ways to select k items from n types with repetition allowed! The number of ways to place k identical items into n distinct bins is: This connects our negative binomial coefficients (up to sign) with a fundamental counting problem: How many ways can we select 3 fruits from apple, banana, cherry with repetition? Answer: C(3+3-1,3) = C(5,3) = 10 Some selections: AAA, AAB, AAC, ABB, ABC, ACC, BBB, BBC, BCC, CCC 5. Applications in Generating Functions

This is the written version of the interactive lesson above. See the full Combinatorics course.