Séminaire Lotharingien de Combinatoire 54A (2006), Article B54Ab

COMBINATORICS OF PATIENCE SORTING PILES*

ALEXANDER BURSTEIN^{†} AND ISAIAH LANKHAM^{‡}

Abstract. Despite having been introduced in 1962 by C.L. Mallows, the combinatorial algorithm Patience Sorting is only now beginning to receive significant attention due to such recent deep results as the Baik-Deift-Johansson Theorem that connect it to fields including Probabilistic Combinatorics and Random Matrix Theory.

The aim of this work is to develop some of the more basic combinatorics of the Patience Sorting Algorithm. In particular, we exploit the similarities between Patience Sorting and the Schensted Insertion Algorithm in order to do things that include defining an analog of the Knuth relations and extending Patience Sorting to a bijection between permutations and certain pairs of set partitions. As an application of these constructions we characterize and enumerate the set S_{n}(3-¯1-42) of permutations that avoid the generalized permutation pattern 2-31 unless it is part of the generalized pattern 3-1-42.

Résumé. En dépit de l’introduction en 1962 par C.L. Mallows, l’algorithme combinatoire Patience Sorting commence seulement maintenant à susciter l’attention significative dû à des résultats profonds récents, tels que le théorème de Baik-Deift-Johansson, qui le relient à la combinatoire probabiliste et à la théorie des matrices aléatoires.

On développe une partie plus fondamentale de la combinatoire de l’algorithme de Patience Sorting. En particulier, on utilise les similarités entre Patience Sorting et la correspondance de Schensted pour définir un analogue des relations de Knuth et pour généraliser Patience Sorting à une bijection entre les permutations et certaines paires de partitions d’ensemble. Comme application de ces constructions on caractérise et énumère l’ensemble S_{n}(3-¯1-42) des permutations qui évitent le motif de permutation généralisé 2-31 à moins qu’il soit partie du motif généralisé 3-1-42.

Key words and phrases. Patience sorting, set partitions, Bell numbers, generalized permutation patterns, left-to-right minima subsequences, basic subsequences, shadow diagrams.

* This material is based in part upon work supported by the National Science Foundation under Grant No. DMS-0502858.

† Department of Mathematics, Iowa State University, Ames, IA 50011-2064, USA. (burstein@math.iastate.edu) Research supported in part by the U.S. NSA Young Investigator Grant H98230-06-1-0037.

‡ Department of Mathematics, University of California-Davis, Davis, CA 95616-8633, USA. (issy@math.ucdavis.edu) Research supported in part by the U.S. NSF Grants DMS-0135345 and DMS-0304414.

1. Introduction

The term Patience Sorting was introduced in 1962 by C. L. Mallows [15, 16] as the name of a card sorting algorithm invented by A. S. C. Ross. This algorithm works by first partitioning a shuffled deck of cards (which throughout this paper we take to be a permutation σ ∈ 𝔖_{n}) into sorted subsequences called piles using what Mallows referred to as a “patience sorting procedure”:

Algorithm 1.1 (Mallows’ Patience Sorting Procedure). Given a shuffled deck of cards σ = c_{1}c_{2} ⋯ c_{n}, inductively build the set of piles R = R(σ) = {r_{1}, r_{2}, …, r_{m}} as follows:

• Place the first card c_{1} from the deck into a pile r_{1} by itself.

• For each remaining card c_{i} (i = 2, …, n), consider the cards d_{1}, d_{2}, …, d_{k} atop

the piles r_{1}, r_{2}, …, r_{k} that have already been formed.

– If c_{i} > max{d_{1}, d_{2}, …, d_{k}}, then put c_{i} into a new right-most pile r_{k+1} by itself.

– Otherwise, find the left-most card d_{j} that is larger than c_{i} and put the card c_{i} atop pile r_{j}.

We call the collection of piles R(σ) the pile configuration associated to the deck of cards σ ∈ 𝔖_{n} and illustrate their formation via an extended version of Algorithm 1.1 in Section 3.1 below.

Since each card c_{i} is either larger than the top card of every pile or is placed on top of the left-most top card d_{j} larger than it, the cards d_{1}, d_{2}, …, d_{k} atop the piles will be in increasing order from left to right at each step of the algorithm. Thus, Algorithm 1.1 resembles repeated application of the Schensted Insertion Algorithm (as discussed in [1]) for interposing a value into the increasing sequence d_{1}, d_{2}, …, d_{k} as if it were the top row of a Young tableau. The distinction is that cards remain in place and have other cards placed on top of them instead of being actively “bumped” from the row so that the Schensted Insertion Algorithm can then be recursively applied to the “bumped” value and the next lower row in the Young tableau. In this sense, Patience Sorting can be viewed as a non-recursive analog of the remarkable Robinson-Schensted-Knuth (or RSK) Algorithm due to G. Robinson [19] for permutations in 1938, C. Schensted [21] for words in 1961, and D. Knuth [12] for so-called ℕ-matrices in 1970. (See Fulton [10] for the appropriate definitions and for a detailed account of the differences between these algorithms.)

Recall that the RSK Algorithm bijectively associates an ordered pair of standard Young tableaux (P (σ), Q(σ)) to each permutation σ = σ_{1}σ_{2} ⋯ σ_{n} ∈ 𝔖_{n} by first building a so-called “insertion tableau” P (σ) through repeated Schensted Insertion of the components σ_{1}, σ_{2}, …, σ_{n} into an initially empty tableau. It also simultaneously constructs the “recording tableau” Q(σ) by literally recording how P (σ) is formed. These tableaux have the same shape (a partition λ of n, denoted λ ⊢ n), and this correspondence has many interesting properties. E.g., RSK applied to a permutation is symmetric in the sense that if σ ∈ 𝔖_{n} corresponds to the ordered pair of tableaux (P (σ), Q(σ)), then (Q(σ), P (σ)) corresponds to the inverse permutation σ^{−1}. As a result, there is a bijection between the set of involutions ℑ_{n} ⊂ 𝔖_{n} and the set 𝔗_{n} of all standard Young tableaux with entries 1, 2, …, n. (This is the famous Schützenberger symmetry property first proven in [22].)

In this paper we develop a bijective extension of Algorithm 1.1 and then study analogues for such properties of RSK. To facilitate this, we first characterize in Section 2 when two permutations have the same pile configurations under Algorithm 1.1. This yields an equivalence relation ∼^{P S} on 𝔖_{n} that is analogous to the Knuth relation 213 ∼^{RSK} 231. (Recall that the Knuth relations describe when two permutations have the same “insertion tableau” P under RSK; see Sagan [20].)

