5

假设有“n”个数字，我们从中选择“p”个数字（p 小于 n），以便对选定的“p”个数字进行排序。可以重复选择的号码。我们如何计算可以选择的组合数量？例如，如果我们有一组数字，例如 {1,2,3,4,5,6} (n=6)，我们将从集合 (p=3) 中选择 3 个已排序的数字。所以我们可以有 {1,2,3}, {1,1,2}, {2,3,6}, {4,5,5}, {5,5,5} .... . 由于所有这些组合都已排序，因此它们是有效的。我们如何才能找到我们可以获得的此类排序组合的数量？

我的意思是，当我们从一组n 个元素中选择 p 个元素时，应该对所选的p个元素进行排序。

举个小例子：

如果集合是{1,2,3,4}（所以 n = 4）并且我们要选择 3 个元素（p = 3），那么我们可以选择 p 个元素（有替换）的方式数将是4*4*4=64。所以选择会有{1,1,1},{1,1,2},{1,1,3}{1,1,4},{1,2,1}.....{3,1,1}...{4,4,4}. 但在这些选择中，并非所有选择都已排序。在本例中，{1,2,1}并{3,1,1}没有排序。

我想获得排序选择的数量。
谢谢。

4

3 回答 3

6

我看不到排序如何影响结果。对于每一个可能的重复组合，都会有一个对应的排序排列。

因此，问题归结为 n 个元素的组合数量，一次取 p 并替换。这是直接的公式， (n-1+p)C(p) = factorial(n-1+p) / (factorial(p) * factorial(n-1) )

在此处输入图像描述

这是公式的解释，另一个来自 wolfram。

于 2012-10-26T05:57:36.773 回答
3

@BiGYaN在这里的回答是正确的，但在获得这个结果的过程中缺乏幽默感（即使在提供的链接上），所以我决定添加这个 -

  1. 首先OP不应该拿集合来类比，因为集合定义不考虑顺序，而且包含唯一项。

  2. 如果我们采用相同的例子，其中 n = 6 或 [1,2,3,4,5,6]，现在我们要得到长度为 3 的序列，这样 -

    模式 = d1<=d2<=d3 （d 代表数字）。

我们需要这样的序列：{[1,1,1], [1,1,2], .... , [2,2,3], [2,2,4],...}。现在，对于这样的序列，从左侧扫描模式并尝试推理我们是否要增加数字。

例如：从 d1 的左侧开始，如果你决定不在这里增加 d1 的原因，如果你决定不 - d1 将是“1”，现在继续在 d2 之前提出相同的问题，如果你再次决定不向上，d2 再次为“1”。

你可以随时选择加注 5 次，因为范围是 [1-6] 并且 d1 至少应该是 6，如果你决定加注 5 次以获得 [6,6,6]。

所以，问题就变成了为 5 ups 选择合适的位置

[up up up up up d1 d2 d3]

这可能是 [up d1 up up up up up d2 d3] 产生 [2,6,6]，或 [d1 up up up up up d2 up d3 up] 产生 [1,4,5] 或任何类似的组合。

所以，实际上答案是 - C(5 up's + 3 d's, 5 up's) 或更一般地说

C(n-1 up's + k digits, n-1 up's) or C(n-1+k, n-1)

其中，要从 n 个事物中按排序顺序选择 k 个事物。

于 2014-11-20T07:19:14.220 回答
1

您可以从一组元素中选择有替换元素的方法k的数量与您可以从一组元素中选择不带替换元素n的方法的数量相同。后一个值是二项式系数，其值为kn + k - 1n+k-1 choose k(n+k-1)!/(k! (n-1)!)

非正式演示：

假设我有 n 个蓝色盒子。我把它们排成一排（这样它们就被排序了），然后拿了k个红球。我把红球放在行中我喜欢的任何地方，除了最后，所以行必须仍然以蓝色框结束。现在，对于每个红球，我选择以下蓝色框。如果两个或多个红球并排排列，则它们都对应同一个蓝色框。

所以红球和蓝盒子的每一次排列对应着一些蓝盒子替换的选择，而蓝盒子的每一次选择都对应着红球和蓝盒子的一些排列。

红球和蓝盒子有几种排列方式？我的行必须以一个蓝色盒子结束，所以我把那个拿走，现在我可以用我选择的任何方式排列剩余的 n-1 个蓝色盒子和 k 个红色球。或者，换句话说，我可以选择 k + n-1 个位置中的 k 个，然后将红球放在这些位置，用蓝色框填充剩余的位置。

于 2012-10-26T05:04:37.013 回答