Python Programs Calculate Value of nCr

nCr, also known as the combination formula, is a mathematical concept used to find the number of ways to choose r elements from a set of n elements without considering the order. nCr counts unique selections, meaning order does not matter. 5C2 means how many ways to choose 2 items from 5 items. Here,

• n: Total number of items
• r: Number of selections

Combinations are used in probability, statistics, and combinatorics. This article discusses various methods in Python to calculate nCr, with explanations and examples.

1. Using Factorial Formula

The factorial of a non-negative integer n (denoted as n!) is the product of all positive integers from 1 to n. For Example, 3! = 3 × 2 × 1 = 6

The mathematical formula to calculate combinations nCr is: nCr = n! / r!(n−r)!​

Where:

• n! (n factorial) = n×(n−1)×(n−2)×…×1
• r! (r factorial) = r×(r−1)×…×1
• (n – r)! = Factorial of the difference between n and r.

For Example, 5C3 = 5! / 3! (5-3)!

Here, we are using math.factorial() function which is in Python’s math module that returns the factorial of a given non-negative integer.

• math.factorial(5)) = 5! = 5 × 4 × 3 × 2 × 1 = 120.
• math.factorial(3)) = 3! = 3 × 2 × 1 = 6.
• math.factorial(5-3)) = math.factorial(2)) = 2! = 2 × 1 = 2.

Once we get all the factorials, we put the values in the formula to get the result: (120 / 6 × 2) = 10

Code Example

import math

def calculate_nCr(n, r):
    if r > n:
        return 0
    return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))

n = 5
r = 3
result = calculate_nCr(n, r)
print(result) # Output: 10Code language: Python (python)

Explanation

• Calculate n!, r!, and (n−r)! using math.factorial and plug them into the formula.
• Use integer division // which always returns an integer result by discarding the decimal part to avoid floating-point precision issues.

2. Using the math.comb Function (Python 3.8+)

math.comb(n, r) is a built-in function in Python that calculates the number of ways to choose r elements from n elements without considering the order (i.e., nCr or combinations). It returns an integer value (avoiding floating-point precision issues).

Code Example

import math

# nCr = math.comb(n, r)
n = 5
r = 3
result = math.comb(n, r)
print(result)  # Output: 10Code language: Python (python)

Explanation

• math.comb(n, r) directly computes nCr.
• It’s efficient and handles edge cases, such as r>n, where it returns 0.

3. Using Recursive Formula

Recursion is a programming technique where a function calls itself to solve smaller instances of a problem until a base condition is met.

Using recursion nCr can also be expressed as: nCr = (n−1)C(r−1) + (n−1)Cr.

Code Example

def calculate_nCr_recursive(n, r):
    if r == 0 or r == n:
        return 1
    return calculate_nCr_recursive(n - 1, r - 1) + calculate_nCr_recursive(n - 1, r)

n = 5
r = 2
result = calculate_nCr_recursive(n, r)
print(result)  # Output: 8Code language: Python (python)

Explanation

• Base cases: nCr=1 when r=0 or r=n.
• The recursion systematically breaks down the problem into smaller subproblems until it reaches the base cases.
• The results of these smaller problems are added together to calculate the larger problem.
• Note: This method is less efficient due to repeated calculations and should be used for learning purposes or small n,r values.
• Example walkthrough: suppose we want to calculate 5C2 (how many ways to choose 2 items from 5 items):
  • Step 1: Start with n = 5, r = 2:
    • 5C2 = 4C1 + 4C2
  • Step 2: Expand 4C1 and 4C2:
    • 4C1 = 3C0 + 3C1
    • 4C2=3C1+3C2
  • Step 3: Expand further until base cases are reached:
    • 3C0 = 1, 3C1 = 2, 3C2 = 3
  • Plugging these values back into the equations, you get:
    • 4C1 = 1 + 2 = 3
    • 4C2 = 2 + 3 = 5
  • Finally:
    • 5C2 = 3 + 5 = 8

Summary

Use math.comb to find nCr using Python for optimal performance in most cases.

• Using math.comb() (Python 3.8+):
  • Advantage: Built-in function, highly optimized, and fastest.
  • Time Complexity: O(r) Python’s internal implementation uses an iterative approach.
  • Space Complexity: O(1) Only a few variables are used; no extra storage is needed.
• Using Factorial Formula:
  • Advantage: Simple and easy to understand.
  • Time Complexity: O(n) Computing factorials require iterating up to n.
  • Space Complexity: O(1) Only a few integer variables are used.
• Using Recursion
  • Advantage: Simple and directly follows the binomial coefficient recurrence relation.
  • Time Complexity: O(2^n) Each call branches into two more calls, leading to exponential growth.
  • Space Complexity: O(n) recursive call stack depth.