In Section 3 we then explicitly describe a bijection between 𝔖_{n} and certain pairs of pile configurations having the same shape (a composition γ of n, denoted γ ⊧ n). Since there are many more possible pile configurations than standard Young tableaux (the former are enumerated by Bell numbers; see Theorem 4.1), it is necessary to specify which pairs are possible; this turns out to involve the same patterns as the other Knuth relation 312 ∼^{RSK} 132 (see Definition 3.8). Moreover, this bijection shares the same Schützenberger symmetry property as RSK, and so we can immediately characterize a certain collection of pile configurations that are in bijection with the set of involutions ℑ_{n} (as well as with the set 𝔗_{n} of standard Young tableaux).

In Section 4 we conclude by using the equivalence relation ∼^{P S} to characterize and enumerate the set S_{n}(3-¯1-42) of permutations avoiding the barred (generalized) permutation pattern 3-¯1-42. Such permutations avoid the pattern 2-31 unless it is contained in a 3-1-42 pattern. (See Sections 2.2 and 4 for the appropriate definitions.)

Another interesting property of RSK is that, given σ ∈ 𝔖_{n}, the number of boxes in the top row of the “insertion tableau” P (σ) is exactly the length of the longest increasing subsequence in σ. (This was first proven by Schensted [21] but is now a special case of Greene’s Theorem [11]). Due to the similarity between the Schensted Insertion Algorithm and Algorithm 1.1, it is clear that the cards atop the piles when Patience Sorting terminates will be exactly the elements in the top row of P (σ). Thus, the number of piles formed under Patience Sorting is also equal to the length of the longest increasing subsequence in σ, and so one can apply the recent but now highly celebrated Baik-Deift-Johansson Theorem [3] in order to describe the asymptotic distribution for the number of piles (up to rescaling). Due to this deep connection between Patience Sorting and Probabilistic Combinatorics, it has been suggested (see, e.g., [13], [14] and [18]; cf. [7]) that studying generalizations of Patience Sorting might be the key to tackling certain open problems that can be viewed from the standpoint of Random Matrix Theory—the most notable being the Riemann Hypothesis.

At the same time, there is a lot more to Patience Sorting than just resembling the RSK Algorithm for permutations. E.g., after applying Algorithm 1.1 to a deck of cards, it is easy to recollect each card in ascending order from amongst the current top cards of the piles (and thus complete A. S. C. Ross’ card sorting algorithm). While this is not necessarily the fastest sorting algorithm one can apply to a deck of cards, the patience in Patience Sorting is not intended to describe a prerequisite for its use. Instead it refers to how pile formation in Algorithm 1.1 resembles the way in which one places cards into piles when playing the popular single-person card game Klondike Solitaire, which is often called Patience in the UK. This is more than a coincidence, though, as Algorithm 1.1 also happens to be an optimal strategy (in the sense of forming as few piles as possible; see [1] for a proof) when playing an idealized model of Klondike Solitaire known as Floyd’s Game:

Game 1.2 (Floyd’s Game). Given a shuffled deck of cards c_{1}, c_{2}, …, c_{n},

• Place the first card c_{1} from the deck into a pile r_{1} by itself.

• Then, for each card c_{i} (i = 2, …, n), either – put c_{i} into a new pile by itself or

– play c_{i} on top of any pile whose current top card is larger than c_{i}.

• The object of the game is to end with as few piles as possible.

In other words, the cards are played one at a time according to the order they appear in the deck so that piles are created in much the same way they are formed under Patience Sorting. According to [1], Floyd’s Game was developed independently of Mallow’s work and originated in unpublished correspondence between computer scientists Bob Floyd and Donald Knuth during 1964.

Note that unlike Klondike Solitaire, there is a known strategy (Algorithm 1.1) for Floyd’s Game under which one will always win. In fact, Klondike Solitaire—though so popular that it has come pre-installed on the vast majority of personal computers shipped since 1989—is very poorly understood mathematically. (Recent progress, however, has been made in developing an optimal strategy for a version called thoughtful solitaire [26].) As such, Persi Diaconis ([1] and private communication with the second author) has suggested that a deeper understanding of Patience Sorting and its generalization would undoubtedly help in developing a better mathematical model for analyzing Klondike Solitaire.

2. Pile Configurations Coming from Patience Sorting

2.1. Pile Configurations, Shadow Diagrams, and Reverse Patience Words. We begin by explicitly characterizing the pile configurations that result from applying Patience Sorting (Algorithm 1.1) to a permutation:

Lemma 2.1. Let σ ∈ 𝔖_{n} be a permutation and R(σ) = {r_{1}, r_{2}, …, r_{k}} be the pile configuration associated to σ under Algorithm 1.1. Then R(σ) is a partition of the set [n] = {1, 2, …, n} such that denoting r_{j} = {r_{j1} > r_{j2} > ⋯ > r_{js_{j}}},

r_{js_{j}} < r_{is_{i}} if j < i  (2.1)

Moreover, for every set partition T = {t_{1}, t_{2}, …, t_{k}} satisfying Equation (2.1), there is a permutation τ ∈ 𝔖_{n} such that R(τ) = T.

Proof. Given a pile configuration R(σ) = {r_{1}, r_{2}, …, r_{k}}, suppose that for some pair of indices i, j ∈ [k] we have j < i but r_{js_{j}} > r_{is_{i}}. Then r_{is_{i}} was put atop pile r_{i} when pile r_{j} had top card d_{j} ≥ r_{js_{j}} so that d_{j} > r_{is_{i}}. However, it then follows that, under Algorithm 1.1, the card r_{is_{i}} would actually then have been placed atop either pile r_{j} or a pile to the left of r_{j} instead of atop pile r_{i}. The resulting contradiction implies that r_{js_{j}} < r_{is_{i}} for each j < i.

Conversely, let T = {t_{1}, t_{2}, …, t_{k}} be any set partition of [n] with t_{j} = {t_{j1} > t_{j2} > ⋯ > t_{js_{j}}} for every j ∈ [k] and t_{js_{j}} < t_{is_{i}} for all pairs j < i. Consider then the permutation

τ = t_{11}t_{12} … t_{1s_{1}} t_{21}t_{22} … t_{2s_{2}} … t_{k1}t_{k2} … t_{ks_{k}} ∈ 𝔖_{n}.

We show that R(τ) = T: Given any j ∈ [k] and any i > j, each m ∈ [s_{i}] satisfies t_{js_{j}} < t_{is_{i}} < t_{im}, and so no value to the right of t_{js_{j}} in τ will be placed on top of t_{js_{j}} in R(τ). Since t_{11} < t_{12} < ⋯ < t_{1s_{1}}, all these entries must be placed in the leftmost (a.k.a. first) pile r_{1} ∈ R(τ), so the first pile of R(τ) is r_{1} = t_{1}. Now suppose that the entries t_{1} through t_{js_{j}} of τ have been placed in piles t_{1}, t_{2}, …, t_{j}. Then the entries t_{j+1,1} > t_{j+1,2} > ⋯ > t_{j+1,s_{j+1}} cannot be placed atop any t_{is_{i}} for i ≤ j, so we must form at least one new pile, say t_{j+1}. However, since these entries occur in decreasing order in τ, these cards will then all be placed in the (j + 1)^{st} pile t_{j+1}. Moreover, no entry to the right of t_{j+1,s_{j+1}} can be placed in pile t_{j+1}, so the (j + 1)^{st} pile of R(τ) is r_{j+1} = t_{j+1}. Therefore, we obtain R(σ) = T by induction. □

