Descent-restricted subsequences via RSK and evacuation Krishna Menon, Anurag Singh Abstract The length š—‚š—Œ ⁔ ( Ļ€ ) \mathsf{is}(\pi) of a longest increasing subsequence in a permutation Ļ€ \pi has been extensively studied. An increasing subsequence is one that has no descents. We study generalizations of this statistic by finding longest subsequences with other descent restrictions. We first consider the statistic which encodes the longest length of a subsequence with a given number of descents. We then generalize this to restrict the descent set of the subsequence. Extending the classical result for š—‚š—Œ ⁔ ( Ļ€ ) \mathsf{is}(\pi) , we show how these statistics can be obtained using the RSK correspondence and the Schützenberger involution. In particular, these statistics only depend on the recording tableau of the permutation. 1 Introduction The study of longest increasing subsequences (LIS) in permutations is a classical and central topic in combinatorics, with strong connections to representation theory, probability, and theoretical computer science. A foundational result of Schensted shows that the length of a longest increasing subsequence of a permutation can be read off from the Robinson–Schensted–Knuth (RSK) correspondence, namely as the length of the first row of the associated Young diagram [ 12 ] . This discovery initiated a vast body of work on variants, distributions, and refinements of LIS (see, for instance, [ 11 , 14 ] , and the references therein). A popular generalization is Greene’s theorem [ 7 ] , which extends Schensted’s result to give interpretations for other row lengths of the Young diagrams obtained using the RSK correspondence. This involves the statistic \mathsf{is}_{k}(\pi) , which is the longest length of a subsequence that can be expressed as a union of k increasing subsequences. Variants replacing monotonicity with prescribed up-down patterns have also been explored. A notable example is longest alternating subsequences, introduced and studied by Stanley [ 15 ] . There are several other statistics whose motivation comes from LIS [ 2 , 4 , 17 ] . For a permutation \pi\in\mathfrak{S}_{n} and a set D\subseteq[n-1] , we define \mathsf{ls}_{D}(\pi)\coloneqq\max\{\#I\mid\operatorname{Des}(\pi_{I})=D\}, the length of a longest subsequence of \pi whose descent set is precisely D . This statistic simultaneously generalizes longest increasing subsequences ( D=\varnothing ), alternating subsequences, and subsequences with a fixed number of descents. For special cases of these statistics, we describe bounds on them and also characterize and count the permutations that achieve these bounds. For the general statistic \mathsf{ls}_{D} , we describe a method (based on a decomposition of D into intervals) to determine when such subsequences exist and how their maximum lengths can be computed. This relies on the use of growth diagrams and the Schützenberger involution [ 6 , 13 ] , and leads to a complete tableau-theoretic description of these descent-restricted subsequence statistics. In particular, for fixed D , the value of \mathsf{ls}_{D}(\pi) depends only on the recording tableau Q(\pi) , extending the classical result for longest increasing subsequences. The paper is organized as follows. In Section 2 , we review the necessary background on the RSK correspondence and Schützenberger involution. Section 3 studies longest subsequences with a fixed number of descents. We first obtain bounds for these statistics and characterize when they are met. We then describe a method to extract these statistics from the evacuation growth diagram. In Section 4 , we extend these results to the statistic \mathsf{ls}_{D} . We also characterize when two permutations attain the same value for all these statistics. We conclude with several open problems and directions for future work. Remark 1.1 . The questions posed in [ 15 , Section 5] were the initial motivation for our study. However, we later found that an algorithm to compute a statistic essentially equivalent to \mathsf{ls}_{D} (called longest wave subsequence with trend ) has been defined in [ 2 ] . In particular, Algorithm 4.14 described in Section 4 is similar to the one in [ 2 ] . Since the connections to RSK and the Schützenberger involution are not explored in [ 2 ] , we present them in this work. 2 Preliminaries We use \mathfrak{S}_{n} to denote the set of permutations of [n]\coloneqq\{1,2,\ldots,n\} . Permutations are written in one-line notation. For a permutation \pi\in\mathfrak{S}_{n} and a subset I\subseteq[n] , we write \pi_{I} for the subsequence of \pi given by \pi(i_{1})\pi(i_{2})\cdots\pi(i_{k}), where i_{1}\pi(i+1)\} denotes the descent set of \pi , and \operatorname{des}(\pi)=\#\operatorname{Des}(\pi) denotes the number of descents. We define the ascent set \operatorname{Asc}(\pi) and the number of ascents \operatorname{asc}(\pi) analogously. • \mathsf{is}(\pi) denotes the length of a longest increasing subsequence of \pi . • For k\geq 1 , \mathsf{is}_{k}(\pi) denotes the maximum length of a subsequence of \pi that can be written as the union of k increasing subsequences. Example 2.1 . Let \pi=234615 . If I=\{2,4,5\} , then \pi_{I}=361 . Moreover, \operatorname{Des}(\pi)=\{4\} and \operatorname{des}(\pi)=1 . The length of a longest increasing subsequence of \pi is \mathsf{is}(\pi)=4 ; for instance, the subsequence 2345 is increasing. Furthermore, \mathsf{is}_{2}(\pi)=6 , since the entire permutation \pi can be written as the union of two increasing subsequences, for example 2346 and 15 . 2.1 The RSK correspondence We now recall some basic facts about the Robinson–Schensted–Knuth (RSK) correspondence defined in [ 12 ] . The definitions and results we state can be found in [ 16 ] . A partition \lambda of n , denoted \lambda\vdash n , is a weakly decreasing sequence of positive numbers that sums to n . The Young diagram of a partition \lambda=(\lambda_{1},\lambda_{2},\ldots) consists of rows of boxes where the i -th row (from the top) has \lambda_{i} boxes. A standard Young tableau (SYT) of shape \lambda is a filling of the boxes in the Young diagram of a partition of n with the numbers from [n] (each used once) such that the rows and columns are increasing. Given a permutation \pi\in\mathfrak{S}_{n} , the RSK correspondence associates to \pi a pair (P(\pi),Q(\pi)) of SYTs of the same shape \lambda\vdash n . The insertion tableau P(\pi) is obtained by performing row-insertion on the entries \pi(1),\pi(2),\ldots,\pi(n) in order, while the recording tableau Q(\pi) records the positions at which new boxes are added in the insertion process. We will not go through the details of this well-known correspondence but only mention the results we will use. If (\lambda_{1},\lambda_{2},\ldots) is the shape of P(\pi) , which is the same as that of Q(\pi) , then \mathsf{is}_{k}(\pi)=\lambda_{1}+\lambda_{2}+\cdots+\lambda_{k} . If the first row of Q(\pi) is u_{1}2 , because no subsequence of \pi can have more descents than \pi itself. The following lemma records a few basic properties of these statistics which will be used repeatedly in the sequel. Lemma 3.3 . For any permutation \pi , we have \mathsf{ls}_{d}(\pi)\geq d+1 for all d\leq\operatorname{des}(\pi) and \mathsf{ls}_{d}(\pi)=0 for all d>\operatorname{des}(\pi) . Moreover, for any d_{1}\operatorname{des}(\pi) . Finally, the strict inequality \mathsf{ls}_{d_{1}}(\pi)<\mathsf{ls}_{d_{2}}(\pi) for d_{1}\pi(i_{m+1}) . The fact that there are at least two ascents in [i_{m},i_{m+1}-1] means that there exist i,j\in[i_{m},i_{m+1}-1] where i\pi(i_{m+1}) and \pi(j)<\pi(i_{m}) , or 2. \pi(i_{m+1})<\pi(i)<\pi(j) , or 3. \pi(i)<\pi(j)<\pi(i_{m}) . In each case, \pi_{I\cup\{i,j\}} is a subsequence of length k+2 with one descent. āˆŽ The above proposition, along with Lemma 3.4 , gives us the following result. Corollary 3.6 . For any permutation \pi and d\leq\operatorname{des}(\pi) , if \operatorname{asc}(\pi)=\mathsf{is}(\pi) , then \mathsf{ls}_{d}(\pi)=\mathsf{is}(\pi)+d+1 . However, the converse of the above corollary is not true. For example, for \pi=563412 , we have \mathsf{is}(\pi)=2 , \mathsf{ls}_{1}(\pi)=4 , and \operatorname{asc}(\pi)=3 . We now count the permutations described in Proposition 3.5 . To do this, we will need to recall the definition of a semistandard Young tableau (SSYT) . An SSYT of shape \lambda is a filling of the Young diagram of \lambda with positive integers such that the rows are weakly increasing and columns are strictly increasing. For any partition \lambda , we use f^{\lambda} to denote the number of SYTs of shape \lambda ; and for any k\geq 1 , we use s_{\lambda}(1^{k}) to denote the number of SSYTs of shape \lambda with entries from [k] . This notation for the number of SSYTs is a reflection of the fact that these numbers can be extract using Schur functions (see [ 16 , Chapter 7] ). Proposition 3.7 . For any n\geq 1 , we have \#\{\pi\in\mathfrak{S}_{n}\mid\operatorname{asc}(\pi)=\mathsf{is}(\pi)-1\}=\sum_{\lambda\vdash n}f^{\lambda}s_{\lambda^{\prime}}(1^{\lambda_{1}}). This sequence of numbers is given by [ 10 , A268699 ] . Proof. We prove the result by showing that for any \lambda\vdash n , the number of SYTs Q of shape \lambda with \operatorname{des}(Q)+\lambda_{1}=n is given by s_{\lambda^{\prime}}(1^{\lambda_{1}}) . The result follows by the RSK correspondence. Fix a partition \lambda\vdash n . By transposing the SSYTs, we can think of s_{\lambda^{\prime}}(1^{\lambda_{1}}) as counting tableaux of shape \lambda such that • entries strictly increase along rows, • entries weakly increase along columns, and • all entries are from [\lambda_{1}] . We will exhibit a bijection between such tableaux and the SYTs we want to count. Starting with an SYT Q of shape \lambda such that \operatorname{des}(Q)+\lambda_{1}=n we construct such a tableau as follows: Suppose the entries of the first row of Q are u_{1}j . Proof. Let i\leq j . Choose an increasing subsequence of \pi(1)\pi(2)\cdots\pi(k) that is of length i (which is possible by the definition of j ). If the last term of this subsequence is \pi(m) and \pi(m)>\pi(k) , then appending \pi(k+1)\pi(k+2)\cdots\pi(n) to the end of this subsequence gives a subsequence of length i+n-k with descent set \{i\} . If \pi(m)\leq\pi(k) , then deleting \pi(m) and appending \pi(k)\pi(k+1)\cdots\pi(n) gives us a subsequence of the required form. Hence, we have \mathsf{ls}_{\{i\}}(\pi)\geq i+n-k . If i>j , then any increasing subsequence of length i (if one exists) must have last entry \pi(m) for some m>k . But no term after \pi(m) is smaller than it (by the definition of k ). Hence, there cannot exist a subsequence with descent set \{i\} . āˆŽ Just as we were able to extract \mathsf{ls}_{1}(\pi) from the first row of Q(\pi) and its evacuation tableau (see Proposition 3.8 ), we can also do so for \mathsf{ls}_{\{i\}}(\pi) . Proposition 4.6 . Let \pi be a permutation of size n and set Q=Q(\pi) and Q_{e}=\operatorname{evac}(Q) . For any i\geq 1 , we have \mathsf{ls}_{\{i\}}(\pi)=\operatorname{max}\{i+j\mid Q(1,i)+Q_{e}(1,j)\leq n\text{ and }Q_{e}(1,j+1)\neq Q_{e}(1,j)+1\} where we set the maximum of the empty set to be 0 . Proof. For any i,j\geq 1 , we use u_{i} to denote Q(1,i) and v_{j} to denote n-Q_{e}(1,j)+1 . We say that a pair (i,j) is a good pair if u_{i}\pi(v_{j}) , we get a subsequence satisfying our requirements. If \pi(u_{i})<\pi(v_{j}) , replace \pi(u_{i}) in this subsequence with \pi(v_{j}-1) . This will give us a subsequence that satisfies our requirements. Next suppose that we have a subsequence of size i+k with descent set \{i\} . We will show that there exists a good pair (i,j) where j\geq k . This will prove the proposition. Suppose that there is no such good pair. Since we already have u_{i}k and v_{j},v_{j-1},\ldots,v_{k+1},v_{k} forms a sequence of consecutive numbers. Hence, we have that • \pi(v_{j})\pi(v_{j-1})\cdots\pi(v_{k+1})\pi(v_{k}) is an increasing factor of \pi , • any increasing subsequence of length i in \pi must end at an index weakly to the right of u_{i}=v_{j} , and • any increasing subsequence of length k in \pi must begin at an index weakly to the left of v_{k} . This tells us that it is impossible for \pi to have a subsequence of length i+k with descent set \{i\} , which is a contradiction. āˆŽ Example 4.7 . With \pi=14567283 , the first row of Q=Q(\pi) is 1,2,3,4,5,7 and the first row of Q_{e}=\operatorname{evac}(Q(\pi)) is 1,3,5,6,7,8 . Using the previous proposition, we get \mathsf{ls}_{\{3\}}(\pi)=5 . This is because the maximum j such that Q(1,3)+Q_{e}(1,j)\leq 8 and Q_{e}(1,j)\neq Q_{e}(1,j+1) is j=2 . Using the interpretation of the entries of the first rows of Q(\pi) and \operatorname{evac}(Q(\pi)) , we get the following equivalent formulation of Proposition 4.6 . Proposition 4.8 . Let \pi be a permutation of size n and i\geq 1 be such that \mathsf{ls}_{\{i\}}(\pi)\neq 0 . Suppose k is the smallest number such that k\in\operatorname{Des}(\pi) and \mathsf{is}(\pi_{[k]})\geq i . Then \mathsf{ls}_{\{i\}}(\pi)=i+\mathsf{is}(\pi_{[k+1,n]}). From definitions, it is clear that for any permutation \pi , we have \mathsf{ls}_{\{i\}}(\pi)\leq\mathsf{is}(\pi)+i . In the case i=1 , we characterize when this bound is (not) met. Corollary 4.9 . For a permutation \pi\in\mathfrak{S}_{n} , we have \mathsf{ls}_{\{1\}}(\pi)<\mathsf{is}(\pi)+1 if and only if the last entry of the first row of \operatorname{evac}(Q(\pi)) is n . The number of such permutations is given by \sum_{\lambda\vdash n-1}f^{\lambda+1}f^{\lambda} where \lambda+1=(\lambda_{1}+1,\lambda_{2},\ldots) for any partition \lambda . Proof. The characterization of \pi for which \mathsf{ls}_{\{1\}}(\pi)<\mathsf{is}(\pi)+1 can be derived using Proposition 4.6 . These are precisely the permutations where any longest increasing subsequence must use the first term of the permutation. To count these permutations, we note that their reverse complements correspond, under RSK, to pairs (P,Q) of SYTs of the same shape where the last entry of the first row of Q is n . āˆŽ 4.2 The general case We now move on to the general statistic \mathsf{ls}_{D} . The proof of the following result is similar to that of Proposition 4.5 . Proposition 4.10 . Let \pi be a non-identity permutation of size n . Let D=D^{\prime}\sqcup[i,i+l-1] where i is the largest element of D such that i-1\notin D . Let k be the largest index such that \pi_{[k,n]} has a decreasing subsequence of length l . We have, \mathsf{ls}_{D}(\pi)\neq 0 if and only if i\leq\mathsf{ls}_{D^{\prime}}(\pi_{[k]}) . The above proposition allows us to inductively determine if \mathsf{ls}_{D}(\pi)\neq 0 by breaking up D into intervals. We now describe a method to extract \mathsf{ls}_{D}(\pi) using this break up of D . We use the notation \mathsf{ds}(\pi) to denote the length of a longest decreasing subsequence of \pi . Proposition 4.11 . Let \pi\in\mathfrak{S}_{n} and D\subseteq[n-1] such that \mathsf{ls}_{D}(\pi)\neq 0 . If D=\varnothing , we have \mathsf{ls}_{D}(\pi)=\mathsf{is}(\pi) . Otherwise, we have \mathsf{ls}_{D}(\pi)=m+\mathsf{ls}_{D^{\prime}}(\pi_{[k,n]}) where D^{\prime}=\{i-m\mid i\in D\setminus[m]\} and • if 1\in D , then m is the smallest number such that m+1\notin D and k is the smallest index such that \mathsf{ds}(\pi_{[k]})=m+1 , and • if 1\notin D , then m=\min D-1 and k is the smallest index such that \mathsf{is}(\pi_{[k]})=m+1 . Proof. We only consider the case when 1\in D , the other case can be proved similarly. By the definition of m and k , we must have that \mathsf{ls}_{D}(\pi)\leq m+\mathsf{ls}_{D^{\prime}}(\pi_{[k,n]}) . We prove the equality by constructing a subsequence of \pi with descent set D of the required length. Let \pi_{K} be a decreasing subsequence of length m+1 with \max K=k and \pi_{J} be a subsequence with J\subseteq[k,n] and \operatorname{Des}(\pi_{J})=D^{\prime} . Let j=\min J . If \pi_{k}\leq\pi_{j} , then consider I=(K\setminus\{k\})\cup J and note that \operatorname{Des}(\pi_{I})=D . Similarly, if \pi_{k}>\pi_{j} , then consider I=K\cup(J\setminus\{j\}) . āˆŽ We unravel the inductive method mentioned above to describe a procedure to extract \mathsf{ls}_{D}(\pi) directly. To do this, it is convenient to represent the set D as a composition. To any composition c=(c_{1},c_{2},\ldots,c_{k}) , we associate a set D_{c} as follows: Set d_{i}=c_{1}+c_{2}+\cdots+c_{i} for all i\in[k] . If k is odd, then D_{c}=[d_{1}]\cup[d_{2}+1,d_{3}]\cup\cdots\cup[d_{k-1}+1,d_{k}]. Similarly, if k is even, then D_{c}=[d_{1}+1,d_{2}]\cup[d_{3}+1,d_{4}]\cup\cdots\cup[d_{k-1}+1,d_{k}]. For example, D_{(2,3,1)}=\{1,2,6\} . To extract \mathsf{ls}_{D}(\pi) , we consider a triangle of pairs that record the longest increasing and decreasing subsequence lengths for factors of \pi . Definition 4.12 . For a permutation \pi\in\mathfrak{S}_{n} and 1\leq i\leq j\leq n , a_{i,j}(\pi)\coloneqq(\mathsf{is}(\pi_{[i,j]}),\mathsf{ds}(\pi_{[i,j]})). We draw the triangle of a_{i,j}(\pi) as shown in Figure 3 . We use blue entries for longest increasing subsequence lengths and red for decreasing. If the triangle is rotated 45 degrees clockwise, then the labeling i,j is just like that of a matrix. Note that the values a_{i,j}(\pi) are the lengths of the firsts rows and columns of the (nonempty) partitions in the evacuation growth diagram of Q(\pi) . Example 4.13 . For \pi=314526 , we have a_{2,5}(\pi)=({\color[rgb]{0,0,1}3},{\color[rgb]{1,0,0}2}) since the length of a longest increasing subsequence of 1452 is 3 and that of a longest decreasing subsequence is 2 . We now describe an algorithm to extract \mathsf{ls}_{D}(\pi) using the triangle of a_{i,j}(\pi) values. Algorithm 4.14 . Given a composition c=(c_{1},\ldots,c_{k}) and a permutation \pi , we extract \mathsf{ls}_{D_{c}}(\pi) as follows. We consider the case when k is even, the other case is analogous. 1. Find the smallest value of j_{1} such that the second entry of a_{1,j_{1}}(\pi) is c_{1}+1 . If no such j_{1} exists, then \mathsf{ls}_{D_{c}}(\pi)=0 . 2. If k>1 , find the smallest value of j_{2} such that the first entry of a_{j_{1},j_{2}}(\pi) is c_{2}+1 . If no such j_{2} exists, then \mathsf{ls}_{D_{c}}(\pi)=0 . 3. Continue this way till either we get \mathsf{ls}_{D_{c}}(\pi)=0 at some step or we find j_{k} . If the first entry of a_{j_{k},n}(\pi) is l , then \mathsf{ls}_{D_{c}}(\pi)=c_{1}+c_{2}+\cdots+c_{k}+l . Example 4.15 . Let \pi=3247516 and D=\{2,3\} . To extract \mathsf{ls}_{D}(\pi) from the a_{i,j}(\pi) triangle, note that D=D_{(1,2)} (see Figure 3 ). The steps to extract \mathsf{ls}_{D}(\pi) is as follows. 1. We move up from the bottom-left entry until we see a term with first (blue) entry 2=c_{1}+1 . Here we find it at a_{1,3}(\pi) . 2. We then move down to the bottom of the triangle. We then move up until we see a term with second (red) entry 3=c_{2}+1 . Here we find it at a_{3,6}(\pi) . 3. We then move down to the bottom of the triangle. Now we keep moving up for as much as we can, and then record the first (blue) entry in this term. Here it is a_{6,7}(\pi) , whose first entry is 2 . Hence, we have \mathsf{ls}_{D}(\pi)=1+2+2=5 . ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}3},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}3},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}3},{\color[rgb]{1,0,0}3}) ({\color[rgb]{0,0,1}4},{\color[rgb]{1,0,0}3}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}3},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}3},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}3},{\color[rgb]{1,0,0}3}) ({\color[rgb]{0,0,1}4},{\color[rgb]{1,0,0}3}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}3}) ({\color[rgb]{0,0,1}3},{\color[rgb]{1,0,0}3}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}3}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}3}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}1}) Figure 3 : Extracting \mathsf{ls}_{\{2,3\}}(\pi)=5 from the a_{i,j}(\pi) triangle. Example 4.16 . Suppose \pi is a permutation such that the a_{i,j}(\pi) triangle is given by Figure 4 . Then we must have \mathsf{ls}_{\{1,2,4,5\}}(\pi)=0 since we cannot finish the procedure to extract \mathsf{ls}_{D}(\pi) . ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}3}) ({\color[rgb]{0,0,1}3},{\color[rgb]{1,0,0}3}) ({\color[rgb]{0,0,1}3},{\color[rgb]{1,0,0}3}) ({\color[rgb]{0,0,1}3},{\color[rgb]{1,0,0}3}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}3},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}3},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}3},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}3},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}3},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}2}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}2},{\color[rgb]{1,0,0}1}) ({\color[rgb]{0,0,1}1},{\color[rgb]{1,0,0}1}) Figure 4 : Showing \mathsf{ls}_{\{1,2,4,5\}}(\pi)=0 using the a_{i,j}(\pi) triangle. From the algorithm described above, we can see that for any D , the value \mathsf{ls}_{D}(\pi) only depends on the values a_{i,j}(\pi) as i,j varies over 1\leq i