C++でのオイラー数

数学では、オイラー数 特殊なタイプの組み合わせ番号です。これは、次の要素が前の要素よりも特定の数大きい順列の数を定義します。

と表記

A（n、m） は1からnまでの順列で、2つの数値はmによって異なります。

問題の説明： この問題では、2つの数mとnが与えられます。そして、オイラー数である順列の数を見つける必要があります。

問題を理解するために例を見てみましょう

入力： n =4、m =2

出力： 11

説明：

1から4までの数のすべての順列は-

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

11の順列すべてのうち、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）

ソリューションの動作を説明するプログラム

例

#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