4 設定、記号等

ここから一般の $a_1,a_2,\ldots,a_n$ に対する考察を行うが、 そのためにいくつか仮定や記号等を導入する。

まず、対象とする数列 $a_1,a_2,\ldots,a_n$ は、

\begin{displaymath}
0\leq a_1\leq a_2\leq\cdots\leq a_n\end{displaymath} (7)

であると仮定する。この $\{a_k\}_k$ の並べかえ $a'_1,a'_2,\ldots,a'_n$ に 対して $S_2$$S_3$ を考えることになる。 その並べかえた列や、その部分列を、順番と端を記号的に示して、
\begin{displaymath}
A=[a'_1 a'_2 \cdots a'_n],
\hspace{1zw}
B=[a'_k a'_{k+1} \cdots a'_m]
\end{displaymath}

のような記号で表すことにし、さらに、
\begin{displaymath}
A=[a'_1 \cdots a'_{k-1} B a'_{m+1} \cdots a'_n]
\end{displaymath}

のように部分列をその中に入れて書くことも行う。

一つの列の並び $B=[b_1 b_2 \cdots b_m]$ を逆順にしたものを $\bar{B}$ と書く:

\begin{displaymath}
\bar{B} = [b_m b_{m-1} \cdots b_1]
\end{displaymath}

$n(B)$ を列 $B$ の要素の個数とする: $n([b_1 b_2 \cdots b_m]) = m$

$B=[b_1 b_2 \cdots b_m]$ ($m\geq 2$) に対して、 隣接積和 $S_3(B)$ と 巡回的隣接積和 $S_2(B)$ を、

\begin{displaymath}
S_3(B) = \sum_{k=2}^m b_{k-1}b_k,
\hspace{1zw}
S_2(B) = S_3(B) + b_mb_1\end{displaymath} (8)

と定義する。なお、$m=0,1$ の場合は、いずれも 0 であるとする。

$S_3$, $S_2$ は反転に関して明らかに不変であることに注意する:

\begin{displaymath}
S_3(\bar{B}) = S_3(B),
\hspace{1zw}
S_2(\bar{B}) = S_2(B)\end{displaymath} (9)

目標は、(7) を満たす $\{a_k\}_k$ の 並びかえ $A'=[a'_1 \cdots a'_n]$ の中で、 $S_3(A')$, $S_2(A')$ を最大、最小にするものを求めること、となる。

竹野茂治@新潟工科大学
2017年2月9日