เลขออยเลอร์ (Eulerian Number) ใน C++

บทนำ

ในคณิตศาสตร์ เลขออยเลอร์ เป็นเลขจัดหมู่พิเศษ ที่กำหนดจำนวนการเรียงสับเปลี่ยน (Permutations) ที่สมาชิกถัดไปมีค่ามากกว่าสมาชิกก่อนหน้าจำนวน m ตัว

สัญลักษณ์ A(n, m) คือการเรียงสับเปลี่ยนของ 1 ถึง n ที่มีความต่างระหว่างสองตัวเลขเป็น m

ตัวอย่าง

อินพุต: n = 4, m = 2

เอาต์พุต: 11

คำอธิบาย: จากการเรียงสับเปลี่ยนทั้งหมด 24 แบบของ 1-4 พบ 11 แบบที่ตรงเงื่อนไข

แนวทางแก้ปัญหา

ใช้สูตรเวียนเกิด (Recurrence Formula) ของเลขออยเลอร์:

A(n, m) = 0, ถ้า m > n หรือ n = 0
A(n, m) = 1, ถ้า m = 0
A(n, m) = (n-m)A(n-1, m-1) + (m+1)A(n-1, m)

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

#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 << "The number of Eulerian permutations is " << countEulerianNumber(n, m);
    return 0;
}

ผลลัพธ์

The number of Eulerian permutations is 26