Counting Stabilized-Interval-Free Permutations
A stabilized-interval-free (SIF) permutation on [n]={1,2,...,n} is one that
does not stabilize any proper subinterval of [n]. By presenting a
decomposition of an arbitrary permutation into a list of SIF permutations,
we show that the generating function A(x) for SIF permutations satisfies
the defining property: [x^(n-1)] A(x)^n = n! . We also give an efficient
recurrence for counting SIF permutations.
