Suppose we are given N numbers and a value K.

Now we can interchange the positions of numbers to form different combinations, where if there are two same numbers then their arrangments will be considered different.

Now the perfectcount of a combination is given by counting those numbers whose value in the formed combination is higher than any previous value.

e.g if combination is 1 2 2 3 then here perfectcount is 3 as 1 is greater than any previous value, and the first 2 is greater than 1, and last 3 is greatest.

I need to find the count of all those combinations whose perfectcount does not exceed K.

EXAMPLE : Say we have 4 numbers given {1,2,2,3} and lets K=3 then here there are 24 combinations whose perfect count is less than or equal to K.

These are as follows: (to make both 2 different I have used 2(1) to depict first 2 and 2(2) to depict second 2)

1. {1,2(1),2(2),3} 
2. {1,2(1),3,2(2)} 
3. {1,3,2(1),2(2)}
4. {2(1),2(2),1,3}
5. {2(1),1,2(2),3}
6. {2(1),1,3,2(2)}
7. {2(1),2(2),3,1}
8. {2(1),3,2(2),1}
9. {2(1),3,1,2(2)}

Similarly 12 combinations by changing positions of 2(1) and 2(2).so total of 24

  • $\begingroup$ So can one say that if each of the $n$ numbers is at most $K$ then all of the $n!$ arrangements will count? If so it seems the hard part will be about cases where the value of $K$ is less than the greatest of the $n$ numbers, and it would seem an interesting thing to try to count. $\endgroup$
    – coffeemath
    Feb 8 '14 at 15:21
  • $\begingroup$ @coffeemath yeah exactly,i spent my whole day and at last posted it here.When K is less than greatest of n numbers it is really hard but thats the best part of the question $\endgroup$ Feb 8 '14 at 15:30
  • $\begingroup$ @user99323 the combination 3,2,1 count.Because we have to count all perfectcount combinations less than K.and 3,2,1 has perfectcount of 1 so it will be counted $\endgroup$ Feb 8 '14 at 16:09
  • $\begingroup$ okay, i thought it had to be equal to k. my bad. $\endgroup$
    – Akshara
    Feb 8 '14 at 16:11
  • $\begingroup$ @user99323 Hmm.But i think i had explained it in question itself $\endgroup$ Feb 8 '14 at 16:11

To find the orders where $K$ is equal to the highest number in the list, you need to start with a $1$. Then you can have as many $1$'s as you like, but nothing else, before the first $2$. Then you can have as many $1$'s and $2$'s as you like, but nothing else, before the first $3$ and so on. I don't see how to turn this into a nice formula for a general multiset of numbers. For your example $1,2,2,3$, the only orders that have $K=3$ are $1,2,2,3$ and $1,2,3,2$, which you can double if you think the $2$'s are distinct. To get $K=1$ you just need the first element of the list to be the greatest value, so if there are $n_{max}$ of the greatest value and you think the matching numbers are distinct there are $n_{\max}(N-1)!$ orders with $K=1$ The intermediate values are much harder.

  • $\begingroup$ These two were calculated by me too.But thanx for explaining them well.Hope You can solve for intermediate K values too $\endgroup$ Feb 9 '14 at 5:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.