We will often express a pile configuration R with its constituent piles r_{1}, r_{2}, …, r_{k} written vertically and bottom-justified with respect to the largest value r_{j1} in each pile r_{j}. This motivates the following definition (which reverses the so-called “far-eastern reading”):

Definition 2.2. The reverse patience word RP W (R) for a pile configuration R is the permutation formed by concatenating the piles r_{1}, r_{2}, …, r_{k} together with each pile r_{j} written in decreasing order (i.e., read from bottom to top in order from left to right). In the notation of Lemma 2.1,

RP W (R) = r_{11}r_{12} … r_{1s_{1}} r_{21}r_{22} … r_{2s_{2}} … r_{k1}r_{k2} … r_{ks_{k}}.

Example 2.3. The pile configuration R = {{6 > 4 > 1}, {5 > 2}, {8 > 7 > 3}} is represented by the piles

1 3 4 2 7 6 5 8

02468 _{0 1 2 3 4 5 6 7 8}

S(2, 4)

•

(a) The Shadow S_{NE}(2, 4).

02468 _{0 1 2 3 4 5 6 7 8} •••••••• (b) Shadowline L_{1}(64518723). 02468 _{0 1 2 3 4 5 6 7 8} •••••••• (c) Shadowline L_{2}(64518723).
02468 _{0 1 2 3 4 5 6 7 8} ••••••••

(d) Shadowline L_{3}(64518723).

Figure 2.1. Examples of Northeast Shadow and Shadowline Constructions

and has the reverse patience word RP W (R) = 64152873. Moreover, note that as in the proof of Lemma 2.1, R(RP W (R)) = R(64152873) = R.

The following Lemma should now be clear from the above definitions and example:

Lemma 2.4. Given a permutation σ ∈ 𝔖_{n}, R(RP W (R(σ))) = R(σ).

Proof. From the proof of Lemma 2.1, we have that if τ = RP W (T), where T is any set partition of [n] satisfying condition (2.1), then T = R(τ). Thus, R(RP W (T)) = T for any partition T of [n] satisfying (2.1), in particular for any T = R(σ) where σ ∈ 𝔖_{n}. □

At the same time, it is also clear that in general there will be many permutations σ, τ ∈ 𝔖_{n} for which R(σ) = R(τ). In Section 2.2 below we characterize when two permutations have the same pile configuration, and we will denote this equivalence relation by σ ∼^{P S} τ. Moreover, we will also see that the reverse patience word RP W (R(σ)) is the most natural representative for the equivalence class generated by a given permutation σ.

We close this section by giving an alternate characterization for pile configurations in terms of the shadow diagram construction that Viennot [24] introduced in the context of studying the RSK Algorithm for permutations.

Definition 2.5. Given a lattice point (m, n) ∈ ℤ^{2}, we define the (northeast) shadow of (m, n) to be the quarter space S(m, n) = {(x, y) ∈ ℝ^{2} | x ≥ m, y ≥ n}.

See Figure 2.1(a) for an example of a point’s shadow.

The most important use of shadows is in building shadowlines:

Definition 2.6. Given lattice points (m_{1}, n_{1}), (m_{2}, n_{2}), …, (m_{k}, n_{k}) ∈ ℤ^{2}, we define their (northeast) shadowline to be the boundary of the region formed from the union of the shadows S(m_{1}, n_{1}), S(m_{2}, n_{2}), …, S(m_{k}, n_{k}).

In particular, we wish to associate to each permutation a certain collection of shadowlines (as illustrated in Figure 2.1(b)–(d)):

Definition 2.7. Given a permutation σ = σ_{1}σ_{2} ⋯ σ_{n} ∈ 𝔖_{n}, the (northeast) shadow diagram D(σ) of σ consists of the shadowlines L_{1}(σ), L_{2}(σ), …, L_{k}(σ) formed as follows:

• L_{1}(σ) is the shadowline for the lattice points {(1, σ_{1}), (2, σ_{2}), …, (n, σ_{n})}.

• While at least one of the points (1, σ_{1}), (2, σ_{2}), …, (n, σ_{n}) is not contained in the shadowlines L_{1}(σ), L_{2}(σ), …, L_{j}(σ), define L_{j+1}(σ) to be the shadowline for the points

{(i, σ_{i}) | (i, σ_{i}) ∉ ⋃_{k=1}^{j} L_{k}(σ)}.

In other words, we define the shadow diagram D(σ) = {L_{1}(σ), L_{2}(σ), …, L_{k}(σ)} inductively with L_{1}(σ) the shadowline for the diagram {(1, σ_{1}), (2, σ_{2}), …, (n, σ_{n})} of the permutation σ ∈ 𝔖_{n}. Then we ignore the points whose shadows were actually used in building L_{1}(σ) and define L_{2}(σ) to be the shadowline of the resulting subset of the permutation diagram. We then build L_{3}(σ) as the shadowline for the points not yet used in constructing both L_{1}(σ) and L_{2}(σ), and this process continues until all points in the permutation diagram are exhausted.

One of the most basic properties of the shadow diagram for a permutation σ is that it encodes the top row of the insertion tableau P (σ) (resp. recording tableau Q(σ)) as the smallest ordinates (resp. smallest abscissae) of all points belonging to the constituent shadowlines L_{1}(σ), L_{2}(σ), …, L_{k}(σ). (A proof of this can be found in Sagan [20].) In particular, this means that if σ has pile configuration R(σ) = {r_{1}, r_{2}, …, r_{m}}, then m = k since the number of piles is equal to the length of the top row of P (σ) (as both are the length of the longest increasing subsequence of σ). We can say even more about the relationship between D(σ) and R(σ) when both are viewed in terms of left-to-right minima subsequences (a.k.a. basic subsequences or records):

Definition 2.8. Let π = π_{1}π_{2} ⋯ π_{l} be a partial permutation on [n] = {1, 2, …, n}. Then the left-to-right minima subsequence of π consists of those components π_{j} of π such that π_{j} = min{π_{i} | 1 ≤ i ≤ j}.

We then inductively define the left-to-right minima subsequences s_{1}, s_{2}, …, s_{k} of a permutation σ by taking s_{1} to be the left-to-right minima subsequence for σ itself and then each subsequent subsequence s_{i} to be the left-to-right minima subsequence for the partial permutation obtained by removing the elements of s_{1}, s_{2}, …, s_{i−1} from σ. The subsequence s_{j} is called the j^{th} left-to-right minima subsequence of σ.

Lemma 2.9. Suppose σ ∈ 𝔖_{n} has shadow diagram D(σ) = {L_{1}(σ), L_{2}(σ), …, L_{k}(σ)}. Then the ordinates of the southwest corners of L_{j} are exactly the cards in the j^{th} pile

