The Number of Times the Placement Algorithm Ends at the Top and Bottom

John Ginsburg1
1Department of Mathematics and Statistics, University of Winnipeg Winnipeg, Manitoba, Canada

Abstract

Let \( n \) and \( q \) be positive integers, with \( n \geq 3 \), and let \( N = nq \). As input, we are to be given an arbitrary ordered \( n \)-sequence \( x_1, x_2, \ldots, x_n \), where \( 1 \leq x_i \leq N \) for all \( i \). We are to be presented with this sequence one entry at a time. As each entry is received, it must be placed into one of the positions \( 1, 2, \ldots, n \), where it must remain. A natural way to do this, in an attempt to sort the input sequence, is as follows. For any integer \( x \in \{1, \ldots, N\} \), we let \( s(x) \) denote the unique integer \( s \) for which \( (s-1)q + 1 \leq x \leq sq \). When we receive the entry \( x_i \), we consider those positions still unoccupied after having placed the previous \( i-1 \) entries, and we place \( x_i \) into the one which is closest to \( s(x_i) \). In the event of a tie for closest, we choose the higher of the two positions. We refer to this procedure as the \({placement\; algorithm}\). Regarding this algorithm, we consider the following question: for how many input sequences will the last two positions filled be positions \( 1 \) and \( n \)? We show that this number is \( (n-1)^{n-3}n^2q^n \).

Keywords: placement algorithm, permutation, sorting, re- currence, convolution, Abel’s binomial theorem