東京大学 新領域創成科学研究科 メディカル情報生命専攻 2019年8月実施 問題12

标签：

• Tokyo-University
• Counting-Ordered-Pairings
• Recurrence-Relation

Author

zephyr

Description

For a mouse aging experiment, we need to pair male and female mice, with these rules:

• Each mouse can match at most one other mouse.
• Each match must be between opposite genders.
• A female can only match a younger male.

Assume that no two mice have exactly the same age. We have a list of $n$ mice, numbered from 1 to $n$ in order of increasing age.

$$F[i] = \begin{cases} 0 & \text{if the $i$-th mouse is male} \\ 1 & \text{if the $i$-th mouse is female} \end{cases}$$

$G[i]$ is the number of males among the first $i$ mice.

$C[i, j]$ is the number of ways of making $j$ matches among the first $i$ mice.

Let $C[i, 0] = 1$ (i $\geq$ 1).

(1) What is $C[1, j]$ when $j > 0$?

(2) Suppose we have already made $j$ matches among the first $i$ mice, and $F[i + 1] = 1$. How many remaining ways are there of matching the $(i + 1)$-th mouse?

(3) Write a formula for $C[i + 1, j + 1]$ in terms of $C[i, j + 1]$ and $C[i, j]$.

---

在一项小鼠衰老实验中，我们需要为雄性和雌性小鼠配对，规则如下：

• 每只小鼠最多只能与另一只小鼠匹配。
• 每次匹配必须是异性之间的匹配。
• 雌性只能与比自己年轻的雄性匹配。

假设没有两只小鼠年龄完全相同。我们有一个编号为 1 到 $n$ 的小鼠列表，按年龄递增顺序排列。

$$F[i] = \begin{cases} 0 & \text{如果第 $i$ 只小鼠是雄性} \\ 1 & \text{如果第 $i$ 只小鼠是雌性} \end{cases}$$

$G[i]$ 是前 $i$ 只小鼠中雄性的数量。

$C[i, j]$ 是前 $i$ 只小鼠中进行 $j$ 次匹配的方法数量。

设 $C[i, 0] = 1$ (i $\geq$ 1)。

(1) 当 $j > 0$ 时，$C[1, j]$ 是多少？

(2) 假设我们已经在前 $i$ 只小鼠中进行了 $j$ 次匹配，且 $F[i + 1] = 1$。匹配第 $(i + 1)$ 只小鼠还有多少剩余的方法？

(3) 用 $C[i, j + 1]$ 和 $C[i, j]$ 表示 $C[i + 1, j + 1]$ 的公式。

题目描述

在小鼠衰老实验中给雌雄小鼠配对，规则为：每只小鼠至多参加一次配对；每对必须一雄一雌；雌鼠只能与比它年轻的雄鼠配对。所有小鼠年龄互异，并将 $n$ 只小鼠按年龄递增编号为 $1,\ldots,n$。定义

$$F[i]= \begin{cases} 0,&\text{第 }i\text{ 只为雄鼠},\\ 1,&\text{第 }i\text{ 只为雌鼠}, \end{cases}$$

$G[i]$ 为前 $i$ 只小鼠中的雄鼠数，$C[i,j]$ 为仅使用前 $i$ 只小鼠组成恰好 $j$ 对的方案数，并规定

$$C[i,0]=1\qquad(i\ge1).$$

回答下列问题：

1. 对 $j>0$，求 $C[1,j]$。
2. 已在前 $i$ 只中组成 $j$ 对，且 $F[i+1]=1$，求为第 $i+1$ 只雌鼠选择尚未配对、比它年轻的雄鼠共有多少种可能。
3. 用 $C[i,j+1]$ 与 $C[i,j]$ 写出 $C[i+1,j+1]$ 的递推式；公式须同时反映第 $i+1$ 只小鼠的性别以及选择不配对或新增一对的情形。

考点

• 有序异性配对计数：利用年龄顺序保证新出现的雌鼠只能选择此前雄鼠，并扣除已被 $j$ 对占用的雄鼠。
• 组合计数递推：按第 $i+1$ 只小鼠是否参与新配对分类，把前缀方案数递推到更长前缀。
• 动态规划边界：正确处理零对方案、单只小鼠及无法达到的配对数量，为二维计数表设置初值。

Kai

(1)

For $C[1, j]$ when $j > 0$, since we only have one mouse, we cannot form any pairs if $j > 0$. Therefore,

$$C[1, j] = 0 \quad \text{for} \quad j > 0$$

(2)

If the $(i + 1)$-th mouse is female ($F[i + 1] = 1$), she can be paired with any of the $G[i]$ males among the first $i$ mice, as long as each male has not been paired yet. Therefore, the number of ways of matching the $(i + 1)$-th mouse is:

$$G[i] - j$$

since $G[i]$ is the total number of males among the first $i$ mice, and $j$ is the number of pairs already formed.

(3)

To derive the formula for $C[i + 1, j + 1]$:

1. If the $(i + 1)$-th mouse is male ($F[i + 1] = 0$), he cannot form a new pair immediately. Thus,

$$C[i + 1, j + 1] = C[i, j + 1]$$

1. If the $(i + 1)$-th mouse is female ($F[i + 1] = 1$), she can form a new pair with any of the $G[i] - j$ available males among the first $i$ mice. This adds $(G[i] - j) \times C[i, j]$ new ways of making $j + 1$ matches by pairing her with one of these males.

Combining both cases, we get the formula:

$$C[i + 1, j + 1] = C[i, j + 1] + (G[i] - j) \times C[i, j]$$

Hence, the formula for $C[i + 1, j + 1]$ can be written as:

$$C[i + 1, j + 1] = C[i, j + 1] + (G[i] - j) \times C[i, j] \times F[i+1]$$

Knowledge

动态规划 组合计数

重点词汇

1. Match 配对
2. Male 雄性
3. Female 雌性
4. Combination 组合
5. Dynamic Programming 动态规划

参考资料

1. Kenneth H. Rosen, "Discrete Mathematics and Its Applications", Chapter 7: Counting and Probability

算法代码

def count_mouse_pairings(F, n):
    # Initialize G array
    G = [0] * (n + 1)
    for i in range(1, n + 1):
        G[i] = G[i-1] + (1 - F[i])

    # Initialize C array
    C = [[0] * ((n // 2) + 1) for _ in range(n + 1)]
    
    # Base cases
    for i in range(n + 1):
        C[i][0] = 1
    
    # Dynamic Programming
    for i in range(1, n + 1):
        for j in range(1, min(i // 2, G[i]) + 1):
            if i == 1:
                C[i][j] = 0
            else:
                C[i][j] = C[i-1][j] + (G[i-1] - (j-1)) * C[i-1][j-1] * F[i]

    return C

# Example usage
n = 5
F = [0, 1, 0, 1, 0, 1]  # 0-indexed, but we ignore F[0]
result = count_mouse_pairings(F, n)

# Print results
for i in range(1, n + 1):
    for j in range(min(i // 2, sum(1 - F[k] for k in range(1, i+1))) + 1):
        print(f"C[{i}][{j}] = {result[i][j]}")