0123 _{0 1 2 3} • • • ∼^{P S} 0123 _{0 1 2 3} • • •

(a) “Stretching” shadowlines effects

231 ∼^{P S} 213. Thus, ˜231 = {231, 213}.

01234 _{0 1 2 3 4} • • • •

(b) No “stretching” can interchange “4” and “2”.

Figure 2.2. Examples of patience sorting equivalence and non-equivalence

r_{j} ∈ R(σ) formed by applying Patience Sorting (Algorithm 1.1) to σ. In other words, the j^{th} pile r_{j} contains exactly the elements of the j^{th} left-to-right minima subsequence of σ.

Proof. The i^{th} basic subsequence s_{i} of σ consists of those elements σ_{t} that appear at the end of an increasing subsequence of length i but not at the end of an increasing subsequence of length i + 1. Thus, since each element added to a pile must be smaller than all other elements already in the pile, s_{1} = r_{1}. It then follows similarly by induction that s_{i} = r_{i} for i = 2, …, k.

The proof that the ordinates of the southwest corners of the shadowlines L_{i} are also exactly the elements of the left-to-right minima subsequences s_{i} is similar. □

Lemma 2.9 gives a particularly nice correspondence between the piles formed under Patience Sorting and the shadowlines that constitute the shadow diagram of a permutation. In particular, we have that forming RP W (R(σ)) essentially amounts to sorting σ ∈ 𝔖_{n} into its left-to-right minima subsequences.

We will rely heavily upon this correspondence in the sections below.

2.2. Permutations Having Equivalent Pile Configurations. In this section we characterize the following equivalence relation:

Definition 2.10. Two permutations σ, τ ∈ 𝔖_{n} are said to be patience sorting equivalent, written σ ∼^{P S} τ, if they have the same pile configuration R(σ) = R(τ) under Algorithm 1.1. We denote the equivalence class generated by σ as σ̃.

By Lemma 2.9 in Section 2.1 above, the pile configurations R(σ) and R(τ) correspond to certain shadow diagrams. Thus, it should be intuitively clear that preserving a given pile configuration is equivalent to preserving the ordinates for the southwest corners of the shadowlines. In particular, this means that we are limited to horizontally “stretching” shadowlines up to the point of not allowing them to cross as is illustrated in Figure 2.2 and the following examples.

Example 2.11. The only non-singleton patience sorting equivalence class for 𝔖_{3} consists of ˜231 = {231, 213}. We illustrate 231 ∼^{P S} 213 in Figure 2.2(a).

Notice that the actual values of the elements interchanged in Example 2.11 are immaterial so long as they have the same relative magnitudes as the literal values in the word 231. (I.e., they have to be order-isomorphic.) Moreover, it should also be clear that any value greater than the element playing the role of “1” can be inserted between the elements playing the roles of “2” and “3” without affecting the ability to interchange the “1” and “3” elements. Problems with this interchange only start to arise when a value smaller than the element playing the role of “1” is inserted between the elements playing the roles of “2” and “3”. We can formally describe this idea using the language of generalized permutation patterns (as was recently defined in [2]; cf. [4]).

Definition 2.12. Let σ = σ_{1}σ_{2} ⋯ σ_{n} ∈ 𝔖_{n} and τ ∈ 𝔖_{m} for m ≤ n. Then we say that σ contains the (classical) pattern τ if there exists a subsequence σ_{i_{1}}, σ_{i_{2}}, …, σ_{i_{m}} of σ (meaning i_{1} < i_{2} < ⋯ < i_{m}) such that the word σ_{i_{1}}σ_{i_{2}} … σ_{i_{m}} is order-isomorphic to τ.

If σ does not contain τ, then we say that σ avoids the pattern τ, and we denote by S_{n}(τ) the subset of the symmetric group 𝔖_{n} that avoids τ.

Note that the elements in the subsequence σ_{i_{1}}, σ_{i_{2}}, …, σ_{i_{m}} are not required to be contiguous in σ. In a generalized pattern one assumes that every element in the subsequence must be taken contiguously unless a dash is inserted in the pattern τ between elements that are not required to be contiguous in σ. (A generalized patterns with no dashes is sometimes called a segment or a consecutive pattern.)

Example 2.13.

(1) Notice that 2431 contains exactly one instance of a 2-31 pattern as the bold underlined subsequence \underline{2}4\underline{3}\underline{1}. (Conversely, \underline{2}\underline{4}3\underline{1} is an instance of 23-1 but not of 2-31.) Moreover, it is clear that 2431 ∼^{P S} 2413.

(2) Even though 3142 contains a 2-31 pattern (as the subsequence \underline{3}1\underline{4}\underline{2}), we cannot interchange “4” and “2”, and so R(3142) ≠ R(3124). As illustrated in Figure 2.2(b), this is because “4” and “2” are on the same shadowline.

We can now state our main result on patience sorting equivalence:

Theorem 2.14. Let σ, τ ∈ 𝔖_{n}. Then σ and τ have the same pile configuration R(σ) = R(τ) under Algorithm 1.1 (so that σ ∼^{P S} τ) if and only if there exists a sequence of 2-31 to 2-13 interchanges (with no 2-31 pattern contained in a 3-1-42 pattern) that transform σ into τ.

In other words, ∼^{P S} is the transitive closure of such interchanges.

Proof. By Lemma 2.9 it suffices to show that 2-31 to 2-13 interchanges (with no 2-31 pattern contained in a 3-1-42 pattern), preserve the left-to-right minima subsequences s_{1}, s_{2}, …, s_{k} of σ. This amounts to showing by induction that such interchanges suffice to transform σ into RP W (R(σ)) via the sequence of pattern interchanges

σ = σ^{(0)} ⇝ σ^{(1)} ⇝ σ^{(2)} ⇝ ⋯ ⇝ σ^{(ℓ)} = RP W (R(σ))

where each σ^{(i)} ∼^{P S} σ^{(i+1)}.

Let (a, b, c) be a subsequence of σ_{i} that is an instance of 2-31 not contained in an instance of 3-1-42. Then c < a < b, and there is no d between a and b in σ such that d < c. Clearly, we do not lose any increasing subsequences of σ^{(i)} by interchanging b and c. Moreover, the only new increasing subsequences σ^{(i+1)} created by this interchange are those that end with the subsequence (c, b). If such an increasing subsequence contains other terms, say d_{1} < d_{2} < ⋯ < d_{m} < c < b, then d_{m} must be to the left of a in σ. But then σ^{(i)} contains an increasing sequence d_{1} < d_{2} < ⋯ < d_{m} < a < b with the same number of terms. Hence, interchanging b and c does not create any longer increasing subsequences with the same final term,

so σ^{(i)} ∼^{P S} σ^{(i+1)}.

