モンモール数 (Montmort number)
(include/emthrm/math/montmort_number.hpp)

• View this file on GitHub
• Last update: 2022-12-15 22:18:37+09:00
• Include: #include "emthrm/math/montmort_number.hpp"

\[!n = \begin{cases} 1 & (n = 0), \\ 0 & (n = 1), \\ (n - 1)(!(n - 1) + !(n - 2)) & (n \geq 2) \end{cases}\]

という漸化式をもつ、完全順列の個数 $!n$ である。これを解くと

\[!n = n! \sum_{k = 0}^n \dfrac{(-1)^k}{k!}\]

という一般項が得られる。

指数型母関数は

\[\sum_{n = 0}^\infty !n \frac{x^n}{n!} = \dfrac{e^{-x}}{1 - x}\]

である。

完全順列 (complete permutation) / 攪乱順列 (derangement)

大きさ $N$ の順列 $P$ の内、任意の $i \in \lbrace 1, 2, \ldots, N \rbrace$ に対して $P_i \neq i$ を満たすものである。

時間計算量

$O(N)$

仕様

名前	戻り値
template <typename T> std::vector<T> montmort_number(const int n);	モンモール数 $!i$ ($1 \leq i \leq n$) の数表

参考文献

• Pierre Remond de Montmort: Essay d’analyse sur les jeux de hazard, 2nd edition (1713).
• https://en.wikipedia.org/wiki/Derangement
• https://mathtrain.jp/montmort
• http://kyuridenamida.hatenablog.com/entry/2016/04/27/015414

Submissons

https://judge.yosupo.jp/submission/2731

Verified with

• 数学/モンモール数 (test/math/montmort_number.test.cpp)

Code

#ifndef EMTHRM_MATH_MONTMORT_NUMBER_HPP_
#define EMTHRM_MATH_MONTMORT_NUMBER_HPP_

#include <vector>

namespace emthrm {

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

}  // namespace emthrm

#endif  // EMTHRM_MATH_MONTMORT_NUMBER_HPP_

#line 1 "include/emthrm/math/montmort_number.hpp"



#include <vector>

namespace emthrm {

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

}  // namespace emthrm

Back to top page