Counting Stabilized-Interval-Free Permutations
David Callan · 2004
A permutation on [n] = {1, 2,..., n} is stabilized-interval-free (SIF) if it does not stabilize any proper subinterval of [n]. For example, ( 1 2 3 4 5 6 6 1 5 3 4 2), or (3, 5, 4)(1, 6, 2) in cycle notation, or 6 1 5 3 4 2 in one-line notation, fails to be SIF because it stabilizes the interval [3, 5] = {3, 4, 5}. On the other hand, the empty permutation is SIF, as is any cycle, and every SIF permutation on [n] is fixed-point-free for n ≥ 2. Let an denote the number of SIF permutations on [n] and A(x) = ∑ n≥0 anxn their generating function. The first objective of this paper is to show that [xn−1]A(x) n = n! and hence that the number of SIF permutations on [n] is given by A075834. This generating function identity amounts to the existence of a decomposition of an arbitrary permutation into a list of SIF permutations. The second objective is to obtain a recurrence relation that permits efficient computation of an: n−2