\(A\) が順列である場合、\(A\) の値の種類数が \(1\) 種類である場合は明らかなので、以下ではそれ以外の場合を考えます。

\(A_1 \neq A_N\) を仮定して一般性を失いません。(☆)

まず、初期状態の \(A\) は順列でないので、\(A\) に操作を \(1\) 回は行える必要があります。

また、 \(A\) をランレングス圧縮した列 \(A'\) を考えると、操作により \(A'\) の要素を削除することはできません。そのため、同じ値が \(A'\) に複数存在している、つまり値が分離している場合は順列を作ることはできません。 （注釈:この問題は円環を考えているので端の処理が面倒です。そのため、初めに適当な回転を行い(☆)の仮定をすることで議論を簡単にしています。）

以下では操作が一回以上可能で、値が分離していない入力を考えます。

\(A\) の種類数が \(N-2\) 種類の場合、つまり \(A=(1,1,1,2,3,4)\) のような場合を考えます。この場合、最後の操作で三つ組の二つを存在しない値（例の場合 \(5,6\)）に置き換えることとなります。それ以前の操作では三つ組を保たないといけないため、可能な操作は \((1,2,2,2,3,4)\) または \((4,4,1,2,3,4)\) に変更するのみです。この操作を再び \(1\) が三つ組になるまで行うと、数列の各要素の位置は \(2\) ずれます。つまり \(2\)-shift が実現できます。そして最後に残り二つの値を（円環上での）距離が \(2\) 以下の場所に挿入することとなります。

ここまでの議論を整理すると、生成できる順列 \(P\) は以下の条件を満たすもの全てです。

• \(A\) に存在する値の順序は \(P\) 内部でも保たれている
• 存在しない二つの値の \(P\) での距離は \(2\) 以下
• 各要素の位置は \(2\) ずつしかずらせないため、\(N\) が偶数の場合、上の条件を満たすもののうち半分のみ（この議論は \(N=4\) の場合のみ壊れていて、\(N=4\) がコーナーケースとなっています）

\(A\) の種類数が \(N-3\) 種類以下の場合は、適当に操作を繰り返すことで、存在しない値を任意に挿入可能で、かつある値の三つ組の位置を自由に調整できます。ただし、最後に追加する残り二つの値の距離は \(2\) 以下である必要があります。この場合は、生成できる順列 \(P\) は以下の条件を満たすもの全てです。

• \(A\) に存在する値の順序は \(P\) 内部でも保たれている
• \(A\) に存在しない二つの値の組であって、\(P\) での距離が \(2\) 以下であるものが存在する

ここまでの議論をもとに数え上げを行いましょう。この数え上げで最も難しいポイントは、

• \(A\) に存在しない二つの値の組であって、\(P\) での距離が \(2\) 以下であるものが存在する

という点です。まず、余事象を用いて条件を

• \(A\) に存在しない二つの値はどの二つも距離が \(3\) 以上である

と言い換えます。

\(P\) での距離が円環上の距離であるのが面倒なので、\(P\) の端に存在しない値を置くかを両方試して、列での距離を考えることとします。さらに、\(A\) に存在しない値の順序は最後に決めることとして、区別しない値を挿入することにすれば、挿入位置が隣接しないような挿入位置の集合の数え上げとなり、二項係数により求められます。計算量は \(\mathrm{O}(N)\) です。