ผลรวมกำลังสองของสัมประสิทธิ์ไบนอมิอัลใน C++ ผลรวมกำลังสองของสัมประสิทธิ์ไบนอมิอัลใน C++

สัมประสิทธิ์ไบนอมิอัล (Binomial Coefficients)

สัมประสิทธิ์ในขยายพหุนาม (a+b)ⁿ คือ ⁿCᵣ = n! / (r!(n-r)!)

สามารถจัดเรียงเป็นสามเหลี่ยมปาสคาลได้

ปัญหา

หาผลรวมของกำลังสองของสัมประสิทธิ์ไบนอมิอัลทั้งหมด:

Σ(r=0 to n) (ⁿCᵣ)² = (ⁿC₀)² + (ⁿC₁)² + ... + (ⁿCₙ)²

สูตรทางคณิตศาสตร์

มีข้อเท็จจริงที่สำคัญ: Σ(r=0 to n) (ⁿCᵣ)² = ²ⁿCₙ

ตัวอย่าง n = 5: ²⁵C₅ = 252

ตัวอย่างโค้ด C++ (คำนวณโดยตรง)

#include <iostream>
using namespace std;

int fact(int n) {
    int res = 1;
    for (int i = 2; i <= n; i++) res *= i;
    return res;
}

int nCr(int n, int r) {
    return fact(n) / (fact(r) * fact(n - r));
}

int main() {
    int n = 5;
    int sum = 0;
    for (int r = 0; r <= n; r++) {
        int coeff = nCr(n, r);
        sum += coeff * coeff;
    }
    cout << "Sum of squares of binomial coefficients: " << sum;
    return 0;
}

โค้ดแบบมีประสิทธิภาพ (ใช้สูตร ²ⁿCₙ)

#include <iostream>
using namespace std;

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

int main() {
    int n = 5;
    cout << "Sum = " << nCr(2 * n, n); // 10C5 = 252
    return 0;
}

ผลลัพธ์

252