最短経路の数え上げと鏡像原理

方針：点 $(x,y)$ に対して $x+y$ の値を見る。1 歩で $x+y$ がどれだけ変わるかを調べる。
段 1（1 歩の変化）。右・上へ 1 歩進むと $x+y$ は $1$ 増え、左・下へ 1 歩進むと $x+y$ は $1$ 減る。
段 2（必要な歩数）。$A$ では $x+y=a_1+a_2$、$B$ では $x+y=b_1+b_2$ なので、全体で $x+y$ は $d:=(b_1-a_1)+(b_2-a_2)$ 増える。右・上の歩数を $s$、左・下の歩数を $t$ とすると、段 1 により $s-t=d$ である。全体の歩数は $s+t=d+2t\ge d$ である。
段 3（等号の場合）。歩数がちょうど $d$ になるのは $t=0$、つまり左・下を 1 度も使わないときである。$\square$

方針：最短経路と「R を $p$ 個、U を $q$ 個並べた文字列」が 1 対 1 に対応することを示し、文字列の個数を数える。
段 1（経路から文字列へ）。最短経路は、def-lpr-path により R と U を並べた文字列で表され、R は $p$ 個、U は $q$ 個である。
段 2（文字列から経路へ）。逆に、R を $p$ 個、U を $q$ 個並べた文字列を 1 つ決め、$A$ から文字列のとおりに進むと、$x$ 座標は $p$ 増え、$y$ 座標は $q$ 増えて、$B$ に着く。よって最短経路が 1 つ決まる。
段 3（対応が 1 対 1）。段 1 と段 2 の操作は互いに逆である。異なる経路は、はじめて違う方向に進む歩があるので、異なる文字列になる。よって、最短経路の数は文字列の数に等しい。
段 4（数える）。長さ $p+q$ の文字列で、R を置く $p$ か所を選べば、残りの $q$ か所は U で埋まる。選び方は $\dbinom{p+q}{p}$ 通りである（同じものを含む順列の数 $\dfrac{(p+q)!}{p!\,q!}$ としても求まる。同じものを含む順列と多項定理）。$\square$

方針：$(x,y)$ への最短経路を、最後の 1 歩が R か U かで 2 組に分けて数える。
段 1（端）。$y=0$ のとき、U を 1 回も使えないので経路は $RR\cdots R$ の 1 通りである。$x=0$ のときも同様に $1$ 通りである。
段 2（分ける）。$x\ge1$、$y\ge1$ とする。最短経路の最後の 1 歩は R か U のどちらかであり、両方であることはない。
段 3（最後が R の組）。最後が R の経路から最後の R を取り除くと、$(x-1,y)$ への最短経路になる。逆に、$(x-1,y)$ への最短経路の後ろに R を付けると、最後が R の $(x,y)$ への経路になる。この 2 つの操作は互いに逆なので、この組の経路は $N(x-1,y)$ 個である。
段 4（最後が U の組）。同じようにして、最後が U の経路は $N(x,y-1)$ 個である。
段 5（足す）。和の法則により $N(x,y)=N(x-1,y)+N(x,y-1)$ である。$\square$

方針：def-lpr-reflection の式に代入して、3 つを順に確かめる。$P=(x,y)$ とする。
段 1（(1)）。$x,y,c$ が整数なら $y-c$、$x+c$ も整数である。$P$ が $L_c$ 上なら $y=x+c$ なので、$\sigma_c(P)=(x+c-c,\ x+c)=(x,y)=P$ である。また $\sigma_c(\sigma_c(P))=\sigma_c(y-c,\ x+c)=\bigl((x+c)-c,\ (y-c)+c\bigr)=(x,y)$ である。
段 2（(2)）。$\sigma_c(P)=(x',y')$ とおくと $x'=y-c$、$y'=x+c$ である。$\sigma_c(P)$ が上側にある条件 $y'>x'+c$ は、$x+c>y-c+c$、つまり $x+c>y$ と同じであり、これは $P$ が下側にある条件である。上側と下側を入れ替えても同じである。
段 3（(3)）。$P$ から R で進んだ点 $(x+1,y)$ の折り返しは $(y-c,\ x+1+c)$ で、これは $\sigma_c(P)=(y-c,\ x+c)$ から上へ 1 進んだ点である。$P$ から U で進んだ点 $(x,y+1)$ の折り返しは $(y+1-c,\ x+c)$ で、これは $\sigma_c(P)$ から右へ 1 進んだ点である。$\square$

