一般性を失わずに，\(P_1 < P_N\) の時を考えます．

まず，\(P\) が一つ与えられたときに条件を満たすかどうかを考えます．このとき，以下が必要十分であるとわかります．

• ある \(1 \leq i \leq N-1\) が存在し，\(P_i \leq P_1\),\(P_{i+1} \geq P_N\)

証明は帰納法でできます．

上記の条件を満たす \(i\) が存在しないような順列 \(P\) の個数を数えます．

\(P_N=A+k\) とおきます．このとき，\(k \geq 2\) であることがまず必要です． 次の手順で \(P\) を構成することを考えます．

• まず，列 \(P=(A,A+k)\) がある．
• \(A+1\) から \(A+k-1\) までの値を \(P\) に挿入する．これは \((k-1)!\) 通りの方法が存在する．
• \(1\) から \(A-1\) までの値を \(P\) に挿入する．このうち \(i\) 番目(\(1 \leq i \leq A-1\))の値を挿入する際，位置の候補は \(k-2+i\) 個ある．
• \(A+k+1\) から \(N\) までの値を \(P\) に挿入する．このうち \(i\) 番目(\(1 \leq i \leq N-(A+k)\))の値を挿入する際，位置の候補は \(k-2+i\) 個ある．

これらをまとめると，\((A+k-3)!(N-A-2)!(k-1)/(k-2)!\) になります． よって，求めるべき式は，\(\sum_{2 \leq k \leq N-A}(A+k-3)!(N-A-2)!(k-1)/(k-2)!\) です． これは \((N-A-2)!(A-1)! \sum_{0 \leq k \leq N-A-2} {A+k-1 \choose k}(k+1)\) と変形できます．また，\({A+k-1 \choose k} k=A {A+k-1 \choose k-1}\) を用いて，\(\sum\) を定数個のコンビネーションの式に帰着できます． よって\(O(1)\) でこの問題は解けます．