1:2:1 - tokoharuの落書き帳

1:2:1といえば ->

(x+1)^2の係数
パスカルの三角形3段目
競プロでは ... Air Pollution | Aizu Online Judge

という感じですが次の性質が成り立つんですね

$A_0 = 0,\\ 2 A_i \geq A_{i-1} + A_{i+1} (i \geq 1)$
ならば $i\geq 1$ に対して $\frac{A_i}{i}$ は非増加列である．
言い換えると $i\geq 1$ に対して $\frac{A_i}{i} \geq \frac{A_{i+1}}{i+1}$ が成立する．

証)
数学的帰納法による．
要素数が2以下の場合，つまり $\frac{A_1}{1}, \frac{A_2}{2}$ のみの時は $2A_1 \geq A_0 + A_2$ より非増加列．
$\frac{A_1}{1} ,\dots, \frac{A_n}{n}$ の数列が非増加だったとする．
このとき $2A_n \geq A_{n-1} + A_{n+1} \geq \frac{n-1}{n} A_{n} + A_{n+1}$ より
$\frac{A_n}{n} \geq \frac{A_{n+1}}{n+1}$ を得るため証明終わり．

この性質が何だという話ですが、これは劣モジュラ性について扱っている本を眺めていて副次的に出てきたものです。

劣モジュラ性とは，（素人なので嘘書いてる可能性がありますが）
要素数 $n$ の有限集合 $S$ の冪集合 $2^S$ 上の分配束（集合の和積で閉じている）であるような部分集合 $\mathcal{D}$ をとる．
この $\mathcal{D}$ から実数への写像 $f$ が劣モジュラであるとは $\forall A, B \in \mathcal{D}$ に対して $f(A)+f(B) \geq f(A \cap B) + f(A \cup B)$ を満たすことである．また通常 $f(\phi) = 0$ としておく．

さらに劣モジュラ多面体というものを考えます。

まず， $x \in \mathbb{R}^S$ とする．この $x$ を拡張して $\forall A \in \mathcal{D}, y(A) = \sum_{a \in A} x(a)$ とする．
この時， $\mathcal{D},$ 劣モジュラ $f$ による劣モジュラ多面体とは $\forall A, \in \mathcal{D}, y(A) \leq f(A)$ となるような $x$ の集合のことである．

定理: 劣モジュラ多面体では $y(S)= f(S)$ を満たす $x$ が必ず存在する（証明略）．

(ここからは $\mathcal{D}=2^S$ とする．)
先ほどの定理は大雑把な書き方をすると $A \neq S, y(A) \leq f(A)$ なる複数の平面で切った後に $y(S) \leq f(S)$ でまだ切れる余地がある（もしくは接する,かする）ことを意味している。（しかしすぐに証明できる気がしないし本当にそんなうまいこといってるのか？と思うわけなので具体的なことを考えていこうという方向です。）

さて、この定理が成り立つということは、例えば $s_1,\dots,s_n \in S$ として $y({s_1}) \leq f({s_1}), y({s_2}) \leq f({s_2}), \dots y({s_n}) \leq f({s_n})$ を満たす多面体 $P$ に対して $\max_{x \in P}\sum y({s_i}) \geq f(S)$ が成り立つはずである。
ということは、 $\sum f({s_i}) \geq f(S)$ が成立するはずである。
さらに言えば、 $y({s_i})$ を $y({s_i, \dots , s_{i+j-1}})$ として巡回的な制約を満たす多面体 $P_j$ に関しても同様なことが成り立ち、
$\sum f({s_i, \dots, s_{i+j-1}}) / j \geq f(S)$ が成り立つはずである。(なお、 $m \geq 0, s_{n+m} = s_{m}$ としておく)

ここで数列 $A$ を $A_j = \sum_{i} f({s_{i}, \dots s_{i+j-1}}) , A_0 = 0, A_n = n f(S)$ とすれば劣モジュラ性の式を足しこむことによって冒頭の1:2:1な式が出てくるという話なのでした（背景説明が長い）。

そんで、ここで冒頭の性質が成り立つので、さっき出てきた式を $\sum f({s_i, \dots s_{i+j-1}}) / j = \frac{A_j}{j} \geq \frac{A_n}{n} = f(S)$ という風に示せるのでなるほど確かに定理は納得できる気もしてくるなぁ、と思ったのでした。