There is a famous recursive relation to find Stirling numbers of the first kind, i.e.

C(n,k)=C(n−1,k−1)+(n−1)C(n−1,k)

This is a solution to the following problem:

```
Given a set of N distinct numbers, how many different permutations of the set exist such that there are exactly K left-to-right maxima?
```

This was not very hard, but the following little variation:

```
Given a multiset of N numbers (not necessarily distinct), how many different permutations of the set exist such that there are exactly K left-to-right maxima (see definition below)?
```

Example:

Let the multiset be S={1,2,2,3} [Note: the two 2s should be considered non-identical while permuting] and K=3. Then, the following permutations:

<1,2,2,3>

<1,2,2,3>

<1,2,3,2>

<1,2,3,2>

satisfy the required condition. Hence, the answer should be 4 (we do not need to find all the permutations but we are interested in the number of such permutations).

```
Definition: An element should be considered a maximum if and only if all the elements occurring before it are strictly less than it.
```

For example, in the above example <1,2,2,3>, the second 2 is not maximum but the first 2 is. Hence, this arrangement satisfy K=3 (not K=4).

PS: I have worked a whole day to solve it, but can't do anything good. Any help is really appreciated.