Counting Sequences

Counting the Number of Ways to Arrange Subsequences With Constraints Charles C. Johnson Suppose we are given the integers 1 through n, inclusive, and that these numbers are split into k finite sequences, S1 through Sk of consecutive integers. If each sequence can be placed forwards or backwards (which we’ll denote Sif and Sib , respectively), how many ways f , and no Sib is preceeded can we arrange the sequences such that no Sif is followed by Si+1 b by Si−1 ? We’ll begin by assuming that all sequences are at least two in length. We will now consider a slightly modified, but equivalent, version of the problem. Suppose instead of k sequences, we have k dominoes that are split into two tiles. The first domino has one dot on one half, and two dots on the other. The second domino has two dots on one half, and three on the other. In general, domino i has i dots on one half and i + 1 dots on the other. We will refer to domino i as the pair (i, i + 1) or (i + 1, i) depending on whether the domino is layed down such that there are i dots on the left-hand side (and thus i + 1 dots on the right-hand side), or the right-hand side (i + 1 dots on the left-hand side), respectively. Using this scheme, Sif is represented by (i, i + 1) and Sib is represented by (i + 1, i). We now wish to lay all of the dominoes out in a line, such that (i, i + 1) is not followed by (i + 1, i + 2), nor is preceeded by (i − 1, i) for any i. We’ll let an denote the number of ways to arrange n dominoes like this, and begin by noting that a1 = 2 (there are two ways to place one domino, (1, 2) and (2, 1)). Now, assume we have a valid permutation of n dominoes. How many ways can we place the domino (n + 1, n + 2)? Clearly, there are n + 1 places this domino could be placed (in front of each of the already placed n dominoes, plus one spot at the very end), and for each of these the domino could be forward or backward. However, when placed next to domino n there will be only one way to place (n + 1, n + 2) on one of the sides domino n. If domino n is placed as (n, n + 1) then if domino n + 1 were to follow, it would have to be placed (n + 2, n + 1). Similarly, if we had (n + 1, n), then the domino would have to be placed (n + 1, n + 2) to preceed. From this we conclude there are 2(n + 1) − 1 ways to place domino n + 1, so we can define an as followed. a1 = 2 an+1 = (2n + 1)an

1