Let r_{11} > r_{12} > ⋯ > r_{1s_{1}} be the subsequence of left-to-right minima of σ; from the proof of Lemma 2.9, these are the entries that form the leftmost pile r_{1} of R(σ). Now suppose that, for some j < s_{1}, there is an entry between r_{1j} and r_{1,j+1}, and let b be the entry immediately preceding r_{1,j+1}. Then b > r_{1j} so that (r_{1j}, b, r_{1,j+1}) is an instance of 2-31. On the other hand, r_{1,j+1} is the leftmost entry of σ that is less than r_{1j}, so no entry d < r_{1,j+1} may occur between r_{1j} and b. Hence, (r_{1j}, b, r_{1,j+1}) is not an instance of 3-1-42, and so interchanging r_{1,j+1} and b will not change the pile configuration. We may repeat this until there are no entries between consecutive left-to-right minima of σ. We thus obtain σ′ = r_{11}r_{12} … r_{1s_{1}}σ′′, where σ′′ is obtained by deleting r_{11}, r_{12}, …, r_{1s_{1}} from σ. Since no instance of 2-31 may start with r_{1s_{1}} and since any instance (r_{1i}, a, b) of 2-31 is part of an instance (r_{1i}, r_{1s_{1}}, a, b) of 3-1-42, no further interchanges will involve any r_{1i}. Thus, by induction, we can now apply the same procedure to σ′′, etc., to ultimately obtain r_{11}r_{12} … r_{1s_{1}} r_{21}r_{22} … r_{2s_{2}} … r_{k1}r_{k2} … r_{ks_{k}} = RP W (R(σ)). □

Remark 2.15. It follows from Theorem 2.14 that Examples 2.11 and 2.13(2) sufficiently characterize when two permutations yield the same pile configurations under Patience Sorting. However, it is worth pointing out that these examples also begin to illustrate how one can build an infinite sequence of generalized permutation patterns (all of them containing either 2-13 or 2-31) with the following property: an interchange of the pattern 2-13 with the pattern 2-31 is allowed within an odd-length pattern in this sequence unless the elements used to form the odd-length pattern can also be used as part of a longer even-length pattern in this sequence.

Example 2.16. Even though the permutation 34152 contains a 3-1-42 pattern in the suffix “4152”, one can still directly interchange the “5” and the “2” because of the “3” prefix (or via the following sequence of interchanges: 34152 ⇝ 31452 ⇝ 31425 ⇝ 34125).

3. Bijectively Extending Patience Sorting to “Stable Pairs” of Pile Configurations

3.1. The Extended Patience Sorting Algorithm. Recall from Section 1 that Patience Sorting (Algorithm 1.1) can be viewed as an iterated, non-recursive form of the Schensted Insertion Algorithm for inserting a value into the top row of a Young tableau. In this section we extend the Patience Sorting construction so that it becomes a full non-recursive analog of the RSK Algorithm for permutations. In particular, we mimic the RSK recording tableau construction so that “recording piles” are formed while assembling the usual pile configuration under Patience Sorting (which by analogy to RSK we will similarly now call “insertion piles”).

Algorithm 3.1 (Extended Patience Sorting Algorithm). Given a shuffled deck of cards σ = c_{1}c_{2} ⋯ c_{n}, inductively build insertion piles R = R(σ) = {r_{1}, r_{2}, …, r_{m}} and recording piles S = S(σ) = {s_{1}, s_{2}, …, s_{m}} as follows:

• Place the first card c_{1} from the deck into a pile r_{1} by itself and set s_{1} = {1}.

• For each remaining card c_{i} (i = 2, …, n), consider the cards d_{1}, d_{2}, …, d_{k} atop the piles r_{1}, r_{2}, …, r_{k} that have already been formed.

– If c_{i} > max{d_{1}, d_{2}, …, d_{k}}, then put c_{i} into a new pile r_{k+1} by itself and set s_{k+1} = {i}.

– Otherwise, find the left-most card d_{j} that is larger than c_{i} and put the card c_{i} atop pile r_{j} while simultaneously putting i at the bottom of pile s_{j}.

We call the pile configuration pairs that result from Algorithm 3.1 stable pairs and give a characterization for them in Section 3.2 below. Note that the pile configurations that comprise a resulting stable pair must have the same “shape”, which we define as follows:

Definition 3.2. Given a pile configuration R = {r_{1}, r_{2}, …, r_{m}} on n cards, we call the composition γ = (|r_{1}|, |r_{2}|, …, |r_{m}|) of n the shape of R and denote this by sh(R) = γ ⊧ n.

Example 3.3. Let σ = 64518723 ∈ 𝔖_{8}. Then according to Algorithm 3.1 we simultaneously form the following pile configurations with shape sh(R(σ)) = sh(S(σ)) = (3, 2, 3) ⊧ 8.

insertion piles recording piles  insertion piles recording piles

Form a new pile with 6: 6  1  Then play the 4 on it: {4 \atop 6}  {1 \atop 2}

Form a new pile with 5: 4 6 5  1 2 3  Add the 1 to left pile: 1 4 6 5  1 2 4 3

Form a new pile with 8: 1 4 6 5 8  1 2 4 3 5  Then play the 7 on it: 1 4  7 6 5 8  1 2  5 4 3 6

Add the 2 to mid- dle pile: 1 4 2 7 6 5 8  1 2 3 5 4 7 6  Add the 3 to right pile: 1  3 4 2 7 6 5 8  1  5 2 3 6 4 7 8

The idea behind Algorithm 3.1 is that we are using the recording piles S(σ) to implicitly label the order in which the elements of the permutation σ are added to the insertion piles R(σ). It is clear that this information then allows us to uniquely reconstruct σ by reversing the order in which the cards were played. However, even though reversing the Extended Patience Sorting Algorithm is much easier than reversing the RSK Algorithm through recursive “reverse row bumping”, the trade-off is that the stable pairs that result from the former are not independent whereas the tableau pairs generated by RSK are completely independent (up to shape).

That S(σ) = {s_{1}, s_{2}, …, s_{m}} records the order of the cards being added to the insertion piles is made clear if we instead add cards to the tops of new piles s′_{j} in Algorithm 3.1 rather than to the bottoms of the piles s_{j}. This yields modified recording piles S′(σ) from which each original recording pile s_{j} ∈ S(σ) can be recovered by simply reflecting the corresponding pile s′_{j} vertically.

Example 3.4. As in Example 3.3 above, let σ = 64518723 ∈ 𝔖_{8}. Then R(σ) is formed as before and

S′(σ) = 4  8 2 7 6 1 3 5 −−→^{reflect} 1  5 2 3 6 4 7 8 = S(σ)

We are now in a position to prove that the Extended Patience Sorting Algorithm has the same form of symmetry as the RSK Algorithm has for permutations.

Proposition 3.5. Let (R(σ), S(σ)) be the insertion and recording piles, respectively, formed by applying Algorithm 3.1 to σ ∈ 𝔖_{n}. Then reversing Algorithm 3.1 for the pair (S(σ), R(σ)) yields the inverse permutation σ^{−1}.

