The answer is given here as (but unfortunately without any explanation).
I need some help with this one:
A permutation is indecomposable if it cannot be cut
into two parts so that everything before the cut is smaller than everything
after the cut. For example 3142 is indecomposable, but 2143 is not as you
can cut it after the first two elements. Let f(n) be the number of indecomposable
permutations of length n and set f(0) = 0. Find the ordinary generating
function.