3 隣接積の和の最大最小

では、今度は $n$ 個のデータ $p_k/M_k(\geq 0)$ が 与えられたときに、(3) の $S_1$ の値は、 軸の並べかえでどのように変化するか、 どのような並びのときに (3) の値は、 最大、最小となるのか、といったことを考えてみる。

これは、 $a_k\geq 0$ ( $k=1,2,\ldots n$) に対し、$a_0=a_n$ とするとき、

$$S_2 = \sum_{k=1}^n a_{k-1}a_k$$

の値が、 $a_1,\ldots a_n$ の順を並べかえたときに、 どのような並びのときに最大、あるいは最小となるか、という問題になる。 そのため、この $S_2$ と、両端の積を排除した

$$S_3 = \sum_{k=2}^n a_{k-1}a_k = S_2 - a_1a_n$$

を考えてみることにする。

ここでは、数列のすべての並びかえを考えるので、元の $a_k$ は

$$0\leq a_1\leq a_2\leq \ldots \leq a_n$$

であるとしてよい。

簡単のため、例えば $n=3$ の場合を考えてみる。 まず $S_3$ を考える。通常の $a_1,a_2,a_3$ の並びに対しては、

$$S_3 = S_3^1 = a_1a_2 + a_2a_3$$ (4)

となるが、これを並べかえて $a_1,a_3,a_2$ とすると、$S_3$ の値は

$$S_3 = S_3^2 = a_1a_3 + a_3a_2$$ (5)

となり、さらに $a_2,a_1,a_3$ という並びに対しては、$S_3$ は

$$S_3 = S_3^3 = a_2a_1 + a_1a_3$$ (6)

となる。$a_1,a_2,a_3$ の順列の並べかえは 全部で $3!=6$ 通りあるが、 並び全体を反転させても $S_3$ の値は変わらないので、 並べかえによる値はこの $S_3^1$, $S_3^2$, $S_3^3$ の 3 通りとなる。 例えば、$a_3,a_1,a_2$ に対する $S_3$ は確かに

$$S_3 = a_3a_1 + a_1a_2 = S_3^3$$

に等しくなる。 この $S_3^1$, $S_3^2$, $S_3^3$ では、

$$S_3^1-S_3^2 = a_1(a_2-a_3)\leq 0$$

より $S_3^1\leq S_3^2$ で、また

$$S_3^1-S_3^3 = (a_2-a_1)a_3\geq 0$$

より $S_3^1\geq S_3^3$ なので、 よって $S_3^3\leq S_3^1\leq S_3^2$ であり、 $a_1,a_3,a_2$ (および $a_2,a_3,a_1$) の並びの場合に $S_3$ は最大、 $a_2,a_1,a_3$ (および $a_3,a_1,a_2$) の並びの場合に最小となる ことがわかる。

一方 $S_2$ は、$a_1,a_2,a_3$ に対しては

$$S_2 = S_2^1 = a_1a_2+a_2a_3+a_3a_1$$

となるが、これも反転しても値は変わらないが巡回的、すなわち円順列なので、 $n=3$ の場合は $(3-1)!/2 = 1$ 通り、 すなわちこの $S_2^1$ の 1 種類しかない。

$n=4$ の場合は、$(4-1)!/2 = 3$ 通りあり、

$$\begin{eqnarray*}S_2^1 &=& a_1a_2+a_2a_3+a_3a_4+a_4a_1 \hspace{1zw}(a_1,a_2,a_3... ...^3 &=& a_1a_3+a_3a_2+a_2a_4+a_4a_1 \hspace{1zw}(a_1,a_3,a_2,a_4)\end{eqnarray*}$$

となる。他のものはすべてこのいずれかと同じものになる。 例えば、 $a_4,a_2,a_1,a_3$ の場合は、

$$S_2 = a_4a_2+a_2a_1+a_1a_3+a_3a_4 = a_1a_2+a_2a_4+a_4a_3+a_3a_1 = S_2^2$$

となる。 これらの大小は、

$$\begin{eqnarray*}S_2^1-S_2^2 &=& a_2a_3+a_4a_1-a_2a_4-a_3a_1 = (a_2-a_1)(a_3-a... ..._2^3 &=& a_1a_2+a_3a_4-a_1a_3-a_2a_4 = (a_1-a_4)(a_2-a_3)\geq 0\end{eqnarray*}$$

より $S_2^3\leq S_2^1\leq S_2^2$ となり、 よって $a_1,a_3,a_2,a_4$ の並びのときに最小、 $a_1,a_2,a_4,a_3$ の並びのときに最大となることがわかる。

なお、上の例では、すべての並べかえに対して $S_2$, $S_3$ の大小が $\{a_k\}$ の順序から一意に確定している、 すなわち線形順序 (全順序) がついているが、 これは常にそうなるわけではない。 例えば、$n=4$ の $S_3$ では、 $a_1,a_2,a_3,a_4$ の並びに対する

$$S_3=S_3^1=a_1a_2+a_2a_3+a_3a_4$$

と、 $a_1,a_4,a_2,a_3$ の並びに対する

$$S_3=S_3^2=a_1a_4+a_4a_2+a_2a_3$$

を比較すると、

$$S_3^1 - S_3^2 = a_1a_2+a_3a_4 - (a_1a_4+a_4a_2) = a_4(a_3-a_2)-a_1(a_4-a_2)$$

となるが、これは正の項同士の差で、 その正負は $a_1\leq a_2\leq a_3\leq a_4$ の大小だけでは決定せず、 値によって変わりうる。 例えば $a_2=4$, $a_3=5$, $a_4=8$, $a_1<4$ とすると、

$$S_3^1 - S_3^2 = 8-4a_1 = 4(2-a_1)$$

となるので、$S_3^1$ と $S_3^2$ の大小は、 $a_1$ が 2 より大きいか小さいかで変わることになり、 $a_1\leq a_2\leq a_3\leq a_4$ という条件だけでは必ずしも確定しない。 このように、すべての並びに必ずしも大小は確定はしないが、 しかし最大値、最小値を与える並びはこの後見るように常に確定する。