| For All Solvers
OMC012

OMC012(F)

　正整数 nn に対し nn 次の置換 σ\sigma であって σ(i)≠i (i=1,…,n)\sigma(i)\neq i~(i=1,\dots,n) をみたすものを nn 次の良い置換 と呼ぶことにする．nn 次の良い置換の個数（モンモール数）を ana_n とすれば，簡単な議論によって N=2048!×(a2047+a2048)N=2048!\times(a_{2047}+a_{2048}) が得られる．

　ここで ana_n の一般項は次の形に表されることが知られている． an=∑k=0n(−1)kn!k!a_n=\sum_{k=0}^{n}\frac{(-1)^kn!}{k!}

漸化式による証明 　nn 次の良い置換 σ\sigma を考える．

  • σ(σ(n))=n\sigma(\sigma(n))=n であるとき：σ\sigma は {1,…,σ(n)−1,σ(n)+1,…,n−1}\{1,\dots,\sigma(n)-1,\sigma(n)+1,\dots,n-1\} の置換と自然に見なすことができ，それは n−2n-2 次の良い置換に自然に対応する．
  • σ(σ(n))≠n\sigma(\sigma(n))\neq n であるとき：次で定義される n−1n-1 次の置換 τ\tau は良い置換である． τ(i)={σ(i)(i≠σ−1(n))σ(n)(i=σ−1(n))\tau(i)=\begin{cases} \sigma(i)&(i\neq \sigma^{-1}(n))\\ \sigma(n)&(i=\sigma^{-1}(n)) \end{cases}

　逆に n−2,n−1n-2,n-1 次の良い置換に対し，対応する nn 次の良い置換は n−1n-1 個存在する．よって ana_n は次の漸化式をみたす： a1=0,a2=1,an+2=(n+1)(an+1+an)(n≥1)a_1=0,\quad a_2=1,\quad a_{n+2}=(n+1)(a_{n+1}+a_n)\quad(n\geq 1) このとき任意の n≥1n\geq 1 について an+1−(n+1)an=−(an−nan−1)=⋯=(−1)n−1(a2−2a1)=(−1)n+1a_{n+1}-(n+1)a_n=-(a_n-na_{n-1})=\cdots=(-1)^{n-1}(a_2-2a_1)=(-1)^{n+1} が成り立ち，この両辺を (n+1)!(n+1)! で割った式を考えれば求める式は容易に得られる．

包除原理による証明 　S:={1,…,n}S:=\{1,\dots,n\} の部分集合 TT に対して，nn 次の置換 σ\sigma であって任意の i∈Ti\in T に対し σ(i)=i\sigma(i)=i をみたすものは (n−∣T∣)!(n-|T|)! 個存在する．また ∣T∣=k (0≤k≤n)|T|=k~(0\leq k\leq n) なる T⊂ST\subset S は nCk{}_{n}\mathrm{C}_{k} 個存在するため，包除原理より an=∑T⊂S(−1)∣T∣(n−∣T∣)!=∑k=0n(−1)knCk(n−k)!=∑k=0n(−1)kn!k!. a_n =\sum_{T\subset S}(-1)^{|T|}(n-|T|)! =\sum_{k=0}^{n}(-1)^{k}{}_{n}\mathrm{C}_{k}(n-k)! =\sum_{k=0}^{n}\frac{(-1)^kn!}{k!}.

これより次が得られる． N=2048!×(2049×∑k=02047(−1)k×2047!k!+1)=2048!×(2049×2046×(2047×∑k=02045(−1)k×2045!k!+1)⏟6の倍数+1)\begin{aligned} N &=2048!\times\left(2049\times\sum_{k=0}^{2047}\frac{(-1)^k\times 2047!}{k!}+1\right)\\ &=2048!\times\left(\underbrace{2049\times2046\times\left(2047\times\sum_{k=0}^{2045}\frac{(-1)^k\times 2045!}{k!}+1\right)}_{6の倍数}+1\right) \end{aligned} よって a,ba,b は 2048!2048! が 2,32,3 で割り切れる回数とそれぞれ一致することがわかる．それはLegendreの公式より a=2047,b=1019a=2047,b=1019 と計算でき，特に解答すべき値は 2085893{\bf 2085893}．

解説YouTube

解説YouTubeが存在しません.