方針：「$A$ から $B$ への、$L_c$ に触れる経路」の集まりを $X$、「$A'$ から $B$ への経路」の集まりを $Y$ とする。$X$ から $Y$ への対応 $\Phi$ と、$Y$ から $X$ への対応 $\Psi$ を作り、互いに逆であることを示す。
段 0（道具：$L_c$ との上下は 1 歩で 1 ずつ変わる）。点 $(x,y)$ に対して $h(x,y):=y-x-c$ とおく。下側は $h<0$、$L_c$ 上は $h=0$、上側は $h>0$ である。R で 1 歩進むと $h$ は $1$ 減り、U で 1 歩進むと $h$ は $1$ 増える。
段 1（$\Phi$ を作る）。$X$ の経路 $w$ を 1 つとる。$w$ は $L_c$ に触れるので、通る点のうち $L_c$ 上にある最初の点 $T$ がある。$w$ の $A$ から $T$ までの部分の通る点をすべて $\sigma_c$ で折り返す。lem-lpr-reflection の (3) により、折り返した点の列は $\sigma_c(A)=A'$ から R と U で進む経路になり、(1) により $\sigma_c(T)=T$ で終わる。これに $w$ の $T$ から $B$ までの部分をつなげたものを $\Phi(w)$ とする。$\Phi(w)$ は $A'$ から $B$ への最短経路なので、$Y$ に入る。
段 2（$Y$ の経路はどれも $L_c$ に触れる）。$Y$ の経路 $v$ をとる。$A$ は下側なので、lem-lpr-reflection の (2) により $A'$ は上側にあり、$h(A')>0$ である。$B$ は下側なので $h(B)<0$ である。段 0 により、$v$ に沿って $h$ は 1 歩ごとに $1$ ずつしか変わらないので、正の値から負の値に移る途中で必ず $0$ を通る。よって $v$ は $L_c$ に触れる。
段 3（$\Psi$ を作る）。$Y$ の経路 $v$ について、段 2 により $L_c$ 上にある最初の通る点 $T'$ がある。$v$ の $A'$ から $T'$ までの部分を $\sigma_c$ で折り返し、$T'$ から $B$ までの部分をつなげたものを $\Psi(v)$ とする。段 1 と同じ理由で、これは $A$ から $B$ への最短経路で、$T'$ を通るので $L_c$ に触れる。よって $\Psi(v)$ は $X$ に入る。
段 4（最初に触れる点は折り返しても変わらない）。段 1 の $w$ で、$T$ より前の通る点はどれも $L_c$ 上にない。それらの折り返しも、(1)・(2) により $L_c$ 上にない（$L_c$ 上の点は $L_c$ 上の点の折り返しでしか得られない。$\sigma_c$ を 2 回行うと元に戻るからである）。よって $\Phi(w)$ で $L_c$ 上にある最初の通る点も $T$ である。同じように、$\Psi(v)$ で $L_c$ 上にある最初の通る点も $T'$ である。
段 5（互いに逆）。$\Psi(\Phi(w))$ を考える。段 4 により $\Phi(w)$ の最初に触れる点は $T$ なので、$\Psi$ は $\Phi(w)$ の $A'$ から $T$ までを折り返す。この部分は $w$ の $A$ から $T$ までを折り返したものなので、もう一度折り返すと (1) により元の $w$ の部分に戻る。$T$ から先は変えていない。よって $\Psi(\Phi(w))=w$ である。同じように $\Phi(\Psi(v))=v$ である。
段 6（結論）。$\Phi$ と $\Psi$ は互いに逆の対応なので、$X$ と $Y$ の経路は 1 対 1 に対応し、個数が等しい。$\square$

