The initial involution patterns of permutations

Abstract

For a permutation pi = pi(1)pi(2)... pi(n) is an element of S-n and a positive integer i <= n, we can view pi(1)pi(2)... pi(i) as an element of S-i by order-preserving relabeling. The j-set of pi is the set of i's such that pi(1)pi(2)... pi(i) is an involution in S-i. We prove a characterization theorem for j-sets, give a generating function for the number of different j-sets of permutations in S-n. We also compute the numbers of permutations in S-n with a given j-set and prove some properties of them.