简单组合学：配对元素的方法数
Simple combinatorics: Number of ways to pair up elements
我正在尝试解决这个问题：https://www.urionlinejudge.com.br/judge/en/problems/view/1616
It's the end of the year, and finally Rafael is graduating in his
Computing course. His classmates decided to celebrate the graduation
organizing a ball, where there would be live music, food and free
drinks. As all balls, the most expected moment is the one in which
everyone starts to dance in pairs.
The pairs will be formed between a boy and a girl, and as Rafael's
classmates are so shy, that they decided to plan ahead what the pairs
would be. There is only one problem: there are more boys than girls in
the class. This implies that, if everyone wants to dance at least
once, one or more girls will have to dance with more than one boy.
Rafael asked your help: in how many ways the pairs can be formed, in
such a way that all the boys dance exactly once, and all the girls
dance at least once
虽然可能有一个数学上的封闭形式的解决方案，但我正在尝试使用动态规划来解决它。我不太能想出复发。有人能给我指出正确的方向吗？
这里需要的是b个元素集合到g个元素集合的满射函数个数
有通用公式，这里不一定需要。
一个简单的递归公式可以直接得到
让我们假设我们知道 b 男孩和 g 女孩的可能性 S(b, g) 的数量。然后一个新男孩来了。我们要计算S(b+1, g)。
我们有两种可能性：
- 将这个新男孩与一个已经有至少一个伴侣的女孩配对 -> 我们有
g * S(b,g) 种可能性
- 以独特的方式将这个新男孩与一个女孩配对 -> 我们有
g * S(b, g-1) 种可能性
最后，我们得到递归关系
S(b, g) = g * (S(b-1, g) + S(b-1, g-1))
在以递归方式实现解决方案时，我们必须考虑：
S(b=g, g) = g!
S(b, 1) = 1
实现该方案时注意不要多次计算同一个值，例如通过使用记忆。
我正在尝试解决这个问题：https://www.urionlinejudge.com.br/judge/en/problems/view/1616
It's the end of the year, and finally Rafael is graduating in his Computing course. His classmates decided to celebrate the graduation organizing a ball, where there would be live music, food and free drinks. As all balls, the most expected moment is the one in which everyone starts to dance in pairs.
The pairs will be formed between a boy and a girl, and as Rafael's classmates are so shy, that they decided to plan ahead what the pairs would be. There is only one problem: there are more boys than girls in the class. This implies that, if everyone wants to dance at least once, one or more girls will have to dance with more than one boy.
Rafael asked your help: in how many ways the pairs can be formed, in such a way that all the boys dance exactly once, and all the girls dance at least once
虽然可能有一个数学上的封闭形式的解决方案，但我正在尝试使用动态规划来解决它。我不太能想出复发。有人能给我指出正确的方向吗？
这里需要的是b个元素集合到g个元素集合的满射函数个数
有通用公式，这里不一定需要。
一个简单的递归公式可以直接得到
让我们假设我们知道 b 男孩和 g 女孩的可能性 S(b, g) 的数量。然后一个新男孩来了。我们要计算S(b+1, g)。
我们有两种可能性：
- 将这个新男孩与一个已经有至少一个伴侣的女孩配对 -> 我们有
g * S(b,g)种可能性 - 以独特的方式将这个新男孩与一个女孩配对 -> 我们有
g * S(b, g-1)种可能性
最后，我们得到递归关系
S(b, g) = g * (S(b-1, g) + S(b-1, g-1))
在以递归方式实现解决方案时，我们必须考虑：
S(b=g, g) = g!
S(b, 1) = 1
实现该方案时注意不要多次计算同一个值，例如通过使用记忆。