Proof. Construct S′(σ) from S(σ) as discussed above, and form the n ordered pairs (r_{ij}, s′_{ij}) where i indexes the individual piles and j the cards in the i^{th} piles. Then these n points correspond to the diagram of a permutation τ ∈ 𝔖_{n}. However, since reflecting these points through the line y = x yields the diagram for σ, it follows that τ = σ^{−1}. □

Proposition 3.5 suggests that Algorithm 3.1 is the right generalization of Algorithm 1.1 since we obtain the same symmetry property as for RSK. At the same time, though, since there are many more possible pile configurations than standard Young tableau (as we’ll show in Section 4 below), not every ordered pair of pile configurations with the same shape will result from Algorithm 3.1. Thus, it is necessary to first characterize the “stable pairs” that result from applying Extended Patience Sorting to a permutation. We do this in Section 3.2.

3.2. Characterizing “Stable Pairs” of Pile Configurations and Pile Configurations for Involutions. Based upon Proposition 3.5 above, there is a bijection between involutions and certain pile configurations. We will describe this bijection as a corollary to a more general characterization for the “stable pairs” of pile configurations that can result from applying the Extended Patience Sorting Algorithm to a permutation.

The following example, though very small, illustrates the most generic behavior that must be avoided in constructing stable pairs. As in Section 3.1 above, we denote by S′ the “reverse pile configuration” of S (which has all piles listed in reverse order).

Example 3.6. Even though the pile configuration R = {{3 > 1}, {2}} cannot result as the insertion piles given by an involution under the Extended Patience Sorting Algorithm, we can still try to look at the shadow diagram for the pre-image of the pair (R, R) under Algorithm 3.1:

R = 1 3 2 and S′ = 3 1 2 ⟹ 0123 _{0 1 2 3} • • •

Note that there are two competing constructions here. On the one hand, we have the diagram {(1, 3), (2, 2), (3, 1)} of a permutation given by the entries in the pile configurations. (In particular, the values in R specify the ordinates and the values in the corresponding boxes of S′ the abscissae.) On the other hand, the piles in R also specify shadowlines with respect to this permutation diagram. Here the pair (R, S) of pile configurations is “unstable” because their combination yields crossing shadowlines—which is clearly not allowed.

Similar considerations lead to avoiding the crossings of the form

0123 _{0 1 2 3} • • •  and  0123 _{0 1 2 3} • • •

Note also that these latter two crossings can also be used together to build something like the first crossing but with “extra” elements on the boundary of the polygon formed:

01234 _{0 1 2 3 4} • • • •

We can now make the following important definitions: Definition 3.7. Given a composition γ of n (denoted γ ⊧ n), we define 𝔓_{γ}(n) to be the set of all pile configurations R having shape sh(R) = γ and put

𝔓(n) = ⋃_{γ ⊧ n} 𝔓_{γ}(n).

Definition 3.8. Define the set Σ(n) ⊂ 𝔓(n) × 𝔓(n) to consist of all ordered pairs (R, S) with sh(R) = sh(S) such that the pair (RP W (R), RP W (S′)) avoids simultaneous occurrences of pairs of patterns (31-2, 13-2), (31-2, 32-1) and (32-1, 13-2) at the same positions in RP W (R) and RP W (S′).

In other words, if RP W (R) contains an occurrence of the first pattern in any of the above pairs, then RP W (S′) cannot contain an occurrence at the same positions of the second pattern in the same pair, and vice versa. Note that Definition 3.8 characterizes “stable pairs” of pile configurations (R, S) by forcing R and S to avoid certain sub-pile pattern pairs. As in Example 3.6, we are characterizing when the induced shadowlines cross.

Theorem 3.9. Extended Patience Sorting (Algorithm 3.1) gives a bijection between the symmetric group 𝔖_{n} and the “stable pairs” set Σ(n) given in Definition 3.8 above.

Proof. We will prove that for any stable pair (R, S) ∈ Σ(n) and any permutation σ ∈ 𝔖_{n},

σ = (\begin{matrix}RP W (S′) \\ RP W (R) \end{matrix}) (in the two-line notation) ⟺ (R, S) = (R(σ), S(σ)).

Clearly, if (R, S) = (R(σ), S(σ)) for some σ ∈ 𝔖_{n}, then σ = (\begin{matrix}RP W (S′) \\ RP W (R) \end{matrix}), so we only

need to prove that (R, S) ∈ Σ(n). Suppose that (R, S) ∉ Σ(n); then RP W (R) and RP W (S′) contain instances of one of the three forbidden pairs.

Suppose RP W (R) contains an occurrence (r_{3}, r_{1}, r_{2}) of 31-2, and RP W (S′) contains an occurrence (s′_{1}, s′_{3}, s′_{2}) of 13-2 at the same positions. Since r_{3} > r_{1} and r_{3}, r_{1} are consecutive entries in RP W (R), it follows that r_{3} and r_{1} must be in the same column c_{i}(R) of R (in fact, r_{1} is immediately on top of r_{3}). Since r_{1} < r_{2} and r_{2} is to the right of r_{1} in R, it follows that the column c_{j}(R) of R containing r_{2} must be to the right of the column containing r_{1} atop r_{3}. Therefore, s′_{2} must also be in a column c_{i}(S′) of S′ to the right of the column c_{j}(S′) containing s′_{3} on top of s′_{1}.

Consider the subpermutation τ of σ formed by deleting entries of RP W (R) and RP W (S′) that are not in these two columns. Alternatively, let R_{∗} and S′_{∗} consist only of the columns (c_{i}(R), c_{j}(R)) of R and (c_{i}(S′), c_{j}(S′)) of S′, respectively. Then

τ = (\begin{matrix}RP W (S′_{∗}) \\ RP W (R_{∗}) \end{matrix}) .

Note that the values r_{3} and r_{1} in c_{i}(S′) are consecutive left-to-right minima of τ, whereas r_{2} is not a left-to-right minimum of τ. Since r_{1} < r_{2} < r_{3}, it follows that r_{2}

cannot occur between r_{1} and r_{3} in τ. However, since (\begin{matrix}s′_{1} & s′_{3} & s′_{2} \\ r_{3} & r_{1} & r_{2} \end{matrix}) is a subpermutation

of τ and s′_{1} < s′_{2} < s′_{3}, it follows that r_{2} does occur between r_{1} and r_{3}, a contradiction.

A similar argument applies to the other two forbidden pairs, (31-2, 32-1) and (32-1, 13-2). The resulting contradiction in each case implies that we must have (R, S) ∈ Σ(n).

Conversely, if (R, S) ∈ Σ(n), then set σ = (\begin{matrix}RP W (S′) \\ RP W (R) \end{matrix}). We must show that

(R, S) = (R(σ), S(σ)). This can be done by showing that c_{1}(R) is the sequence of left-to-right minima of σ and c_{1}(S′) is the sequence of their positions, and then proceeding by induction on the length of σ.

