T.11 · Weak compositions, loop invariants and flowchart tracing

大学卒GRE準備。検証済みETS範囲内の地域的な目標；これは独自の教育であり、公式テストや得点予測器ではありません。

前提知識：二項係数、補集合および割り当てトレース。

• 非負または正の制約を持つ区別不可能な配分の数を数える
• 正しいリセット挙動を持ってステートメント順にフローチャートをトレースする
• ループ不変量と進行測度を用いてアルゴリズムを正当化する

弱合成: 全体を非負整数部分に並べ替えた順序付き配分。

ループ不変量: ループの各反復前後で保たれる性質。

x₁+⋯+x_k=n の非負整数解の個数は C(n+k−1,k−1) である（n≥0, k≥1）。n個の同一の星をk個の名前付き箱に分けるには、k−1本の棒を用いる。隣接する棒や端の棒はゼロ成分を許容する。箱は区別可能だが、物体は区別不可である。異なるトークンを数える場合、各トークンに独立して割り当てて k^n を求めるが、他の制約がある場合はそうではない。モデルは familiar な二項係数の形ではなく、物体と受け手が何を表すかに基づいて決定すべきである。

正の配分 x_i≥1 に対して z_i=x_i−1 とおくと、残りの総和は n−k となり、n≥k のとき C(n−1,k−1) が得られる。より一般的な下限 x_i≥a_i は、各 a_i を引くことで処理できる。少なくとも一つがゼロであることは、すべての成分が正であることの補集合であるため、非負の総和から C(n−1,k−1) を引く。空の箱がちょうど2つであるような重なったケースは別の数え方が必要であり、空の箱のケースをそれぞれ独立に引くと、その共通部分が二重にカウントされる。

フローチャートをステートメントごとにトレースし、変数を表に記録する。代入と数学的な等号テストを区別せよ。代入の右辺では置換前の古い値を用いる。次に実行される枝と、どの変数がリセットされるかを記録せよ。新しい外側ループの候補が内側の和をリセットしても、候補自体はリセットされないことがある。プロセスが零から 1,3,5,… を S に加えていく場合、m回の加算後 S=m² となり、次の加算項は 2m+1 である。

ループ不変量は各反復前後で真である。平方和不変量は m=0 で初期に成立し、m²+(2m+1)=(m+1)² であることから保たれる。不変量だけでは終端性を証明できない。整数 N≥0 が平方数かどうかを奇数の累加によって S≥N まで確認する場合、S は無限に増加する。これは m が増加し N などの境界に達することを意味する。終了時に等号が成り立つことが平方数であり、超過することが非平方数である。印刷された値は実際の実行パス上で到達されなければならない。 plausible な数値パターンだけではトレースにならない。

11 個の同一のトークンを 4 個の名前付き箱に分配する。非負の配分数は C(14,3)=364、全正の配分数は C(10,3)=120 である。したがって、少なくとも1つの空箱を含む配分数は 244 である。N=10 の奇数和テストにおいて、S は 0,1,4,9,16 へ進み、超えて 10 を却下する。N=9 の場合、3回の加算後に S=9 で終了する。次の加算対象は 1,3,5,7,9 であり、和と次の加算対象の列は混同してはならない。

同一物体と固有物体は異なるモデルを用いる。少なくとも一つの空箱は「ちょうど一つ」の物とは同じではない。フローチャートでは更新順序を保持し、実行されたパスが実際にリセットする変数のみをリセットする。

$a+b+c=8$ の非負解を $a\ge2$ で数えよ。$b,c\ge1$ を満たすものはいくつあるか？最初のセットのうち b,c がゼロ以上1つ含まれるものはいくつあるか？

解例

$u=a-2$ を置く。次に $u+b+c=6$ は $\binom82=28$ 個の非負解を持つ。b,c が正で、それぞれ1を引いた結果の総和が三つの非負変数で4になることを要求すると、$\binom62=15$ で数えられる。補集合の個数は $28-15=13$ である。直接 b=0 の場合が七つ、c=0 の場合が七つあり、両方ゼロの場合は二重にカウントされるため、$7+7-1=13$ となる。

N=15 および N=16 に対してこのアルゴリズムをトレースせよ: S=0, k=1 を初期化し、S<N ならば S=S+k、k=k+2 を実行し、S=N かどうかを報告する。不変量を述べて、整数 $N\ge0$ に対して終端性を正当化せよ。

解答後の確認

m 回の反復後、$S=m^2$ と $k=2m+1$。トレース対 (S,k) は $(0,1),(1,3),(4,5),(9,7),(16,9)$ である。したがって、15 はオーバーシュートにより除外され、16 が採用される。不変式は初期に成立し、$m^2+(2m+1)=(m+1)^2$ 以来維持されている。和は有界でないため、最終的に N に到達するか超える；例えば、N が正のとき m=N で十分である。N=0 の場合、ループはスキップされ等号が成立する。不変式だけでは終端性を保証できない。