หาค่าสัมประสิทธิ์ Binomial สูงสุด (Max Binomial Coefficient) ใน C

โจทย์

กำหนดจำนวนเต็มบวก N หาค่า Max ของ Binomial Coefficients:

C(n,0), C(n,1), C(n,2), ..., C(n,n)

ที่ C(n,r) = n! / (r! * (n-r)!)

คุณสมบัติทางคณิตศาสตร์

• 對稱性: C(n,r) = C(n,n-r)
• เพิ่มขึ้นจนถึงกลาง แล้วลดลง
• ค่าสูงสุดอยู่ที่ r = n/2 (ถ้า n คู่) หรือ r = n/2 และ n/2+1 (ถ้า n คี่)
• ค่าสูงสุด = C(n, ⌊n/2⌋)

ตัวอย่าง

n=4: C(4,0)=1, C(4,1)=4, C(4,2)=6, C(4,3)=4, C(4,4)=1 → Max=6
n=5: C(5,0)=1, C(5,1)=5, C(5,2)=10, C(5,3)=10, C(5,4)=5, C(5,5)=1 → Max=10

วิธีที่ 1: Pascal's Triangle (Dynamic Programming)

#include 

int maxBinomialCoeff(int n) {
    int C[n+1][n+1];
    int max = 0;
    
    for (int i = 0; i <= n; i++) {
        int limit = (i < n) ? i : n;
        for (int j = 0; j <= limit; j++) {
            if (j == 0 || j == i)
                C[i][j] = 1;
            else
                C[i][j] = C[i-1][j-1] + C[i-1][j];
            
            if (i == n && C[i][j] > max)
                max = C[i][j];
        }
    }
    return max;
}

วิธีที่ 2: คำนวณ C(n, n/2) โดยตรง (Efficient)

#include 

// คำนวณ C(n, k) แบบไม่ Overflow (มากที่สุด)
long long binomialCoeff(int n, int k) {
    if (k > n - k) k = n - k; // ใช้ Symmetry
    
    long long res = 1;
    for (int i = 0; i < k; i++) {
        res = res * (n - i) / (i + 1); // คูณก่อน หารทีหลัง ป้องกัน Fraction
    }
    return res;
}

int maxBinomialCoeffFast(int n) {
    return binomialCoeff(n, n / 2);
}

โปรแกรมสมบูรณ์

#include 

long long binomialCoeff(int n, int k) {
    if (k > n - k) k = n - k;
    long long res = 1;
    for (int i = 0; i < k; i++) {
        res = res * (n - i) / (i + 1);
    }
    return res;
}

int main() {
    int n;
    printf("Enter n: ");
    scanf("%d", &n);
    
    if (n < 0) {
        printf("Invalid input\n");
        return 1;
    }
    
    long long maxCoeff = binomialCoeff(n, n / 2);
    printf("Maximum Binomial Coefficient C(%d, %d) = %lld\n", n, n/2, maxCoeff);
    
    // แสดงทุกค่า (ถ้า n เล็ก)
    if (n <= 20) {
        printf("\nAll coefficients:\n");
        for (int r = 0; r <= n; r++) {
            printf("C(%d,%d) = %lld\n", n, r, binomialCoeff(n, r));
        }
    }
    return 0;
}

ผลลัพธ์:

Enter n: 5
Maximum Binomial Coefficient C(5, 2) = 10

All coefficients:
C(5,0) = 1
C(5,1) = 5
C(5,2) = 10
C(5,3) = 10
C(5,4) = 5
C(5,5) = 1

Complexity

ข้อควรระวัง: Overflow

• long long รองรับได้ถึง ~C(66,33) ≈ 7.2×10¹⁸
• ใหญ่กว่า → ใช้ BigInteger Library, GMP, หรือ Log Gamma Approximation