We know that c_{1}(R) is decreasing and c_{1}(S′) is increasing, with both columns of the same length. Moreover, c_{1}(R) is the sequence of left-to-right minima of RP W (R), and c_{1}(S′) is increasing, so the values of c_{1}(R) are in decreasing order in σ. Note that the first term of c_{1}(R) is the leftmost value in σ, and the last term of c_{1}(R) is the least value of σ.

If every value in the first column of R is less than every value not in the first column of R, and every value in the first column of S′ is less than every value not in the first column of S′, then we are done. Now suppose this is not so. Then there exists a point (s′, r) with s′ ∈ (RP W (S′) \ c_{1}(S′) and r ∈ RP W (R) \ c_{1}(R)) such that there are points (s′_{1}, r_{1}) and (s′_{2}, r_{2}), where r_{1}, r_{2} ∈ c_{1}(R) and s′_{1}, s′_{2} ∈ c_{1}(S′)) are consecutive terms occupying the same positions in the first columns of R and S′, for which either r_{1} > r > r_{2} or s′_{1} < s′ < s′_{2}. None of the three forbidden pairs may occur at positions (s′_{1}, r_{1}), (s′_{2}, r_{2}), (s′, r), in other words, given that one of r_{1} > r > r_{2} or s′_{1} < s′ < s′_{2} must hold, we must avoid the following cases:

r_{1} > r > r_{2} and s′ < s′_{1}, i.e. an occurrence of (31-2, 32-1),
r_{1} > r > r_{2} and s′_{1} < s′ < s′_{2}, i.e. an occurrence of (31-2, 13-2),
r < r_{1} and s′_{1} < s′ < s′_{2}, i.e. an occurrence of (32-1, 13-2).

Hence, r_{1} > r > r_{2} implies s′ > s′_{2}, while s′_{1} < s′ < s′_{2} implies r > r_{1}. Thus, r_{2} is the first value of σ to the right of r_{1} that is less than r_{1}, and all values between r_{1} and r_{2} are to the right of r_{2}. Therefore, if r_{1} is a left-to-right minimum of σ, then r_{2} is the next left-to-right minimum of σ. Since the first term of c_{1}(R) is a left-to-right minimum of σ, it follows by induction that c_{1}(R) is the sequence of left-to-right minima of σ, which occur at positions in c_{1}(S′). This finishes the proof. □

Example 3.10. The pair of piles

(R, S) = (\begin{matrix}1 & & 3 \\ 4 & 2 & 7 \\ 6 & 5 & 8 \end{matrix} , \begin{matrix}1 & & 5 \\ 2 & 3 & 6 \\ 4 & 7 & 8 \end{matrix}) ∈ Σ(8)

corresponds to the permutation

σ = (\begin{matrix}RP W (S′) \\ RP W (R) \end{matrix}) = (\begin{matrix}1 & 2 & 4 & 3 & 7 & 5 & 6 & 8 \\ 6 & 4 & 1 & 5 & 2 & 8 & 7 & 3 \end{matrix}) = 64518723 ∈ 𝔖_{8}.

Based upon the characterization of stable pairs given in Theorem 3.9 and the Schützenberger-type Symmetry Property proven in Proposition 3.5, we can immediately describe a bijection between involutions and certain pile configurations. In particular, these pile configurations must avoid simultaneously containing the symmetric sub-pile patterns corresponding to the patterns given in Definition 3.8.

This corresponds to the reverse patience word for a pile configuration simultaneously avoiding a symmetric pair of the generalized patterns 31-2 and 32-1. As such it is interesting to compare this construction to two results recently obtained by Claesson and Mansour [6]:

(1) The size of S_{n}(3-12, 3-21) is equal to the number of involutions |ℑ_{n}| in 𝔖_{n}.

(2) The size of S_{n}(31-2, 32-1) is 2^{n−1}.

The first result suggests that there should be a way to relate the result in Theorem 3.9 to simultaneous avoidance of the very similar patterns 3-12 and 3-21. The second result suggests that restricting to complete avoidance of all simultaneous occurrences of 31-2 and 32-1 will yield a natural bijection between S_{n}(31-2, 32-1) and a subset 𝔑 ⊂ 𝔓(n) such that 𝔑 ∩ 𝔓_{γ}(n) contains exactly one pile configuration of each shape γ. A natural family for this collection of pile configurations consists of what we call non-crossing pile configurations; namely, for the composition γ = (γ_{1}, γ_{2}, …, γ_{k}) ⊧ n,

𝔑 ∩ 𝔓_{γ}(n) = {{{γ_{1} > ⋯ > 1}, {γ_{1} + γ_{2} > ⋯ > γ_{1} + 1}, …, {n > ⋯ > n − γ_{k−1}}}}

so that there are exactly 2^{n−1} such pile configurations. One can also show that 𝔑 is the image R(S_{n}(3-1-2)) of all permutations avoiding the classical pattern 3-1-2 under the Patience Sorting Algorithm.

4. Enumerating S_{n}(3-¯1-42)

In this section we use the results from Section 2 to both enumerate and characterize the permutations that avoid the generalized permutation pattern 2-31 unless it is part of the generalized pattern 3-1-42. We call this restricted form of the generalized pattern 2-31 a barred (generalized) permutation pattern and denote it by 3-¯1-42. (This notation is due to J. West, et al., and first appeared in the study of two-stack sortable permutations [8, 9, 25].)

Theorem 4.1.

(1) The set of permutations S_{n}(3-¯1-42) that avoids the pattern 3-¯1-42 is exactly the set RP W (R(𝔖_{n})) of reverse patience words obtainable from the symmetric group 𝔖_{n}.

(2) The size of S_{n}(3-¯1-42) is given by the n^{th} Bell number B_{n}.

Proof.

(1) Let σ ∈ S_{n}(3-¯1-42). Then, for i = 1, 2, …, n − 1, define

σ_{m_{i}} = min{σ_{j} | i ≤ j ≤ n}.

Since σ avoids 3-¯1-42, the subpermutation σ_{i}σ_{i+1} ⋯ σ_{m_{i}} must be a decreasing subsequence of σ. (Otherwise σ would necessarily contain a 2-31 pattern that is not part of a 3-1-42 pattern.) It follows that the left-to-right minima subsequences s_{1}, s_{2}, …, s_{k} of σ must be disjoint and satisfy Equation (2.1) so that the result follows by Lemmas 2.1 and 2.9.

(2) Recall that the Bell number B_{n} enumerates the set partitions of the set [n] = {1, 2, …, n}. From Part (1), the elements of S_{n}(3-¯1-42) are in bijection with pile configurations. Thus, since pile configurations are themselves set partitions by Lemma 2.1, we need only show that every set partition is also a pile configuration. But this follows by ordering the components of a given set partition by their smallest element so that Equation (2.1) is satisfied. □

