🐷

ABC172/E - NEQ

2 min read

完全順列(撹拌順列)

1 から N の自然数の列の並び替えであって、i 番目の数が i でないようなものを完全順列という.
例えば N=3 に対しては

  • 2, 3, 1
  • 3, 1, 2

という二通りがある.

このように N に対してありえる完全順列の個数を !_N と書くことにする. (ビックリマークに対する添字のように書いてるのはわざとです. 一般的な記法であるとは言っていません.) ナントカ数っていう名前も付いてるらしい.
上記では !_3 = 2 であることを確認した.

さて一般の N に対して !_N を計算する方法はいくつかあるが, 次のように考えることで漸化式を立てて O(N) で計算することが出来る.

完全順列であって i 番目 (i=1,2,\ldots,N) の数が P_i であるとする.

最後の N 番目に置ける数は 1 から N-1N-1 通り.
今仮にこれが i だとする (P_N = i).
次に i 番目の数 P_i について考える.
これは N であるか N 以外(もちろんi 以外でもある)であるかの二通り.

  1. P_i = N のとき,
    • P は単に iN を交換した数列になっている
    • それ以外に注目した場合は N-2 の完全順列(数字は適切にズラしたもの)
  2. P_i \ne N かつ P_i \ne i のとき,
    • 他のところで P_j = N となっている
    • 数列 PP_N=iP_j=N を交換する
    • すると 1 番目から N-1 番目に注目すれば N-1 の完全順列になっている

というわけで

!_N = (N-1) (!_{N-1} + !_{N-2})

使える数を増やした完全順列

完全順列は 1 から N の並び替えだったが, M \geq N なる M について, 1 から M の自然数から異なる N 個選んで並べるという一般化が考えられる.
つまり,

  • 長さ N の数列 P
    • i 番目 (i = 1, 2, \ldots, N) の数 P_i1 \leq P_i \leq M
    • P_i \ne i
    • i \ne j に対して P_i \ne P_j

というようなものを一般化完全順列とここでは呼ぶ.

さらに (N, M) に対する今述べた一般化完全順列の個数のことを仮に

!^M_N

と書くことにする.
この値はやはり完全順列の個数 !_N と同じノリで計算出来る.

やはり P_N についてまず考えるのだが, P_N > N という例外が一個増える. この場合は N-1 番目以下には大した影響がなくて, ただ使える数の種類が一個減るだけ. それ以外は同じ.
というわけで,

\begin{aligned} !^M_N & = (M-N) !^{M-1}_{N-1} + (N-1) \left( !^{M-1}_{N-1} + !^{M-2}_{N-2} \right) \\ & = (M-1) ~ !^{M-1}_{N-1} + (N-1) ~ !^{M-2}_{N-2} \\ \end{aligned}

ABC172/E - NEQ

問題

解答

A を固定した場合の B というのは !^M_N になる.
A の作り方は単に M 個から N 個の選び方なので, {}_MP_N = \binom{M}{N} N! 通り.

答えは

\binom{M}{N} \times N! \times !^M_N

さて !^M_N の計算方法は上記の漸化式に従うだけだが, 注意点として,
!^m_n ~(m \leq M, n \leq N) 全部を計算しないといけないとすると, O(MN) 掛かってこの問題では間に合わない.
しかしよく見ると !^{M-k}_{N-k} という形のものしか要求していないので, 結局 O(N) である.
基底として

  • !^m_0 = 1
  • !^m_1 = m-1

を用いるとよい.

Discussion

ログインするとコメントできます