数学において並べ替え不等式(ならべかえふとうしき、, Section 10.2, Theorem 368)とは、2つの数列の項を掛け合わせて和を作る際、どのように並べ替えて組み合わせればその和が最大(あるいは最小)になるかを述べた不等式である。

定義 任意の実数列

と、 の任意の置換 に対して、以下の不等式が成り立つ。

直感的に言えば、この不等式は「大きいもの同士、小さいもの同士を組み合わせたときに和が最大になり、逆に大きいものと小さいものを組み合わせたときに和が最小になる」ことを意味している。

等号成立の条件については以下の通りである。 上界(右側の不等式): かつ である場合、最大値をとるのは が恒等置換(すなわち順序を変えない)のとき、かつそのときに限る。 下界(左側の不等式):同条件において、最小値をとるのは が逆順の置換(すなわち )のとき、かつそのときに限る。

この不等式は、相加相乗不等式などとは異なり、各項が負の実数であっても成り立つ点に特徴がある。

直感的説明 この不等式は、次のような日常的な例え話で理解することができる。 1,000円札、5,000円札、10,000円札の束がそれぞれ1つずつあるとする。あなたは各束から札を取ることができるが、回数ごとに取れる枚数は「3枚」「5枚」「7枚」と決められており、一度選んだ束や枚数の設定は再度選ぶことができない。

このとき、合計金額を最大にするには、最も価値の高い10,000円札を最も多い「7枚」に割り当て、次に5,000円札を「5枚」、最後に1,000円札を「3枚」取るのが最善である( 円)。逆に、10,000円札を最も少ない3枚に割り当ててしまうと、合計金額は最小になる。

これはまさに、2つの数列(枚数の数列と紙幣価値の数列)を大きい順に並べて掛け合わせたときに和が最大になり、逆順に組み合わせたときに最小になるという、並べ替え不等式の主張そのものである。この性質から、本不等式は貪欲法が最適解を与える一例と見なすこともできる。

幾何学的解釈 並べ替え不等式は、分割された長方形の面積を用いた幾何学的なモデルで解釈できる。

および と仮定する。幅が 、高さが である大きな長方形を考え、各列の幅を 、各行の高さを となるように 個の小さな長方形の区画に分割する。

このとき、並べ替え不等式の問題は、「各列から1つ、かつ各行から1つずつ、合計 個の区画を選択したとき、その合計面積を最大化(または最小化)せよ」という問題に置き換えられる。 最大値:左下から右上に向かう対角線上の区画(小さい幅には小さい高さを、大きい幅には大きい高さを組み合わせる)を選択したとき、合計面積は最大となる。 最小値:左上から右下に向かう対角線上の区画(小さい幅に大きい高さを組み合わせる)を選択したとき、合計面積は最小となる。

これは、面積の大きな区画(大きな と大きな の積)を優先的に選ぶことが、全体の和を押し上げるのに最も効率的であることを視覚的に示している。

応用例 並べ替え不等式を用いることで、数学における多くの重要な不等式を証明できる。例えば、相加相乗不等式、コーシー=シュワルツの不等式、チェビシェフの和の不等式などが挙げられる。

簡単な例として、実数 に対して、 とおいて適用すると、任意の置換 に対して以下が得られる。

証明

背理法による証明 ここでは右側の不等式(最大値)について証明する。 置換 は有限個であるため、和を最大にする置換が少なくとも1つ存在する。そのような置換のうち、恒等置換と一致するインデックス (すなわち )の数が最も多いものを とする。

もし が恒等置換でないならば、ある が存在して となる。このとき であって となるものが存在するはずである。また、 である。 このとき、 かつ であることから、以下の関係が導かれる。

これを展開して整理すると:

ここで、置換 の 番目と 番目の値を入れ替えた新しい置換 を作ると、その和は元の による和以上になる。しかし、これは の選び方(恒等置換と一致する箇所が最大であること)に矛盾する。したがって、和を最大にする置換は恒等置換でなければならない。

数学的帰納法による証明 の場合、 かつ より、

これを展開すれば となり、成立する。 次に、 で成り立つと仮定して の場合を考える。和を最大にする置換において であれば、帰納法の仮定より直ちに証明される。 の場合は、上述の入れ替え操作(隣接互換に類する操作)を行うことで和を減らさずに の状態へ帰着させることができる。

一般化

3つ以上の数列 非負の実数列が3つ以上ある場合にも一般化が可能である。 、、 とし、それぞれの置換を考えると、

が成り立つ。ただし、この場合は各項が非負であるという条件が必要になる。

関数への一般化 連続微分可能な関数 の族に対しても一般化が存在する。 導関数が を満たすとき、

が成り立つ。ここで とおけば標準的な並べ替え不等式が再現される。

関連項目 ハーディ=リトルウッドの不等式 チェビシェフの和の不等式 コーシー=シュワルツの不等式 減少再配列

参考文献