(Originally posted [on Math.SE](https://math.stackexchange.com/questions/11852/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.

One approach is to first use divide and conquer to split the problem into finding increasing subsequences in pairs of numbers. The resulting 'tree' then has height $\log n$. I'm wondering how the subproblems could be combined 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 the increasing subsequences in the first subproblem with values in the second subproblem.

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