# Number of ascending subsequences in permutation

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.

-
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
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

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.

-
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