找到可能的選擇數的算法

Question

我已經被問及這個問題，並給了這個相當多的想法，但無法解決它。

問題是：

我被要求選擇n個彩色鉛筆。有不同顏色組的鉛筆。從每個顏色組還有無限多的鉛筆。我想每個顏色組中至少有一支鉛筆，但我的選擇仍有很多可能性。

這套選擇有多少種可能性？ 假設無法區分同一種顏色的鉛筆，並且鉛筆的順序無關緊要。

Answer 1

想象n個時隙與它們之間的N-1位。將k-1分隔符放入插槽之間的空間（每插槽最多1個分隔符）將確定一個有效的選擇：將第一種顏色放入第一個分隔符之前的所有插槽中，將第二種顏色插入第一個分隔符之前和第二個分隔符之前等等。由於每兩個分隔符之間至少有一個空格，每種顏色至少有一個鉛筆。

映射是一對一的，因爲每個選擇都會生成一個獨立的分隔符配置。可以用N（n-1，k-1）的方式完成k-1個分隔符到n-1個空格，其中N是牛頓符號，所以答案是N（n-1，k-1） ）。

表示此的另一種方式的基礎上，DJNA答案：

修復ķ鉛筆，一個在每種顏色 - 你NEAD每個顏色的至少一個，所以這將確保滿足此要求。現在你有左邊的選擇，你可以在任何你想要的顏色之間分割，這次不需要關心選擇每種顏色（這是由第一個選擇的K鉛筆確定的。）解決方案的數量是你可以分割的方法的數量將不可區分的鉛筆劃分爲k個可區分的（*）分區。

如何枚舉這？將k-1筆添加到您的n-k鉛筆，將它們排列並從左至右着色，在遇到鉛筆後更改顏色。例如，表示作爲筆和*鉛筆作爲-，以三種顏色（紅，綠，藍）這一點：

--**- 

表示兩個紅色鉛筆，零綠色和一個藍色。在這樣的表示中，有（nk）+（k-1）= n-1個元素（鋼筆和鉛筆）。從這些中，您需要選擇k-1筆位置（或者nk鉛筆位置，另一個）。你可以做的方式的數量是N（n-1，k-1）。 （*）我認爲「2紅1綠」不同於「2綠1紅」，否則是完全不同的任務。

Answer 2

我們假設n> k，否則你不能達到「至少每種顏色之一」。

然後你的第一個k選擇是完全定義的，每種顏色之一。所有剩下的都是（n-k）鉛筆，可以是任何顏色。所以這就是ķ選擇用於第一，K爲第二...

換句話說：K ^（N-K）