组合公式减去镜像结果
Combination Formula Minus Mirrored Results
我在争论一个 5 人团队可以有多少种组合。我们都同意总组合数是 5！ = 120。我们的不同之处在于不包括镜像结果。所以 ABCDE 与 EDCBA 相同，但 DECBA 不同。
我的想法是你减去 4！其余4个位置产生96种不同的球队组合。
他试图说服我，120 个原始组合中有 1/2 会是一面镜子。
请哪位离散数学高手帮忙解决一下？
你们都说得对，有5个！ = 一组五个唯一元素 {A、B、C、D、E} 的 120 个排列。但是，您的朋友是对的，这些排列中有一半与列表中的其他排列相反。证明很简单：
考虑任何排列 uvxyz。其反面 zyxvu 也是一个排列，并且是唯一确定的。因为反转是它自己的反转，所以 zyxvu 的反转是 uvxyz，原始排列。因此，这组 120 个排列中的每个排列都恰好反映了另一个排列，而该排列不反映任何其他排列。我们可以想象一个二分图，其节点标有排列，并用弧连接标签为反向的节点。必须从此图中移除以消除所有边（镜像）的最小节点数恰好是图中节点的一半。
要对此有一些直觉，请先想象一个小得多的案例，然后再想象一个大得多的案例。考虑 N=3，集合 {A, B, C}。有六种排列：ABC、ACB、BAC、BCA、CAB 和 CBA。如果你的朋友是对的，我们需要删除其中的三个；如果你是对的，我们会删除两个。您可以验证实际上存在三对：
ABC CBA
ACB BCA
BAC CAB
现在，想象一个更大的数字，比如 N=100。如果你的朋友是对的，正好需要删除 50% 的排列。如果你是对的，那么只有 99! 或恰好 1% 的排列需要删除。对于 N=1000，您的朋友说 50% 的排列必须进行，而您说只有 0.1% 的排列被镜像。等等。
我在争论一个 5 人团队可以有多少种组合。我们都同意总组合数是 5！ = 120。我们的不同之处在于不包括镜像结果。所以 ABCDE 与 EDCBA 相同，但 DECBA 不同。
我的想法是你减去 4！其余4个位置产生96种不同的球队组合。
他试图说服我，120 个原始组合中有 1/2 会是一面镜子。
请哪位离散数学高手帮忙解决一下？
你们都说得对，有5个！ = 一组五个唯一元素 {A、B、C、D、E} 的 120 个排列。但是，您的朋友是对的，这些排列中有一半与列表中的其他排列相反。证明很简单：
考虑任何排列 uvxyz。其反面 zyxvu 也是一个排列，并且是唯一确定的。因为反转是它自己的反转，所以 zyxvu 的反转是 uvxyz，原始排列。因此，这组 120 个排列中的每个排列都恰好反映了另一个排列，而该排列不反映任何其他排列。我们可以想象一个二分图，其节点标有排列，并用弧连接标签为反向的节点。必须从此图中移除以消除所有边（镜像）的最小节点数恰好是图中节点的一半。
要对此有一些直觉，请先想象一个小得多的案例，然后再想象一个大得多的案例。考虑 N=3，集合 {A, B, C}。有六种排列：ABC、ACB、BAC、BCA、CAB 和 CBA。如果你的朋友是对的，我们需要删除其中的三个；如果你是对的，我们会删除两个。您可以验证实际上存在三对：
ABC CBA
ACB BCA
BAC CAB
现在，想象一个更大的数字，比如 N=100。如果你的朋友是对的，正好需要删除 50% 的排列。如果你是对的，那么只有 99! 或恰好 1% 的排列需要删除。对于 N=1000，您的朋友说 50% 的排列必须进行，而您说只有 0.1% 的排列被镜像。等等。