# Thread: Find the generating function

1. ## Find the generating function

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.

2. Originally Posted by Severus
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.
The answer is given here as $1 - \left(\sum_{k=0}^{\infty}k!x^k\right)^{-1}$ (but unfortunately without any explanation).

3. Someone who can give me an explanation?