Remark 4.2. We conclude by remarking that even though the set S_{n}(3-¯1-42) is enumerated by the very well known Bell numbers, it cannot be described in a simpler way using classical pattern avoidance. This means that there does not exist a countable set of non-generalized (a.k.a. classical) permutation patterns τ_{1}, τ_{2}, … such that

S_{n}(3-¯1-42) = S_{n}(τ_{1}, τ_{2}, …) = ⋂_{i≥1} S_{n}(τ_{i}).

There are two very important reasons that this cannot happen:

First of all, the Bell numbers satisfy log B_{n} = n(log n − log log n + O(1)) and so exhibit superexponential growth. However, in light of the Stanley-Wilf ex-Conjecture (which was recently proven by Marcus and Tardos [17]), the set of permutations S_{n}(τ) avoiding any classical pattern τ can only grow at most exponentially in n.

On the other hand, the so-called avoidance class of permutations

Av(3-¯1-42) = ⋃_{n≥0} S_{n}(3-¯1-42)

is not closed under taking order-isomorphic subpermutations, whereas it is easy to see that classes of permutations defined by classical pattern avoidance must be closed. (See Bóna [4], Chap. 5.) In particular, 3142 ∈ Av(3-¯1-42) but 231 ∉ Av(3-¯1-42).

At the same time, Theorem 4.1(2) implies that 3-¯1-42 belongs to the so-called Wilf Equivalence class for the generalized pattern 1-23. That is, if

τ ∈ {1-23, 3-21, 12-3, 32-1, 1-32, 3-12, 21-3, 23-1}

then the size of the avoidance class S_{n}(τ) is also given by the n^{th} Bell number B_{n}. In particular, Claesson [5] showed that |S_{n}(23-1)| = B_{n} via a direct bijection between permutations avoiding 23-1 and set partitions. Furthermore, given σ ∈ S_{n}(3-¯1-42), each segment between consecutive right-to-left minima must be a single decreasing run (when from read left to right), so it is easy to see that S_{n}(3-¯1-42) = S_{n}(23-1). Thus, the barred pattern 3-¯1-42 and the generalized pattern 23-1 are not just in the same Wilf equivalence class but also have identical avoidance classes.

Still, even though S_{n}(3-¯1-42) = S_{n}(23-1), it is more natural to use avoidance of 3-¯1-42 when studying Patience Sorting. Fundamentally, this lets us look at S_{n}(3-¯1-42) as the set of equivalence classes in 𝔖_{n} modulo 3-¯1-42 ∼^{P S} 3-¯1-24, where each equivalence class corresponds to a unique pile configuration. The same equivalence relation is not easy to describe when starting with an occurrence of 23-1. (Note that 23-1 ∼ 2-13 or 23-1 ∼ 21-3 is wrong since we would incorrectly get 2431 ∼ 2314 or 2431 ∼ 2134 instead of the correct 2431 ∼ 2413).

This suggests that there is even more information about pattern avoidance to be gotten from such a simple algorithm as Patience Sorting.

References

[1] D. Aldous and P. Diaconis. “Longest Increasing Subsequences: From Patience Sorting to the Baik-Deift-Johansson Theorem.” Bull. Amer. Math. Soc. 36 (1999), 413–432.

[2] E. Babson and E. Steingrímsson. “Generalized Permutation Patterns and a Classification of the Mahonian Statistics.” Séminaire Lotharingien de Combinatoire B44b (2000), 18 pp.

[3] J. Baik, P. Deift, and K. Johansson. “On the Distribution of the Length of the Longest Increasing Subsequence in a Random Permutation.” J. Amer. Math. Soc. 12 (1999), 1119–1178.

[4] M. Bóna. Combinatorics of Permutations. Chapman & Hall/CRC Press, 2004.

[5] A. Claesson. “Generalized Pattern Avoidance.” Europ. J. Combin. 22 (2001), 961–971.

[6] A. Claesson and T. Mansour. “Enumerating Permutations Avoiding a Pair of Babson-Steingrímsson Patterns.” Ars Combinatoria 77 (2005), 17–31.

[7] J. B. Conrey. “The Riemann Hypothesis.” Not. Amer. Math. Soc. 50 (2003), 341–353.

[8] S. Dulucq, S. Gire, and O. Guibert. “A Combinatorial Proof of J. West’s Conjecture.” Discrete Math. 187 (1998), 71–96.

[9] S. Dulucq, S. Gire, and J. West. “Permutations with Forbidden Subsequences and Nonseparable Maps.” Discrete Math. 153 (1996), 85–103.

[10] W. Fulton. Young Tableaux. LMS Student Texts 35. Cambridge University Press, 1997.

[11] C. Greene. “An Extension of Schensted’s Theorem.” Adv. in Math. 14 (1974), 254–265.

[12] D. E. Knuth. “Permutations, Matrices, and Generalized Young Tableaux.” Pac. J. Math. 34 (1970), 709–727.

[13] C. Kuykendall. “Analyzing Solitaire.” Science 283 (1999), 794–795.

[14] D. Mackenzie. “From Solitaire, a Clue to the World of Prime Numbers.” Science 282 (1998), 1631–1633.

[15] C. L. Mallows. “Problem 62-2, Patience Sorting.” SIAM Review 4 (1962), 148–149.

[16] C. L. Mallows. “Problem 62-2’.’ SIAM Review 5 (1963), 375–376.

[17] A. Marcus and G. Tardos. ”Excluded Permutation Matrices and the Stanley-Wilf Conjecture.” J. Combin. Th. Ser. A 107 (2004), 153–160.

[18] I. Peterson. “Solitaire-y Sequences.” MathTrek.

Available online at http://www.maa.org/mathland/mathtrek 7 5 99.html

[19] G. de B. Robinson. “On the Representations of the Symmetric Group.” Amer. J. Math. 60 (1938), 745–760.

[20] B. Sagan. The Symmetric Group, Second Edition. Graduate Texts in Mathematics 203. Springer-Verlag, 2000.

[21] C. Schensted. “Longest Increasing and Decreasing Subsequences.” Can. J. Math. 13 (1961), 179–191.

[22] M. P. Schützenberger. “Quelques remarques sur une construction de Schensted.” Math. Scand. 12 (1963), 117–128.

[23] R. Stanley. Enumerative Combinatorics, Volume 2. Studies in Advanced Mathematics 62. Cambridge University Press, 1999.

[24] G. Viennot. “Une forme géométrique de la correspondance de Robinson-Schensted.” In Combinatoire et Représenatation du Groupe Symétrique. D. Foata, ed. Lecture Notes in Mathematics 579. Springer-Verlag, 1977, pp. 29–58.

[25] J. West. Permutations with Forbidden Subsequences and Stack-sortable Permutations. Ph.D. thesis, M.I.T., 1990.

[26] X. Yan, P. Diaconis, P. Rusmevichientong, and B. Van Roy. “Solitaire: Man Versus Machine.” In Advances in Neural Information Processing Systems 17. L.K. Saul, Y. Weiss, and L. Bottou, eds. MIT Press, 2005, to appear.