Trong toán học, số Eulerian là một loại số kết hợp đặc biệt. Nó xác định số lượng hoán vị trong đó phần tử tiếp theo là một số cụ thể lớn hơn phần tử trước.
Được biểu thị là,
A (n, m) là hoán vị từ 1 đến n trong đó hai số thay đổi theo m.
Tuyên bố sự cố: Trong bài toán này, chúng ta được cung cấp hai số m và n. Và chúng ta cần tìm số hoán vị là Số Eulerian.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào: n =4, m =2
Đầu ra: 11
Giải thích:
Tất cả các hoán vị của số từ 1 đến 4 là -
1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2
2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1
3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1
4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1
Trong tổng số 11 hoán vị có hiệu giữa hai số là m.
Phương pháp tiếp cận Giải pháp -
Để tìm số hoán vị, chúng tôi sẽ sử dụng công thức cho số eulerian,
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 hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra -
The number of Eulerian permutations is 26