Python Program to Find nCr and nPr

You can find nCr and nPr in Python by using the formulas nCr = factorial(n) // (factorial(r) * factorial(n - r)) and nPr = factorial(n) // factorial(n - r), where factorial is the product of all positive integers up to a number.

Examples

Inputn=5, r=3

OutputnCr = 10, nPr = 60

Inputn=6, r=0

OutputnCr = 1, nPr = 1

Inputn=4, r=4

OutputnCr = 1, nPr = 24

How to Think About It

To find nCr and nPr, first understand that nCr counts how many ways to choose r items from n without caring about order, while nPr counts how many ways to arrange r items from n with order. Both use factorials: nCr divides factorial of n by factorial of r and factorial of n minus r; nPr divides factorial of n by factorial of n minus r.

Algorithm

1

Get input values for n and r.

2

Calculate factorial of n, r, and n minus r.

3

Compute nCr using factorial(n) divided by (factorial(r) times factorial(n - r)).

4

Compute nPr using factorial(n) divided by factorial(n - r).

5

Return or print the values of nCr and nPr.

Code

python

def factorial(num):
    result = 1
    for i in range(1, num + 1):
        result *= i
    return result

def nCr(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r))

def nPr(n, r):
    return factorial(n) // factorial(n - r)

n = 5
r = 3
print(f"nCr = {nCr(n, r)}, nPr = {nPr(n, r)}")

Output

nCr = 10, nPr = 60

Dry Run

Let's trace n=5 and r=3 through the code

1

Calculate factorial(5)

factorial(5) = 1*2*3*4*5 = 120

2

Calculate factorial(3)

factorial(3) = 1*2*3 = 6

3

Calculate factorial(2)

factorial(2) = 1*2 = 2

4

Calculate nCr

nCr = 120 // (6 * 2) = 120 // 12 = 10

5

Calculate nPr

nPr = 120 // 2 = 60

Step	Operation	Value
1	factorial(5)	120
2	factorial(3)	6
3	factorial(2)	2
4	nCr = 120 // (6*2)	10
5	nPr = 120 // 2	60

Why This Works

Step 1: Factorial Calculation

The factorial function multiplies all numbers from 1 up to the given number to get the factorial value.

Step 2: Calculate nCr

nCr uses the formula factorial(n) // (factorial(r) * factorial(n - r)) to count combinations without order.

Step 3: Calculate nPr

nPr uses the formula factorial(n) // factorial(n - r) to count permutations with order.

Alternative Approaches

Using math module

python

import math

def nCr(n, r):
    return math.comb(n, r)

def nPr(n, r):
    return math.perm(n, r)

n = 5
r = 3
print(f"nCr = {nCr(n, r)}, nPr = {nPr(n, r)}")

This uses Python's built-in math functions for combinations and permutations, which is faster and simpler.

Recursive factorial

python

def factorial(num):
    if num == 0 or num == 1:
        return 1
    else:
        return num * factorial(num - 1)

n = 5
r = 3
print(f"nCr = {factorial(n) // (factorial(r) * factorial(n - r))}, nPr = {factorial(n) // factorial(n - r)}")

This uses recursion to calculate factorial but can be slower for large numbers due to call stack overhead.

Complexity: O(n) time, O(1) space

Time Complexity

Calculating factorial takes O(n) time because it multiplies numbers from 1 to n. Both nCr and nPr depend on factorial calculations.

Space Complexity

The space used is O(1) because calculations use a fixed amount of memory without extra data structures.

Which Approach is Fastest?

Using Python's built-in math.comb and math.perm is fastest and most efficient, as they are optimized in C.

Approach	Time	Space	Best For
Manual factorial loop	O(n)	O(1)	Learning and small inputs
Recursive factorial	O(n)	O(n)	Understanding recursion, smaller inputs
math.comb and math.perm	O(1) or optimized	O(1)	Production and large inputs