algorithm - 假设一个数字大于另一个数字，则 2 个数字的可能结果数

Question

我正在尝试编写一个算法来计算结果。但我需要组合数学方面的帮助。

假设我必须从 1 到 10 中选择 2 个数字。根据计数的基本规则，在没有任何限制的情况下，可能结果的数量是 10 * 10 = 100。（选择第一个数字的 10 个可能结果 x 10 个可能选择第二个的结果）。

鉴于第一个数字必须大于第二个数字，可能的结果数量是多少？

Answer 1

45.

想象一下你的 10x10 对网格。从 1,1 到 10,10 有一条对角线，其中 A=B，所以那些不是 A>B。该行将其他情况分为两半。一是 A>B，一是 B < A。这些分区中的每一个都是相同的大小。剩下 90 个值（对角线取 10 个），所以有 45 对 A > B。

Answer 2

如果您选择：

• 1：2 到 10 = 9 种可能性
• 2：3 到 10 = 8 种可能性
• ...
• 9：10 = 1 种可能性

所以

9 + 8 + ... + 2 + 1 = 45

这称为算术级数，其总和等于：

f(n) = n * (n+1) / 2 = 9 * 10 / 2 = 45

Answer 3

我会说

f(n) = n * (n-1) / 2

其中 n 等于需要组合的不同数字的数量。所以对于 n = 10 它将是：

10 * (10-1) / 2 = 45

Answer 4

您的问题属于二项式系数。计算 10 个项目的唯一组合总数，一次取 2 个，公式 N! /（K！（N - K）！）可以使用。为 N 代入 10，为 K 代入 2 得到 45。

我编写了一个类来处理处理二项式系数的常用函数，这是属于这种问题的类型。它执行以下任务：

1. 将任何 N 选择 K 的所有 K 索引以良好的格式输出到文件。K-indexes 可以替换为更具描述性的字符串或字母。这种方法使得解决这类问题变得非常简单。

2. 将 K 索引转换为已排序二项式系数表中条目的正确索引。这种技术比依赖迭代的旧已发布技术快得多。它通过使用帕斯卡三角形固有的数学属性来做到这一点。我的论文谈到了这一点。我相信我是第一个发现并发表这种技术的人，但我可能是错的。

3. 将已排序二项式系数表中的索引转换为相应的 K 索引。

4. 使用Mark Dominus方法计算二项式系数，它不太可能溢出并且适用于更大的数字。

5. 该类是用 .NET C# 编写的，并提供了一种通过使用通用列表来管理与问题相关的对象（如果有）的方法。此类的构造函数采用一个名为 InitTable 的 bool 值，当它为 true 时，将创建一个通用列表来保存要管理的对象。如果此值为 false，则不会创建表。无需创建表即可执行上述 4 种方法。提供了访问器方法来访问表。

6. 有一个关联的测试类，它显示了如何使用该类及其方法。它已经用 2 个案例进行了广泛的测试，并且没有已知的错误。

要了解此类并下载代码，请参阅制表二项式系数。

将此类转换为 C++ 应该不难。