4 設定、記号等

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

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

$$0\leq a_1\leq a_2\leq\cdots\leq a_n$$ (7)

であると仮定する。この $\{a_k\}_k$ の並べかえ $a'_1,a'_2,\ldots,a'_n$ に 対して $S_2$ や $S_3$ を考えることになる。 その並べかえた列や、その部分列を、順番と端を記号的に示して、

$$A=[a'_1 a'_2 \cdots a'_n], \hspace{1zw} B=[a'_k a'_{k+1} \cdots a'_m]$$

のような記号で表すことにし、さらに、

$$A=[a'_1 \cdots a'_{k-1} B a'_{m+1} \cdots a'_n]$$

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

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

$$\bar{B} = [b_m b_{m-1} \cdots b_1]$$

$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)$ を、

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

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

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

$$S_3(\bar{B}) = S_3(B), \hspace{1zw} S_2(\bar{B}) = S_2(B)$$ (9)

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