場合の数と確率の問題

1. 全体の並べ方

$19$ 枚のうち $-2$ のカードの位置を選べばよいので、並べ方は全部で
$${}_{19}{\mathrm{C}}_6=\frac{19\cdot 18\cdot 17\cdot 16\cdot 15\cdot 14}{6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}=27132\text{通り}$$
である。$19$ 枚全部の和は $13-12=1$ である。

2. 鍵となる考え：始まりの位置をずらす

並べ方 $w=(c_1,c_2,\dots ,c_{19})$ に対し、$k$ 番目のカードから始めて右へ読み、右端の次は左端に戻って $19$ 枚読んだ並べ方
$$(c_k,c_{k+1},\dots ,c_{19},c_1,\dots ,c_{k-1})$$
を「$w$ を $k$ から読んだもの」と呼ぶ（$k=1,2,\dots ,19$）。また、問題の条件（途中の和がすべて正）を満たす並べ方を「よい並べ方」と呼ぶ。

主張：どの $w$ についても、$k=1,\dots ,19$ のうち「$w$ を $k$ から読んだもの」がよい並べ方になる $k$ はちょうど $1$ つである。

$S_0=0$、$S_i=c_1+\cdots +c_i$ とし、さらに $c_{i+19}=c_i$ として番号を延長すると、$S_{i+19}=S_i+1$ が成り立つ（$19$ 枚分の和が $1$ だから）。「$w$ を $j+1$ から読んだもの」の $t$ 枚目までの和は $S_{j+t}-S_j$ である（$0\leqq j\leqq 18$、$1\leqq t\leqq 19$）。

(存在) $S_0,S_1,\dots ,S_{18}$ の最小値を $M$ とし、$S_j=M$ となる $j$ $(0\leqq j\leqq 18)$ のうち最大のものをとる。
- $j+t\leqq 18$ のとき、$j$ は最小値をとる最後の番号なので $S_{j+t}>M=S_j$。
- $j+t\geqq 19$ のとき、$S_{j+t}=S_{j+t-19}+1\geqq M+1>S_j$。

よって「$w$ を $j+1$ から読んだもの」はよい並べ方である。

(ただ $1$ つ) 「$w$ を $j+1$ から読んだもの」がよい並べ方であるとする。$0\leqq i\leqq 18$、$i\ne j$ について
- $i>j$ なら $S_i-S_j>0$、すなわち $S_i>S_j$。
- $i<j$ なら $S_{i+19}-S_j>0$、すなわち $S_i+1>S_j$ で、整数なので $S_i\geqq S_j$。

よって $S_j$ は $S_0,\dots ,S_{18}$ の最小値で、しかも最小値をとる番号のうち最大のものである。このような $j$ はただ $1$ つに決まる。

3. 数え上げ

組 $(w,k)$（$w$ は並べ方、$k=1,\dots ,19$）のうち、「$w$ を $k$ から読んだもの」がよい並べ方であるものの個数を $2$ 通りに数える。

• 主張より、各 $w$ に対してそのような $k$ はちょうど $1$ つなので、個数は $27132$。
• 一方、よい並べ方 $g$ を $1$ つ固めると、各 $k$ に対して「$w$ を $k$ から読んだものが $g$」となる $w$ は（$g$ を逆にずらして）ただ $1$ つ決まる。よって $1$ つの $g$ につき $19$ 組あり、よい並べ方の数を $N$ とすると個数は $19N$。

したがって $19N=27132$ より $N=1428$。

（確認：小さい例として、$+1$ が $3$ 枚、$-2$ が $1$ 枚のとき、よい並べ方は $(+1,+1,+1,-2)$ の $1$ 通りで、${}_4{\mathrm{C}}_1÷4=1$ と一致する。）

よって、求める並べ方は $1428$ 通りである。

$+1$ を右へ 1、$-2$ を「下へ 1」とみなし、$(i,j)$ を「$+1$ を $i$ 枚、$-2$ を $j$ 枚並べた状態」とする。和は $i-2j$ で、すべての途中の和が正であるとは、始点 $(0,0)$ の後に通る点がすべて $i>2j$ を満たすことである。
$f(i,j)$ を $(0,0)$ から $(i,j)$ までの条件を満たす並べ方の数とすると、$i>2j$ の点で $f(i,j)=f(i-1,j)+f(i,j-1)$（条件外の点の値は $0$）、$f(0,0)=1$。
- $j=0$: $f(i,0)=1$。
- $j=1$ ($i\geqq 3$): $1,2,3,4,5,6,7,8,9,10,11$（$i=3,\dots ,13$）。
- $j=2$ ($i\geqq 5$): $3,7,12,18,25,33,42,52,63$（$i=5,\dots ,13$）。
- $j=3$ ($i\geqq 7$): $12,30,55,88,130,182,245$（$i=7,\dots ,13$）。
- $j=4$ ($i\geqq 9$): $55,143,273,455,700$（$i=9,\dots ,13$）。
- $j=5$ ($i\geqq 11$): $273,728,1428$（$i=11,12,13$）。
- $j=6$ ($i\geqq 13$): $f(13,6)=f(13,5)=1428$。
よって $1428$ 通り。
検算: 全体の和は $13-12=1$ で、循環補題（サイクル補題）により、合計が $1$ になる並べ方 ${}_{19}{\mathrm{C}}_6$ 通りのうち、19 通りの巡回シフトのちょうど 1 つだけが条件を満たす。したがって $\frac{{}_{19}{\mathrm{C}}_6}{19}=\frac{27132}{19}=1428$ となり、上の計算と一致する。