Counting length-k increasing subsequences in a permutation (Originally posted on Math.SE.)

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.
According to Kim, finding one such sequence is equivalent to finding a maximum independent set in a permutation graph and can be done in $O(n\log n)$ time. The running time you're looking for suggests you already knew about that, but if not, looking at citing papers might help.

Update: actually, the complement of a permutation graph is also a permutation graph, and the complement of an independent set is a clique, so unless I'm missing something, maximising the number of increasing sequences of length $k$ in your permutation should be equivalent to partitioning a permutation graph into as many $K_k$'s as possible. Surely this has been studied, at least for triangles...