Journal of Integer Sequences, Vol. 7 (2004), Article 04.1.8

Counting Stabilized-Interval-Free Permutations

David Callan
Department of Statistics
University of Wisconsin-Madison
1210 W. Dayton St.
Madison, WI 53706-1693
USA

Abstract: 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.

(Concerned with sequences A000142 A003319 and A075834 .)

Received September 25 2003; revised version received March 15 2004. Published in Journal of Integer Sequences March 15 2004.