Eulerian number
(include/emthrm/math/formal_power_series/eulerian_number.hpp)

View this file on GitHub
Last update: 2023-02-25 16:35:06+09:00
Include: #include "emthrm/math/formal_power_series/eulerian_number.hpp"

Eulerian number

\[A_n(x) = \sum_{m = 0}^n A(n, m) x^m\]

で定義される $A(n, m)$ である。ただし $A_n(x)$ は

\[\sum_{n = 0}^{\infty} A_n(x) \dfrac{t^n}{t!} = \dfrac{x - 1}{x - e^{(x - 1)t}}\]

で定義される Eulerian polynomials である。

\[A(n, m) = \begin{cases} 1 & (m = 0), \\ 0 & (n = m > 0), \\ (n - m) A(n - 1, m - 1) + (m + 1) A(n - 1, m) & (0 < m < n) \end{cases}\]

という漸化式をもつ。

一般項

\[A(n, m) = \sum_{k = 0}^m (-1)^k \binom{n + 1}{k} (m + 1 - k)^n\]

である。

時間計算量

	時間計算量
	$O(NM)$
形式的冪級数版	$O(N\log{N})$

仕様

名前	戻り値
`template <typename T>` `std::vector<std::vector<T>> eulerian_number(const int n, const int m);`	Eulerian number $A(i, j)$ ($0 \leq i \leq n,\ 0 \leq j \leq m$) の数表

形式的冪級数版

名前	戻り値
`template <unsigned int T>` `std::vector<MInt<T>> eulerian_number_init_by_fps(const int n);`	Eulerian number $A(n, j)$ ($0 \leq j \leq n$) の数表

参考文献

Leonhard Euler: Institutiones calculi differentialis (1755).
https://en.wikipedia.org/wiki/Eulerian_number
http://oeis.org/wiki/Eulerian_numbers,_triangle_of
~~https://min-25.hatenablog.com/entry/2015/04/07/160154~~

Code

#ifndef EMTHRM_MATH_FORMAL_POWER_SERIES_EULERIAN_NUMBER_HPP_
#define EMTHRM_MATH_FORMAL_POWER_SERIES_EULERIAN_NUMBER_HPP_

#include <vector>

namespace emthrm {

template <typename T>
std::vector<std::vector<T>> eulerian_number(const int n, const int m) {
  std::vector<std::vector<T>> a(n + 1, std::vector<T>(m + 1, 0));
  a[0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    a[i][0] = 1;
    for (int j = 1; j < i; ++j) {
      a[i][j] = a[i - 1][j - 1] * (i - j) + a[i - 1][j] * (j + 1);
    }
  }
  return a;
}

}  // namespace emthrm

#endif  // EMTHRM_MATH_FORMAL_POWER_SERIES_EULERIAN_NUMBER_HPP_

#line 1 "include/emthrm/math/formal_power_series/eulerian_number.hpp"



#include <vector>

namespace emthrm {

template <typename T>
std::vector<std::vector<T>> eulerian_number(const int n, const int m) {
  std::vector<std::vector<T>> a(n + 1, std::vector<T>(m + 1, 0));
  a[0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    a[i][0] = 1;
    for (int j = 1; j < i; ++j) {
      a[i][j] = a[i - 1][j - 1] * (i - j) + a[i - 1][j] * (j + 1);
    }
  }
  return a;
}

}  // namespace emthrm

Eulerian number (include/emthrm/math/formal_power_series/eulerian_number.hpp)