Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

With given permutation of $1,\ldots,n$ for example (in one-line notation): 3 5 1 2 4 6.

How to find amount of ascending subsequences of length 3 in the second row of the permutation ?

There's $n!/k!(n-k)!$ of subsequences of length $k$ for the identity permutation 1 2 3 4 5 6$\cdots$n.

How to deal with this problem ?

Thanks.

share|improve this question
    
When you write 3 5 1 2 4 6, do you mean the permutation of $\{1,\ldots,6\}$ that sends 1 to 3, 2 to 5, 3 to 1, 4 to 2, 5 to 4, and 6 to 6? Or do you mean the cyclic permutation that sends 3 to 5, 5 to 1, 1 to 2, 2 to 4, 4 to 6, and 6 to 3? I am guessing it's the former, but better to make sure... –  Arturo Magidin May 3 '11 at 16:19
    
yes first thing. f(1)=3 f(2)=5 f(3)=1 and so on –  Chris May 3 '11 at 16:37
    
Just so I know I'm understanding this, nC3 is the ceiling on this value, correct? And you are looking at k=3, right? –  a little don May 3 '11 at 16:50
    
yes k=3 for any kind of permutation –  Chris May 3 '11 at 16:55
1  
Since the answer could be as big as $Cn^3$, I doubt there's a way to count them quickly. –  Gerry Myerson May 4 '11 at 1:58

1 Answer 1

up vote 2 down vote accepted

It can be done in O(n log n) time. Assume for every index that it's your mid element in subsequence.

Now having x smaller elements than your mid elements and y greater elements than your mid element you can make max(x,y) subsequences with selected mid point.

It can be also easily programmed.

Simply use segment tree or BIT.

for mid element m you want to check value of x:

-they are in range $<0;m-1>$

Value of y is:

$<0;n-1> - <0;m-1>$ where n is number of elements.

share|improve this answer
    
Good approach, but it seems larger than $O(n \log n)$. For element $i$ you have $i-1$ before it and $n-i$ after it. You have to determine how many of the $i-1$ are less than element $i$ and how many of the $n-i$ are greater. Seems like those take $i$ and $n-i$ tries respectively, and we do this once for each element, so we are $O(n^2)$ –  Ross Millikan Oct 26 '11 at 13:43
    
Yes, you are right, but with segment tree or binary indexed tree we can easily have answer in $O(log n)$ time for each range. So overall complexity is $O(n log n)$. –  Martin Blu Oct 26 '11 at 14:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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