# Find the generating function

• Mar 8th 2008, 09:29 AM
Severus
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.
• Mar 8th 2008, 10:18 AM
Opalg
Quote:

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).
• Mar 11th 2008, 12:13 PM
Severus
Someone who can give me an explanation?