Số Eulerian (Eulerian Number) trong C++

Trong toán học, số Eulerian là một loại số tổ hợp đặc biệt. Nó định nghĩa số lượng hoán vị của các số từ 1 đến n sao cho có đúng m cặp phần tử liền kề thỏa mãn điều kiện phần tử sau lớn hơn phần tử trước (hoặc "số lần tăng" bằng m).

Ký hiệu: A(n, m) là số hoán vị của 1..n có đúng m lần tăng.

Ví dụ minh họa

Đầu vào: n = 4, m = 2

Đầu ra: 11

Giải thích:

Trong 24 hoán vị của 1..4, có 11 hoán vị có đúng 2 vị trí i mà a[i] < a[i+1].

Phương pháp giải - Công thức truy hồi

Số Eulerian có thể tính bằng công thức truy hồi sau:

A(n, m) = 0, nếu m >= n hoặc n = 0
A(n, m) = 1, nếu m = 0
A(n, m) = (n - m) * A(n-1, m-1) + (m + 1) * A(n-1, m)

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

#include <iostream>
using namespace std;

int countEulerianNumber(int n, int m) {
    if (m >= n || n == 0) return 0;
    if (m == 0) return 1;
    return (n - m) * countEulerianNumber(n - 1, m - 1)
         + (m + 1) * countEulerianNumber(n - 1, m);
}

int main() {
    int n = 5, m = 3;
    cout << "Số hoán vị Eulerian là " << countEulerianNumber(n, m);
    return 0;
}

Đầu ra

Số hoán vị Eulerian là 26

Lưu ý: Giải pháp đệ quy trên có độ phức tạp thời gian lớn do tính toán trùng lặp. Để tối ưu, nên sử dụng Quy hoạch động (Dynamic Programming) hoặc memoization để lưu trữ các giá trị trung gian.