เลข Entringer (Entringer Number) ใน C++

บทนำ

เลข Entringer E(n, k) คือจำนวนการเรียงสับเปลี่ยนของ {1, 2, ..., n+1} ที่เริ่มต้นด้วย k+1 และสลับกันระหว่างลดและเพิ่ม

ความสัมพันธ์เวียนเกิด (Recurrence Relation)

E(n, k) = E(n, k-1) + E(n-1, n-k)
Base cases:
E(0, 0) = 1
E(n, 0) = 0 (สำหรับ n > 0)

ตัวอย่าง

E(5, 3) = 14

โปรแกรมตัวอย่าง

#include <iostream>
using namespace std;

int EntringerNumber(int n, int k) {
    if (n == 0 && k == 0) return 1;
    if (k == 0) return 0;
    return EntringerNumber(n, k - 1) + EntringerNumber(n - 1, n - k);
}

int main() {
    int n = 5, k = 3;
    cout << "E(" << n << ", " << k << ") = " << EntringerNumber(n, k);
    return 0;
}

ผลลัพธ์

E(5, 3) = 14