個の元の順列を考えるとき、どの元(げん)をとっても元(もと)の位置にいないような順列のことを完全順列といいます。
個の元の完全順列の総数を
と表し、Montmort数と名付けられています。便宜的に
と定義します。
例えば、の順列は
の六通りですが、完全順列は
の二通りです。
Montmort数は漸化式
を満たす。
証明. の完全順列を考える。完全順列において
番目にくる数は
から
の
通りある。
番目の数が
であったとしよう。もし、
番目の数が
であれば、残りの部分の順列の総数は
である。また、
番目が
でなければ、そのような順列の総数は
通りあることがわかる(
と
を同一視していると考えればよい)。 Q.E.D.
この漸化式からは明示的な表示
をもつことを(帰納法などで)示せます。また、この式から別の漸化式
を満たすことも分かります。Eulerはこれらの漸化式を証明していたそうです(流石!)。
演習問題
とする。このとき、
は
の倍数であることを示せ。
つまり、の絶対値が素数になるのは残念ながら
のみです。
順列を固定する元を指定しながら数えていくことによって、
が成り立つことも分かります。
の数値(
)
私はなんとなくを気に入ってます。