完全順列（撹拌順列）
1 から N の自然数の列の並び替えであって、i 番目の数が i でないようなものを完全順列という.
例えば N=3 に対しては
という二通りがある.
このように N に対してありえる完全順列の個数を !_N と書くことにする. （ビックリマークに対する添字のように書いてるのはわざとです. 一般的な記法であるとは言っていません.） ナントカ数っていう名前も付いてるらしい.
上記では !_3 = 2 であることを確認した.
さて一般の N に対して !_N を計算する方法はいくつかあるが, 次のように考えることで漸化式を立てて O(N) で計算することが出来る.
完全順列であって i 番目 (i=1,2,\ldots,N) の数が P_i であるとする.
最後の N 番目に置ける数は 1 から N-1 の N-1 通り.
今仮にこれが i だとする (P_N = i).
次に i 番目の数 P_i について考える.
これは N であるか N 以外（もちろんi 以外でもある）であるかの二通り.
-
P_i = N のとき,
-
P は単に i と N を交換した数列になっている
- それ以外に注目した場合は N-2 の完全順列（数字は適切にズラしたもの）
-
P_i \ne N かつ P_i \ne i のとき,
- 他のところで P_j = N となっている
- 数列 P で P_N=i と P_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_i は 1 \leq P_i \leq M
- P_i \ne i
-
i \ne j に対して P_i \ne P_j
というようなものを一般化完全順列とここでは呼ぶ.
さらに (N, M) に対する今述べた一般化完全順列の個数のことを仮に
と書くことにする.
この値はやはり完全順列の個数
!_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) である.
基底として
を用いるとよい.
Discussion