Số Entringer (Entringer Number) trong C++

Số Entringer E(n, k) là số lượng hoán vị của tập {1, 2, ..., n+1} bắt đầu bằng k+1 và thay đổi chiều tăng/giảm xen kẽ (up-down permutations).

Công thức truy hồi

E(0, 0) = 1
E(n, 0) = 0 (với n > 0)
E(n, k) = E(n, k-1) + E(n-1, n-k)  (với 1 ≤ k ≤ n)

Ví dụ

E(5, 3) = 14

Chương trình minh họa (Đệ quy + Memoization)

Đệ quy đơn giản sẽ rất chậm do tính toán trùng lặp. Cần dùng mảng nhớ (memoization) hoặc quy hoạch động bottom-up.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_N = 100;
long long memo[MAX_N][MAX_N];

long long EntringerNumber(int n, int k) {
    if (n == 0 && k == 0) return 1;
    if (k == 0) return 0;
    if (memo[n][k] != -1) return memo[n][k];
    
    return memo[n][k] = EntringerNumber(n, k - 1) + EntringerNumber(n - 1, n - k);
}

int main() {
    memset(memo, -1, sizeof(memo));
    int n = 5, k = 3;
    cout << "E(" << n << ", " << k << ") = " << EntringerNumber(n, k) << endl;
    
    // In bảng nhỏ để tham khảo
    cout << "\nBang Entringer n=0..5:\n";
    for(int i=0; i<=5; i++) {
        for(int j=0; j<=i; j++) 
            cout << EntringerNumber(i, j) << "\t";
        cout << endl;
    }
    return 0;
}

Đầu ra

E(5, 3) = 14

Bang Entringer n=0..5:
1	
0	1	
0	1	1	
0	1	2	2	
0	2	4	5	5	
0	5	10	14	16	16