方針：「$y\le x$ をみたさない点を通る」ことを「直線 $y=x+1$ に触れる」ことに言いかえ、thm-lpr-reflection を $c=1$ で使う。
段 1（言いかえ）。通る点に $y>x$ となる点があるとする。格子点なので $y\ge x+1$、つまり $h=y-x-1\ge0$ である。出発点 $(0,0)$ では $h=-1<0$ であり、段 0（prf-lpr-reflection）により $h$ は 1 歩ごとに $1$ ずつしか変わらないので、その点までのどこかで $h=0$、つまり $y=x+1$ となる点を通る。逆に $y=x+1$ となる点を通れば、その点で $y>x$ である。よって、「$y\le x$ をみたさない点を通る経路」と「$L_1$ に触れる経路」は同じものである。
段 2（鏡像原理）。$A=(0,0)$ は $0<0+1$、$B=(n,n)$ は $n< n+1$ をみたすので、どちらも $L_1$ の下側にある。$A'=\sigma_1(0,0)=(-1,1)$ である。thm-lpr-reflection により、$L_1$ に触れる経路の数は $(-1,1)$ から $(n,n)$ への経路の数に等しい。この経路は R を $n-(-1)=n+1$ 個、U を $n-1$ 個使うので、thm-lpr-count により $\dbinom{2n}{n+1}=\dbinom{2n}{n-1}$ 通りである。
段 3（引く）。全体は $\dbinom{2n}{n}$ 通りなので、$y\le x$ をみたす経路は $\dbinom{2n}{n}-\dbinom{2n}{n-1}$ 通りである。
段 4（式変形）。$\dbinom{2n}{n-1}=\dfrac{(2n)!}{(n-1)!\,(n+1)!}$ である。$n!=n\cdot(n-1)!$、$(n+1)!=(n+1)\cdot n!$ を使って分母をそろえると
$$ \binom{2n}{n}-\binom{2n}{n-1}=\frac{(2n)!\,(n+1)}{n!\,(n+1)!}-\frac{(2n)!\,n}{n!\,(n+1)!}=\frac{(2n)!}{n!\,(n+1)!}=\frac{1}{n+1}\cdot\frac{(2n)!}{n!\,n!} $$
となる。最後の式は $\dfrac{1}{n+1}\dbinom{2n}{n}$ である。$\square$

方針：開票の順番を $(0,0)$ から $(a,b)$ への最短経路とみる。「A がつねに多い」を「1 歩目が R で、そのあと直線 $y=x$ に触れない」に言いかえ、thm-lpr-reflection を $c=0$ で使う。
段 1（言いかえ）。A がつねに多いとは、出発点以外のすべての通る点で $x>y$、つまり $y< x$ となることである。1 歩目が U なら点 $(0,1)$ で $x< y$ となるので、1 歩目は R でなければならない。よって、求める経路は「1 歩目が R で、$(1,0)$ から $(a,b)$ までの部分が直線 $L_0:y=x$ に触れない経路」であり、その個数は「$(1,0)$ から $(a,b)$ への経路で $L_0$ に触れないもの」の個数に等しい。逆に、1 歩目が R で、$(1,0)$ から先が $L_0$ に触れない経路では、$(1,0)$ で $y-x=-1<0$ であり、prf-lpr-reflection の段 0 により $y-x$ は 1 歩ごとに $1$ ずつしか変わらないので、$0$ にならない限り負のままである。よって $(1,0)$ から先のすべての通る点で $y-x<0$、つまり $y< x$ となり、A がつねに多い。
段 2（全体）。$(1,0)$ から $(a,b)$ への経路は、R を $a-1$ 個、U を $b$ 個使うので、thm-lpr-count により $\dbinom{a+b-1}{a-1}$ 通りある。
段 3（触れる経路）。$(1,0)$ は $0<1$、$(a,b)$ は $b< a$ をみたすので、どちらも $L_0$ の下側にある。$\sigma_0(1,0)=(0,1)$ である。thm-lpr-reflection により、$L_0$ に触れる経路は $(0,1)$ から $(a,b)$ への経路と同じ数だけある。この経路は R を $a$ 個、U を $b-1$ 個使うので $\dbinom{a+b-1}{a}$ 通りである（$b=0$ のときは経路がなく、$\dbinom{a-1}{a}=0$ と約束すれば式もそのまま使える）。
段 4（引いて整理する）。求める経路の数は
$$ \binom{a+b-1}{a-1}-\binom{a+b-1}{a}=\frac{(a+b-1)!}{(a-1)!\,b!}-\frac{(a+b-1)!}{a!\,(b-1)!} $$
である。$a!=a\cdot(a-1)!$、$b!=b\cdot(b-1)!$ を使って分母を $a!\,b!$ にそろえると
$$ \frac{(a+b-1)!\,a}{a!\,b!}-\frac{(a+b-1)!\,b}{a!\,b!}=\frac{(a+b-1)!\,(a-b)}{a!\,b!}=\frac{a-b}{a+b}\cdot\frac{(a+b)!}{a!\,b!} $$
となる（最後は $(a+b)!=(a+b)\cdot(a+b-1)!$ を使った。$b=0$ のときも第 2 項は $0$ で、同じ式になる）。
段 5（確率）。全体は $\dbinom{a+b}{a}=\dfrac{(a+b)!}{a!\,b!}$ 通りで、どれも同じ確からしさなので、確率は段 4 の数をこれで割った $\dfrac{a-b}{a+b}$ である。$\square$