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.
