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.

i don't know how to solve this. I am asking for a approach so as to solve this

It looks like a fairly straight forward recursive algorithm. Work it through in words (pseudo code) what you need to solve it.

This article has been dead for over six months. Start a new discussion instead.