I want to prove the following. Let $P$ be a permutation of $n$ numbers from $1$ to $n$. Let $L$ be the length of longest decreasing subsequence. Show that $P$ can be covered by $L$ increasing subsequences.
Could you give me any hints how to prove this?
Hint: classify all numbers in the permutation by the length of the longest decreasing subsequence (not necessarily unique) of which that element in the final term. By hypothesis there are $L$ classes. Show that within each class, the numbers are increasing; this amounts to showing that a number cannot be less than a previous number in the same class, and that is fairly obvious.