# computing the number of increasing $k$-long subsequences

Let $f$ be a permutation on $n$ letters. I want to count the number of $k$-long increasing subsequences quickly.

First I use divide and conquer to split the problem into finding increasing subsequences in pairs of numbers. The resulting 'tree' has height $\log n$. I'm wondering how I can combine the subproblems in an efficient way. I thought about prefix sums and using mergesort, but I can't see how to effectively implement them.

One idea to save time when combining two subproblems is to compare elements at the end of your increasing subsequences in your first subproblem with the values in your second subproblem.

My goal is to get to $O(kn\log n)$ time but this doesn't do it.

-
This seems like more of a question for cstheory.stackexchange.com. – Qiaochu Yuan Nov 25 '10 at 17:03
actually stackoverflow might help too. – user1709 Nov 25 '10 at 21:41
k-long sequences do not have to be contiguous? – user4143 Apr 26 '11 at 5:52
– r.e.s. Dec 28 '11 at 3:17