東京工業大学 情報理工学院 数理・計算科学系 2017年8月実施 午前 問C

标签：

• TITech
• Binomial-Coefficient

Author

祭音Myyura

Description

以下の図に示すような $n \times m$ の格子を考える．ただし $n \geq m \geq 1$ とする．

ここで，点 $(0, 0)$ から点 $(n, m)$ まで，条件 1 を満たすように隣接する点の間を移動する経路全体の集合を $\mathcal{P}(n, m)$ とする．

• 条件 1: 経路上の全ての点に関して，その右または上の隣接点へのみ移動可能．

有限集合 A に対して |A| は A の濃度 (要素数) を表すものとする．

(1) $|\mathcal{P}(n,m)|$ を求めよ．

$\mathcal{P}(n,m)$ に含まれる経路で，条件 2 を満たす経路全体の集合を $\mathcal{B}(n, m) \subseteq \mathcal{P}(n, m)$ とする．

• 条件 2: ある $a \in \{1, . . . , m\}$ に対して，経路上に点 $(a, a)$ が存在する．すなわち，経路は上図に示した • 印の点を少なくとも 1 つ経由する．

集合 $\mathcal{B}(n,m)$ を $\mathcal{B}_{(0,1)}(n,m) \subseteq \mathcal{B}(n,m)$ と $\mathcal{B}_{(1,0)} \subseteq \mathcal{B}(n,m)$ に分割する．

• $\mathcal{B}_{(0,1)}(n,m): \mathcal{B}(n,m)$ に含まれる経路で，点 $(0, 1)$ を通る経路全体の集合．
• $\mathcal{B}_{(1,0)}(n,m): \mathcal{B}(n,m)$ に含まれる経路で，点 $(1, 0)$ を通る経路全体の集合．

(2) $|\mathcal{B}_{(0,1)}(n,m)|$ を求めよ．

(3) $|\mathcal{B}_{(1,0)}(n,m)|$ を求めよ．

(4) $r(n,m) = \frac{|\mathcal{G}(n,m)|}{|\mathcal{P}(n,m)|}$ | を求めよ．ただし $\mathcal{G}(n,m) = \mathcal{P}(n,m) \setminus \mathcal{B}(n,m)$． また $n = 15, m = 10$ として $r(15, 10)$ を求めよ．

题目描述

考虑题面图示的 $n\times m$ 方格，其中 $n\geq m\geq1$。令 $\mathcal P(n,m)$ 为所有从 $(0,0)$ 走到 $(n,m)$ 且满足条件 1 的格路径集合。

• 条件 1： 在路径上的每一点，只能移动到其右侧或上侧的相邻点。

对有限集合 $A$，以 $|A|$ 表示其元素个数。

1. 求 $|\mathcal P(n,m)|$。

在 $\mathcal P(n,m)$ 中，令 $\mathcal B(n,m)$ 为满足条件 2 的路径集合。

• 条件 2： 存在某个 $a\in\{1,\ldots,m\}$，使路径经过点 $(a,a)$；也就是说，路径至少经过题面图中一个以黑点标出的正对角点。

再把 $\mathcal B(n,m)$ 分为以下两个子集：

• $\mathcal B_{(0,1)}(n,m)$：$\mathcal B(n,m)$ 中经过点 $(0,1)$ 的全部路径；
• $\mathcal B_{(1,0)}(n,m)$：$\mathcal B(n,m)$ 中经过点 $(1,0)$ 的全部路径。

2. 求 $|\mathcal B_{(0,1)}(n,m)|$。

3. 求 $|\mathcal B_{(1,0)}(n,m)|$。

4. 定义

   $$\mathcal G(n,m)=\mathcal P(n,m)\setminus\mathcal B(n,m), \qquad r(n,m)=\frac{|\mathcal G(n,m)|}{|\mathcal P(n,m)|}.$$

   求 $r(n,m)$ 的表达式，并进一步计算 $n=15,m=10$ 时的 $r(15,10)$。

考点

• 格路径与二项式系数：把向右、向上的步序列计数转化为组合数。
• 对角线首次相交的路径计数：利用路径分割或反射对应关系，分别计算经 $(0,1)$、$(1,0)$ 且触及正对角点的路径。
• 补集概率：由总路径数减去经过指定对角点的路径数，化简合法路径比例并代入给定参数。

Kai

(1)

Total number of moves in which we have to move up to reach the last row $= m$

Total number of moves in which we have to move right to reach the last column $= n$

Total moves $= m + n$

Now think of moves as a string of ‘R’ and ‘U’ characters where ‘R’ at any ith index will tell us to move ‘Right’ and ‘U’ will tell us to move ‘Up’. Then $\mathcal{P}(n,m)$ equals to how many unique strings (moves) we can make where in total there should be $(n + m)$ characters and there should be $m$ ‘U’ character and $n$ ‘R’ character. Note that choosing positions of $n$ ‘R’ characters results in the automatic choosing of $m$ ‘U’ character positions

Therefore,

$$\mathcal{P}(n,m) = \binom{n+m}{m}$$

(2)

Note that all paths go through the point $(0,1)$ will cross the line $y=x$, hence

$$\mathcal{B}_{(0,1)} (n,m) = \mathcal{P}(n, m-1) = \binom{n+m-1}{m-1}$$

(3)

We take a path from $(1,0)$ to $(n,m)$ which touch (cross) the line $y=x$, and let $p$ be the point where it first touches this line.

If we reflect the portion of the path from $(1,0)$ to $p$ around the line $y=x$, then we get a path from $(0,1)$ to $(n,m)$. Conversely, any path from $(0,1)$ to $(n,m)$ must cross the line $y=x$. If we let $p'$ be the point where the path first touches this line and reflect the portion of the path from $(0,1)$ to $p'$ about this line, then we get a path from $(1,0)$ to $(n,m)$.

Since this gives a bijection between the two types of paths, and since the number of paths from $(0,1)$ to $(n,m)$ is given by $\mathcal{B}_{(0,1)} (n,m)$, we have

$$\mathcal{B}_{(1,0)} (n,m) = \mathcal{B}_{(0,1)} (n,m) = \binom{n+m-1}{m-1}$$

(4)

By (2) and (3) we have

$$\begin{aligned} r(n,m) &= \frac{|\mathcal{G}(n,m)|}{|\mathcal{P}(n,m)|} = \frac{\binom{n+m}{m}-2\binom{n+m-1}{m-1}}{\binom{n+m}{m}} \\ &= 1 - \frac{2\binom{n+m-1}{m-1}}{\binom{n+m}{m}} \\ &= 1 - 2 \cdot \frac{(n+m-1)!}{(m-1)!n!} \cdot \frac{m!n!}{(m+n)!} \\ &= 1 - \frac{2m}{m+n} \end{aligned}$$

Then

$$r(15, 10) = 1 - \frac{2 \times10}{10 + 15} = \frac{1}{5}$$