找到可能的选择数量的算法
我被问过这个问题，并对此进行了相当多的思考，但未能解决。
问题是：
我被要求选择 n 支彩色铅笔。有 k 种不同颜色组的铅笔。每个颜色组中还有无限多的铅笔。我想要每个颜色组至少有一支铅笔，但我的选择仍然有很多可能性。
这组选择可以有多少种可能性？ 假设无法区分相同颜色的铅笔，并且铅笔的顺序无关。
I have been asked this question and have given this quite some thought but was not able to solve it.
The question is:
I am asked to select n colored Pencils. There are pencils of k different color group. From each color group there are also infinitely many pencils. I want to have at least one pencil of each color group, but still there are a lot of possibilities for my selection.
How many possibilities for this set of selection can one have ?
Assume that pencil of same color can't be distinguished, and the order of the pencils is irrelevant.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
想象 n 个槽，它们之间有 n-1 个空格。将 k-1 个分隔符放入槽之间的空间中（每个槽最多 1 个分隔符）确定有效选择：将第一种颜色放入第一个分隔符之前的所有槽中，将第二种颜色放入第一个分隔符之后和第二个分隔符之前的槽中等。由于每两个分隔符之间至少有一个空格，因此每种颜色至少有一支铅笔。
映射是一对一的，因为每个选择也会生成唯一的分隔符配置。
将 k-1 个分隔符放入 n-1 个空间可以通过 N(n-1,k-1) 种方式完成，其中 N 是牛顿符号，因此答案是 N(n-1,k-1)。
基于 djna 答案的另一种表示方式：
固定 k 支铅笔，每种颜色一支 - 每种颜色至少需要一支，因此这些将确保满足此要求。现在你剩下 nk 个选择，你可以按照你想要的方式在颜色之间分割，这次不必关心选择每种颜色（这是由首先选择的 k 支铅笔保证的）。解决方案的数量就是你可以分割的方式数量将 nk 个不可区分的铅笔分成 k 个可区分的（*）分区。
这个怎么枚举呢？将k-1笔添加到nk铅笔中，将它们排列起来并从左到右着色，遇到铅笔后改变颜色。例如，将钢笔表示为
*，将铅笔表示为-，具有三种颜色（红、绿、蓝）：表示两支红色铅笔、零支绿色和一支蓝色。在这样的表示中，有 (nk) + (k-1) = n-1 个元素（钢笔和铅笔）。从中，您需要选择 k-1 个钢笔位置（或 nk 个铅笔位置，因为选择一组决定了）可以实现的方法有 N(n-1,k-1) 种。
(*) 我假设“2 红，1 绿”与“2 绿，1 红”不同，否则是完全不同的任务。
Imagine n slots with n-1 spaces between them. Putting k-1 separators into the spaces between the slots (max 1 separator per slot) determines a valid selection: put first color into all of the slots before the first separator, the second color into the slots after the first and before the second separator, etc. Since there's at least one space between each two separators, there will be at least one pencil in each color.
The mapping is one-to-one, since every selection also generates a unique configuration of separators.
Putting k-1 separators into n-1 spaces can be done in N(n-1,k-1) ways, where N is the Newton symbol, so the answer is N(n-1,k-1).
Another way of representing this, based on djna answer:
Fix k pencils, one in each color - you nead at least one in each color, so these will make sure this requirement is fulfilled. Now you have n-k picks left, which you can split between colors anyway you want, this time not having to care about picking each color (this is assured by k pencils chosen first.) The number of solutions is the number of ways you can split n-k indistinguishable pencils into k distinguishable(*) partitions.
How to enumerate this? Add k-1 pens to your n-k pencils, line them up and color from left to right, changing color after encountering a pencil. For example, representing pens as
*and pencils as-, with three colors (red, green, blue) this:represents two red pencils, zero green and one blue. In such a representation, there are (n-k) + (k-1) = n-1 elements (pens and pencils.) From these, you need to pick k-1 pen positions (or n-k pencil positions, since picking one set determines the other.) The number of ways you can do that is N(n-1,k-1).
(*) I assume that "2 red, one green" is different from "2 green, one red", otherwise is a totally different task.
我们假设n＞1。 k，否则无法实现“每种颜色至少一种”。
然后你的前 k 个选择就完全定义好了，每种颜色一个。剩下的就是（nk）铅笔，可以是任何颜色。所以第一个选项有 k 个选择，第二个选项有 k 个……
换句话说： k ^ (n -k)
We assume n > k, otherwise you can't achieve "at least one of each colour".
Then your first k picks are completely defined, one of each colour. All that remains are the (n-k) pencils which can be any colour. so thats k choices for the first, k for the second ...
In other words: k ^ (n -k)