Combinations and Binomial Coefficients

A combination chooses k of n distinct objects without caring about order. C(n,k) differs from a permutation because every selected set has k! internal orders. Pascal’s recurrence counts combinations by whether a particular object is included, avoiding division and working naturally with DP. This lesson computes exact small coefficients, with an explicit n bound preventing long-long overflow.

Prerequisites: Basic DP; factorials; permutations.

Build the idea

1. 1. Distinguish selection from ordering

   Choosing {A,B} is the same combination as {B,A}, while these are different ordered selections. There are n(n−1)…(n−k+1) ordered selections, and each k-set appears k! times. Hence C(n,k)=n!/(k!(n−k)!). This counts WITHOUT replacement; choosing the same object repeatedly is a different model covered by Stars and Bars.

2. 2. Derive Pascal’s recurrence

   Fix one distinguished object. A k-set either excludes it, choosing k of the remaining n−1, or includes it, choosing the other k−1 from n−1. These two families are disjoint and exhaustive, so their counts add. Boundary choices C(n,0)=C(n,n)=1 represent the unique empty/full selection.

   $$C(n,k)=C(n-1,k)+C(n-1,k-1)$$

3. 3. Build the triangle in dependency order

   Initialize row zero with C(0,0)=1. For each next row, set both ends to one and compute interior entries from the previous row. The program keeps the full table for O(1) later queries. A one-row variant can reduce memory but must update k downward so new-row values do not overwrite needed previous-row data.

4. 4. Trace row five

   Rows start [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1], then [1,5,10,10,5,1]. Thus C(5,2)=10 and C(5,3)=10, reflecting the bijection between selecting k objects and leaving n−k unselected. C(0,0)=1, and k outside 0..n gives zero rather than an invalid table access.

   $$C(n,k)=C(n,n-k)$$

5. 5. Choose exact or modular arithmetic intentionally

   Even when C(n,k) fits, separately forming n! may overflow. Pascal uses smaller directly relevant sums, but coefficients still grow rapidly. N≤60 ensures every stored exact coefficient fits long long, including C(60,30)=118264581564861424. For larger N, choose modular arithmetic with a stated modulus or an arbitrary-precision representation; do not silently wrap.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Choose exact or modular arithmetic intentionally Even when C(n,k) fits, separately
// forming n!
#include<iostream>
#include<vector>
int main(){
    int N,q;
    std::cin>>N>>q;
    std::vector<std::vector<long long>>choose(N+1,std::vector<long long>(N+1,0));
    for(int n=0;n<=N;++n){
        choose[n][0]=choose[n][n]=1;
        for(int k=1;k<n;++k){
            choose[n][k]=choose[n-1][k]+choose[n-1][k-1];
        }
    }
    while(q--){
        int n,k;
        std::cin>>n>>k;
        std::cout<<(k<0||k>n?0:choose[n][k])<<'\n';
    }
}

Complexity analysis

O(N²) preprocessing time and memory, O(1) each query. A descending one-row DP uses O(N) memory when only one final row is required, but that is not this multi-row query implementation. N≤60 is the exact-arithmetic limit chosen here, not a claim of unlimited binomial storage.

Example input and output

Read N q, 0≤N≤60, then q pairs n k with 0≤n≤N and int k. Print exact C(n,k), zero for invalid k.

Input

5 4
5 2
5 3
0 0
4 5

Output

10
10
1
0

Row five has coefficients [1,5,10,10,5,1]. Choosing nothing from zero has one outcome.

Practical applications

Use for subset counts, probability sample spaces, lattice paths and combinatorial identities. The previous modular table handles many large-but-below-prime queries faster after linear preprocessing. Pascal works over any modulus using addition, while inverse-factorial formulas need invertibility.

Check your understanding

Why do the two Pascal terms add without subtracting overlap?

Put it into practice

Check symmetry and that the sum of row n equals 2ⁿ.