離散数学・組合せ論の問題

条件の言いかえ

レジの中の 500 円硬貨の枚数は、A の客が来ると 1 枚増え、B の客が来ると 1 枚減る。はじめは 0 枚なので、B の客におつりを渡せるのは、その客の直前までに来た A の人数が B の人数より多いときである。よって、条件は

「列の先頭から何文字目まで見ても、A の個数 $\ge$ B の個数」

と言いかえられる。これは長さ $10$ の正しい括弧列（A を「(」、B を「)」とみる）と同じ条件であり、その個数はカタラン数 $C_5$ である。鏡像原理で求める。

全体の個数

A を 5 個、B を 5 個並べる列は、10 か所から A の位置を 5 か所選べばよいので
$$\left(\genfrac{}{}{0ex}{}{10}{5}\right)=252\text{ 通り}.$$

条件を満たさない列の個数（鏡像原理）

条件を満たさない列では、先頭から見ていって初めて「B の個数 $=$ A の個数 $+1$」となる位置がある。その位置より後ろの部分で A と B をすべて入れかえる。

その位置までに A が $k$ 個、B が $k+1$ 個あるとすると、後ろの部分には A が $5-k$ 個、B が $4-k$ 個ある。入れかえると後ろは A が $4-k$ 個、B が $5-k$ 個になるので、列全体では A が $4$ 個、B が $6$ 個になる。

逆に、A が 4 個、B が 6 個の列では、必ずどこかで初めて「B の個数 $=$ A の個数 $+1$」となる位置があり、その後ろを入れかえるともとの列に戻る。したがって、この対応は 1 対 1 であり、条件を満たさない列の個数は
$$\left(\genfrac{}{}{0ex}{}{10}{4}\right)=210\text{ 通り}.$$

答え
$$\left(\genfrac{}{}{0ex}{}{10}{5}\right)-\left(\genfrac{}{}{0ex}{}{10}{4}\right)=252-210=42.$$

これは $C_5=\frac{1}{6}\left(\genfrac{}{}{0ex}{}{10}{5}\right)=\frac{252}{6}=42$ と一致する。よって 42 通り である。

A を +1、B を −1 とみなすと、おつりを必ず渡せる条件は、どの接頭部分でも A の個数が B の個数以上であること、つまり部分和が常に 0 以上であることと同値。これは長さ 10 のディック路（バロット列）で、その総数はカタラン数 $C_5=\frac{1}{6}\left(\genfrac{}{}{0ex}{}{10}{5}\right)=\frac{252}{6}=42$ である。

検算（反射原理）：全列 $\left(\genfrac{}{}{0ex}{}{10}{5}\right)=252$ 通り。途中で部分和が −1 に達する悪い列は、最初に −1 に達した時点以降を反転すると、A が 4 個、B が 6 個の列と 1 対 1 に対応する。その個数は $\left(\genfrac{}{}{0ex}{}{10}{4}\right)=210$。よって $252-210=42$。

なお、B の客が来る直前のレジの硬貨は A の累計個数 − それまでの B の個数であり、B の客に渡すには 1 枚以上必要なので、B を含めた接頭部分で A の個数 ≥ B の個数が必要となる。これは上の条件と一致する。