Combinations and Permutations in C – nCr and nPr Without Overflow

Combinations and permutations in C are computed using two related formulas. A combination C(n, r) counts the number of ways to choose r items from n items where order does not matter. A permutation P(n, r) counts the number of ways to arrange r items chosen from n items where order matters.

C(n, r) = n! / (r! × (n−r)!) — selecting a committee of 3 from 10 people = C(10,3) = 120
P(n, r) = n! / (n−r)! — filling 3 medals (gold, silver, bronze) from 10 athletes = P(10,3) = 720

The programs below use a multiplicative formula instead of computing factorials directly. Direct factorial computation overflows even 64-bit integers for n ≥ 21. The multiplicative approach avoids this by dividing at each step, keeping intermediate values small.

How It Works — Step by Step

Compute C(5, 2) with the multiplicative formula:

Step i	Multiply by (n−i)	Divide by (i+1)	result
0	× (5−0) = 5	÷ 1	5
1	× (5−1) = 4	÷ 2	10

C(5,2) = 10. Verify: 5!/(2!×3!) = 120/(2×6) = 10 ✓

Compute P(5, 2):

Step i	Multiply by (n−i)	result
0	× 5	5
1	× 4	20

P(5,2) = 20. Verify: 5!/(5−2)! = 120/6 = 20 ✓

C Program for Combinations and Permutations

/* Combinations (nCr) and Permutations (nPr) in C
 * Uses multiplicative formula — avoids factorial overflow.
 * Compile: gcc -ansi -Wall -Wextra comb.c -o comb */
#include <stdio.h>

/* C(n,r) = n*(n-1)*...*(n-r+1) / r! computed incrementally */
long ncr(int n, int r)
{
    long result = 1;
    int i;
    if (r > n - r) r = n - r; /* use smaller r; C(n,r) == C(n,n-r) */
    for (i = 0; i < r; i++) {
        result *= (n - i);
        result /= (i + 1);
    }
    return result;
}

/* P(n,r) = n*(n-1)*...*(n-r+1) */
long npr(int n, int r)
{
    long result = 1;
    int i;
    for (i = 0; i < r; i++)
        result *= (n - i);
    return result;
}

int main(void)
{
    int n, r;

    printf("Enter n and r (where r <= n): ");
    scanf("%d %d", &n, &r);

    if (n < 0 || r < 0 || r > n) {
        printf("Error: need 0 <= r <= n.\n");
        return 1;
    }

    printf("%dC%d (combinations) = %ld\n", n, r, ncr(n, r));
    printf("%dP%d (permutations) = %ld\n", n, r, npr(n, r));

    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra comb.c -o comb
./comb

Sample Input and Output

Enter n and r (where r <= n): 5 2
5C2 (combinations) = 10
5P2 (permutations) = 20

Enter n and r (where r <= n): 10 3
10C3 (combinations) = 120
10P3 (permutations) = 720

Enter n and r (where r <= n): 20 10
20C10 (combinations) = 184756
20P10 (permutations) = 670442572800

Enter n and r (where r <= n): 5 0
5C0 (combinations) = 1
5P0 (permutations) = 1

Code Explanation

ncr — Why the Multiplicative Formula Works

The combinatorial formula C(n,r) = n!/(r!×(n−r)!) can be rewritten as:

C(n,r) = (n/1) × ((n-1)/2) × ((n-2)/3) × ... × ((n-r+1)/r)

At every step, the partial product is a binomial coefficient and is always an integer. Dividing by (i+1) immediately after multiplying by (n-i) keeps numbers small. For C(20,10), the largest intermediate value is C(20,10) = 184,756 — far smaller than 20! ≈ 2.4×10¹⁸.

if (r > n-r) r = n-r — uses the symmetry C(n,r) = C(n,n−r). C(20,18) needs only 2 loop steps, not 18. C(20,10) is the worst case and takes 10 steps.
result *= (n-i) then result /= (i+1) — the order matters. Multiply first, divide second. At step i, result × (n-i) is always divisible by (i+1) (a mathematical property of binomial coefficients).

npr — Permutation Formula

P(n,r) = n!/(n−r)! = n × (n−1) × ... × (n−r+1). The loop multiplies r consecutive integers starting from n down to (n−r+1). No division needed — permutations are always a product of r consecutive integers.

Overflow warning: P(n,r) grows fast. P(20,10) = 670,442,572,800 — this fits in a 64-bit long (max ~9.2×10¹⁸) but would overflow a 32-bit int. On systems where long is 32 bits, use long long and %lld for larger inputs.

Combinations vs Permutations — Quick Reference

Situation	Type	Formula
Choose 3 people for a team from 10	Combination	C(10,3) = 120
Assign 1st, 2nd, 3rd place from 10	Permutation	P(10,3) = 720
Choose a 4-digit PIN where order matters	Permutation	P(10,4) = 5040
Select 6 lottery numbers from 49	Combination	C(49,6) = 13,983,816
C(n,0) and C(n,n)	Combination	Always = 1
P(n,1) and C(n,1)	Both	Always = n

What This Program Teaches

Avoiding factorial overflow — computing n! directly fails for n ≥ 21 even with 64-bit integers. The multiplicative formula stays manageable for any n where the final result fits in the target type.
Symmetry optimization — C(n,r) = C(n,n−r) means C(20,18) is computed in 2 steps instead of 18. Recognizing and using mathematical symmetry is a core optimization technique.
Function decomposition — splitting ncr() and npr() into separate functions makes each testable independently and keeps main() clean.
Input validation — the condition r < 0 || r > n guards against inputs that have no mathematical meaning and would produce wrong results silently.

Related Programs

Practice what you learned: C Aptitude Questions — or try our C Programming Quiz App on Android.

Combinations and Permutations in C (nCr and nPr)