CBMS-2020-12

题目来源：[[做题/文字版题库/CBMS/2020#Question 10|2020#Question 12]] 日期：2024-07-23 题目主题：CS-离散数学-组合数学

解题思路

这道题涉及匹配雄性和雌性老鼠的组合问题，使用动态规划的方法来解决。我们需要计算出满足特定条件的匹配数，主要条件是匹配必须是不同性别，且雌性老鼠只能与比她年轻的雄性老鼠匹配。具体问题细分如下：

1. 计算初始状态下的组合数 $C[1,j]$。
2. 给定已有匹配数的情况下，计算添加新的雌性老鼠后的匹配方法数。
3. 推导出一般情况下的递推关系式。

Solution

Question 1: What is $C[1,j]$ when $j>0$?

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\text{for}j>0$$

Question 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?

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.

Question 3: Write a formula for $C[i+1,j+1]$ in terms of $C[i,j+1]$ and $C[i,j]$

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]$$

知识点

动态规划组合计数

重点词汇

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