সি++-এ অয়লারিয়ান নম্বর

গণিতে, অয়লারিয়ান নম্বর হলো একটি বিশেষ ধরনের কম্বিনেশন নম্বর। এটি সেই পারমুটেশনগুলোর সংখ্যা নির্ধারণ করে যেখানে পরবর্তী উপাদান পূর্ববর্তী উপাদানের থেকে একটি নির্দিষ্ট সংখ্যা বড়।

নির্দেশিত হিসেবে,

A(n, m) হলো ১ থেকে n পর্যন্ত পারমুটেশন যেখানে দুটি সংখ্যার পার্থক্য m।

সমস্যা বিবরণ: এই সমস্যায় আমাদের দুটি সংখ্যা m এবং n দেওয়া হয়েছে। এবং আমাদের অয়লারিয়ান নম্বর স্বরূপ পারমুটেশনগুলোর সংখ্যা বের করতে হবে।

উদাহরণ দিয়ে বুঝি

ইনপুট: n = 4, m = 2

আউটপুট: ১১

ব্যাখ্যা:

১ থেকে ৪ পর্যন্ত সংখ্যাগুলোর সব পারমুটেশন:

১ ২ ৩ ৪      ১ ২ ৪ ৩      ১ ৩ ২ ৪      ১ ৩ ৪ ২      ১ ৪ ২ ৩      ১ ৪ ৩ ২
২ ১ ৩ ৪      ২ ১ ৪ ৩      ২ ৩ ১ ৪      ২ ৩ ৪ ১      ২ ৪ ১ ৩      ২ ৪ ৩ ১
৩ ১ ২ ৪      ৩ ১ ৪ ২      ৩ ২ ১ ৪      ৩ ২ ৪ ১      ৩ ৪ ১ ২      ৩ ৪ ২ ১
৪ ১ ২ ৩      ৪ ১ ৩ ২      ৪ ২ ১ ৩      ৪ ২ ৩ ১      ৪ ৩ ১ ২      ৪ ৩ ২ ১

এই সব পারমুটেশনের মধ্যে ১১টি পারমুটেশনে দুটি সংখ্যার পার্থক্য m।

সমাধানের পদ্ধতি

পারমুটেশনের সংখ্যা বের করতে আমরা অয়লারিয়ান নম্বরের সূত্র ব্যবহার করব:

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)

সমাধান minhaj করার প্রোগ্রাম

#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