Car Convoy Problem（その3） - 球面倶楽部零八式 mark II

Car Convoy Problem（その2） - 球面倶楽部零八式 mark II
の続き

$N$ 台の車における Car Convoy Problem において，車列の数が $M$ となる確率 $P(M,N)$ について論ぜよ．

$M\gt N$ ， $M\lt 0$ のときは $P(M,N)=0$ とする．

漸化式
$P(1,N+1)=\dfrac{1}{N+1}$ ，
$P(M,N+1)=\dfrac{N P(M,N) + P(M-1,N+1)}{N+1}$ （ $M\geqq 2$ ）
( $P(N+1,N+1)=\dfrac{1}{(N+1)!}$ )
が成立するので，これを解こうとすれば良いのだが，難しい．
（この漸化式は，参照した web page
Probability problem: cars on the road - Mathematics Stack Exchange
の Hagen von Eitzen の解答と同じ考え方）

ここで $Q(M,N):=(N!)P(M,N)$ とおくと，漸化式は
$Q(N,N)=1$ ，
$Q(M,N)=Q(M-1,N-1)+ (N-1)Q(M,N-1)$
となる．

$L=N-s$ とおくと
$Q(N-s,N)=Q(N-s-1,N-1)+ (N-1)Q(N-s,N-1)$
となるので，
$q_s(N):=Q(N-s,N)$
とおくと
$q_s(s)=0$ ，
$q_s(N)=q_s(N-1)+ (N-1)\cdot q_{s-1}(N-1)$ （ $N\geqq s+1$ ）
という漸化式が得られ，
$q_s(N)=q_s(s)+\displaystyle\sum_{m=s}^{N-1}m\cdot q_{s-1}(m)$
$q_s(N)=\displaystyle\sum_{m=s}^{N-1}m\cdot q_{s-1}(m)$
を計算すれば良いことがわかる．

(i) $s=0$ のとき， $q_0(N)=Q(N,N)=1$ である．

(ii) $s=1$ のとき
$q_1(N)=\displaystyle\sum_{m=1}^{N-1} m=\dfrac{N(N-1)}{2}$ $={}_N\mbox{C}_2$
である．

(iii) $s=2$ のとき，
$q_2(N)=\displaystyle\sum_{m=2}^{N-1}m\cdot q_{1}(m)$
$=\displaystyle\sum_{m=2}^{N-1}m\cdot {}_m\mbox{C}_2$
$=\displaystyle\sum_{m=2}^{N-1}\bigl( (m+1){}_m\mbox{C}_2-{}_m\mbox{C}_2\bigr)$
$=\displaystyle\sum_{m=2}^{N-1}\bigl(3\cdot {}_{m+1}\mbox{C}_3-{}_m\mbox{C}_2\bigr)$
$=\displaystyle\sum_{m=2}^{N-1} \{3\bigl({}_{m+2}\mbox{C}_4-{}_{m+1}\mbox{C}_4\bigr)-\bigl({}_{m+1}\mbox{C}_3-{}_{m}\mbox{C}_3\bigr)\}$
$=3\cdot {}_{N+1}\mbox{C}_4 - {}_{N}\mbox{C}_3$
$=3\cdot {}_{N}\mbox{C}_4 + 2 \cdot {}_{N}\mbox{C}_3$

一般に，
$=\displaystyle\sum_{m=r}^{N-1}m\cdot {}_m\mbox{C}_r$ $＝(r+1)\cdot {}_N\mbox{C}_{r+2}+r \cdot {}_N\mbox{C}_{r+1}$
が成立することに注意すると，

(iii) $s=3$ のとき，
$q_3(N)=\displaystyle\sum_{m=3}^{N-1}m\cdot q_{2}(m)$
$=3\displaystyle\sum_{m=3}^{N-1}m\cdot {}_m\mbox{C}_4$ $+2\displaystyle\sum_{m=3}^{N-1}m\cdot {}_m\mbox{C}_3$
$=15 {}_N\mbox{C}_6$ $+20 {}_N\mbox{C}_5$ $+6 {}_N\mbox{C}_4$
となる．

例えば， $Q(4,7)=q_3(7)$ $=15 {}_7\mbox{C}_6$ $+20 {}_7\mbox{C}_5$ $+6 {}_7\mbox{C}_4$ $=15\times 7+20 \times 21+6\times 35$ $=735$ となるので，7台あるときに車列の数が4になる確率は
$\dfrac{735}{7!}$ $=\dfrac{7}{48}$
となることがわかる．

(iii) $s=4$ のとき，
$q_4(N)$ $=105\cdot {}_N\mbox{C}_8$ $+210\cdot {}_N\mbox{C}_7$ $+130\cdot {}_N\mbox{C}_6$ $+24\cdot {}_N\mbox{C}_5$

例えば， $Q(3,7)=q_4(7)$ $=105\times 0+210\times 1+130\times 7+24\times 21$ $=1624$ となるので，7台あるときに車列の数が3になる確率は
$\dfrac{1624}{7!}$ $=\dfrac{29}{90}$
となることがわかる．

同様に考えると,
$q_s(N)=\displaystyle\sum_{m=s+1}^{2s} \alpha_{m,s}\cdot {}_N\mbox{C}_m$
をみたす自然数 $\alpha_{s,m}$ が存在することがわかり，よって
$Q(M,N)=q_{N-M}(N)$ $=\displaystyle\sum_{m=N-M+1}^{2(N-M)} \alpha_{m,N-M}\cdot {}_N\mbox{C}_m$
のように表現できることがわかった．
これら係数の値は
$Q(N-s,N)$ （ $N=s+1,\ldots,2s$ ）から計算することができるが，
帰納的に， $\alpha_{s+1,s}=s!$ ， $\alpha_{2s,s}=(2s-1)!!$ であることはすぐにわかる．

他の係数は単純に表すことができるかは謎．

結局，
$P(M,N)=\dfrac{1}{N!}\displaystyle\sum_{m=N-M+1}^{2(N-M)} \alpha_{m,N-M}\cdot {}_N\mbox{C}_m$
$=\displaystyle\sum_{m=N-M+1}^{2(N-M)} \dfrac{\alpha_{m,N-M}}{m!(n-m)!}$
の形となる．

Car Convoy Problem（その4） - 球面倶楽部零八式 mark II