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

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 mice, numbered from 1 to in order of increasing age.

is the number of males among the first mice.

is the number of ways of making matches among the first mice.

Let (i 1).

(1) What is when ?

(2) Suppose we have already made matches among the first mice, and . How many remaining ways are there of matching the -th mouse?

(3) Write a formula for in terms of and .

---

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

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

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

是前 只小鼠中雄性的数量。

是前 只小鼠中进行 次匹配的方法数量。

设 (i 1)。

(1) 当 时， 是多少？

(2) 假设我们已经在前 只小鼠中进行了 次匹配，且 。匹配第 只小鼠还有多少剩余的方法？

(3) 用 和 表示 的公式。

Kai

(1)

For when , since we only have one mouse, we cannot form any pairs if . Therefore,

(2)

If the -th mouse is female (), she can be paired with any of the males among the first mice, as long as each male has not been paired yet. Therefore, the number of ways of matching the -th mouse is:

since is the total number of males among the first mice, and is the number of pairs already formed.

(3)

To derive the formula for :

1. If the -th mouse is male (), he cannot form a new pair immediately. Thus,

1. If the -th mouse is female (), she can form a new pair with any of the available males among the first mice. This adds new ways of making matches by pairing her with one of these males.

Combining both cases, we get the formula:

Hence, the formula for can be written as:

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]}")