algorithm - 网球锦标赛配对 (1x3x5x7x9x...(2n-1) )

Question

需要帮助解决这个算法问题：在网球锦标赛游戏中，我们有 2n 个玩家。在第一轮中，每个玩家只玩一次，因此我们有 n 场比赛，每场比赛有 2 名玩家。证明第一轮球员的配对可以用 1 x 3 x 5 x 7 x 9 ... (2n-1) 精确完成。

它看起来好像是阶乘，但带有奇数。我读到的关于阶乘的所有内容都没有得出这个结论，在组合问题中，消息来源仅解释了 1 对 1 比例的可能配对，而不是 2 对 1，就像在这种情况下（每场比赛 2 名球员）。阅读和阅读让我无处可去。

Answer 1

显然，对于n = 1，只有一种方法可以将两个玩家配对。

现在，归纳地，玩家 1 可以与2*n - 1玩家配对，然后其余2*(n-1)玩家可以配对

1*3*...*(2*n-3)

方法由归纳假设，共为1*3*...*(2*n-3)*(2*n-1)方法。

Answer 2

这个答案说明了在一组n对顶点上的比赛次数t的归纳证明。有关更简单、直接的计数方法，请参阅 Daniel Fischer 的回答。

我使用强归纳来证明t ( n ) = (2 n - 1)!!。

作为一个基础，让n = 1。所以我们有t (1) = (2 - 1)！= 1. 由于只有 1 场比赛只有 1 对球员，所以基础检查。

接下来，我们假设t = (2 m - 1)!! 对于所有m < n，我们让i + 1 = n。我们从i对的比赛开始，添加一个新的对来组成n对，并证明t ( n ) = (2 n - 1)!!。有两种情况需要考虑。情况 1：新对子与自己对抗，而情况 2:则不对抗。由于这两种情况是互斥的，我们可以分别确定每种情况产生的锦标赛数量，并将结果相加。

考虑案例 1，我们可以将新配对与现有玩家匹配多少种方式？好吧，新对中的第一个玩家可以玩任何 2 i个现有玩家，第二个玩家可以玩任何 2 i - 1 个剩余玩家。因此，新对的对战总数为 2 i (2 i - 1)。当然，在我们匹配新配对之后，我们不能忘记还剩下i - 1 对。通过归纳假设，我们可以匹配这些玩家 (2 ( i - 1) - 1)！！方法。应用乘积规则进行计数后，案例 1 的结果为 2 i (2 i - 1) (2 ( i - 1) - 1)！！。

转向案例 2，新对子可以自己玩 1 种方式。通过归纳假设，剩余的i对可以形成锦标赛 (2 i - 1)！方式，所以案例 2 的总数是 (2 i - 1)!!。

将这两种情况相加，我们有t ( n ) = 2 i (2 i - 1) (2 ( i - 1) - 1)！！+ (2 i - 1)！！。

我们分解出 (2 ( i - 1) - 1)!! 在右边得到t ( n ) = (2 ( i - 1) - 1)!! (2 i (2 i - 1) + (2 i - 1))。

结合类似的术语，我们有t ( n ) = (2 ( i - 1) - 1)!! (2 i - 1)(2 i + 1)。

将尾随因子折叠成双因子我们有t ( n ) = (2 ( i + 1) - 1)！！

最后，我们应用i的定义，我们有 t ( n ) = (2 n - 1)！！