How to implement falling factorial in Python

Falling factorial is a notion used in counting issues to describe the product of decreasing integers up to a given point. It is especially helpful when selecting a certain number of elements from a bigger collection is required, and order is important.

Definition of falling factorial

The sum of the firstkkdescending integers fromnnis the falling factorial ofnnwith a factor ofkk, represented as(n)k(n)_k. In terms of math, it is stated as:

Generalization of falling factorial

The falling factorial, which we can use to select the topkkelements out ofnnelements can be written as a ratio of factorials:

Recurrence relation

The recurrence connection can be used to relate the falling factorial to the factorial:

By using this relation, we may create a recursive definition of the falling factorial by expressing it in terms of a smaller falling factorial.

Implementation

Let’s implement the falling factorial in Python:

import math
def falling_factorial(n, k):
   
    if n < k:
        raise ValueError("n must be greater than or equal to k")
    
    result = math.factorial(n) // math.factorial(n - k)
    return result
# Example usage
n = 10
k = 3
result = falling_factorial(n, k)
print(f"The falling factorial ({n})_{k} is: {result}")

Explanation

  • Line 1: Here, we import the math module.

  • Lines 3–9: We calculate the falling factorial of a given number n with k terms.

    • Lines 5–6: We check if the value of n (representing the base) is less than the value of k (representing the number of terms). If n is less than k, it means there aren't enough terms to calculate the falling factorial, so it raises a ValueError with an appropriate message.

    • Line 8: We calculate the falling factorial using the formula n! / (n - k)!. It first calculates the factorial of n using math.factorial(n) and then divides it by the factorial of n - k to get the falling factorial. The // operator is used for integer division to ensure the result is an integer.

    • Line 9: It returns the calculated falling factorial value.

  • Lines 12–15: We print the result is an example of using the function with n=10 and k=3.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved