Algorithm to find the possible number of selections

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 开发者_StackOverflowcolor 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.

---

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.

---

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)