{'fraction_non_alphanumeric': 0.06192660550458716, 'fraction_numerical': 0.011795543905635648, 'mean_word_length': 3.1969749054657957, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A human proof for a generalization of Shalosh B. Ekhad's 10^n Lattice Paths Theorem

Consider lattice paths in Z^2 taking unit steps north (N) and east (E). Fix positive integers r,s and put an equivalence relation on points of Z^2 by letting v,w be equivalent if v - w = m (r,s) for some m in Z. Call a lattice path valid if whenever it enters a point v with an E-step, then any further points of the path in the class of v are also entered with an E-step. Loehr and Warrington conjectured that the number of valid paths from (0,0) to (nr,ns) is (r+s choose r)^n. We prove this conjecture when s = 2.


Introduction
A lattice path is a directed graph whose vertices are elements of Z 2 where Z denotes the integers. All our lattice paths will have edges which are unit steps north (Nsteps) or east (E-steps). It is well-known and easy to prove that the number of such paths from (0, 0) to (r, s) is Given r, s we put an equivalence relation on Z 2 by saying that points v, w are equivalent if v − w = ℓ(r, s) for some ℓ ∈ Z. As usual, addition and scalar multiplication of points are done componentwise. Denote the equivalence class of v = (x, y) by [v] = [x, y]. Call a lattice path P valid if it satisfies the following condition: Whenever P enters a point v with an E-step then any future points of P in [v] must be entered by an E-step. Otherwise P is said to be invalid. Figure 1 shows an invalid path for r = 3, s = 2. In particular, we can take [v] = [2, 1] and then two points where the validity condition is violated are shown as circles. Loehr and Warrington made the following conjecture.
Conjecture 1.1 The number of valid paths from (0, 0) to (nr, ns) is Ekhad, Vatter, and Zeilberger [?] gave a fully computer-based proof of the special case r = 3, s = 2 of this conjecture. It is for this reason (and also at the request of its two human coauthors) that we call this "Shalosh B. Ekhad's 10 n Lattice Paths Theorem." Although our demonstration is very different in nature, being purely human and bijective rather than inductive, we should mention that some of our ideas came from looking at the trees generated by Ekhad. Also, while we were writing this note, it came to our attention that Jonas Sjöstrand [?] has given a bijective proof of the full conjecture which is similar to ours in some respects but differs in others.
The rest of this paper is structured as follows. In the next section we will provide three lemmas which will permit us to demonstrate that our bijection is x + y = i = 7 x + y = k = 10 P Q Figure 2: The Switching Lemma for r = 3, s = 2 well defined. These lemmas hold for all r, s. In the final section, we prove the case s = 2 of Conjecture 1.1.

Preliminary Lemmas
We first need to establish some notation. If P is any lattice path and v is any point, then P + v will denote the translated lattice path obtained by adding v to every point of P . Note that P is invalid precisely when there is some ℓ > 0 such that P and Q = P + ℓ(r, s) intersect where P enters the intersection with an N-step and Q enters it with an E-step. In Figure 1, ℓ = 2. Given P and a line x + y = i we let v i = v i (P ) be the intersection of P with this line. Note that this will not necessarily be the ith vertex of P unless P starts at the origin. We denote the coordinates of v i by (x i , y i ) = (x i (P ), y i (P )) and the edge/step of P into v i by e i = e i (P ).
The next lemma is fundamental to all that follows. The reader may find it useful to refer to Figure 2 while reading the statement and proof. Circles mark the points on the lines x + y = i, j and k.
Lemma 2.1 (Switching Lemma) Let P be a lattice path and let Q = P + (r, s). If there are integers i < k with then P is invalid. Proof Since the x-coordinate of a path changes by at most one with each step, the hypotheses imply that there is an index j with i < j ≤ k and x j (P ) = x j (Q). If one takes the smallest such j, then we must have e j (P ) = N and e j (Q) = E. It follows that P is invalid by the remark at the end of the first paragraph of this section.
Partially order Z 2 componentwise, i.e., (x, y) ≤ (x ′ , y ′ ) if and only if x ≤ x ′ and y ≤ y ′ . If P is a path and v is a point then we say that P passes strictly west of v if there is a point v ′ of P with the same y-coordinate as v satisfying v ′ < v. We also define P to pass weakly west of v if for all points v ′ of P with the same y-coordinate we have v ′ ≤ v. (We also insist that at least one such point exists.) Note the difference in the quantifiers between the two definitions. Passing east, either strictly or weakly, is defined by simply reversing the inequalities. Many of our geometric arguments will be based on the following lemma. A path satisfying the hypotheses of this result is shown in Figure 3.
Lemma 2.2 (Three-Points Lemma) Let u < v < w be three points in the same equivalence class and let P be a path. Suppose that P passes strictly west of u, weakly east of v, and weakly west of w. Then P is invalid.
Proof Among all such triples (u, v, w) satisfying the conditions of the lemma, we can choose one where u, v are a minimum distance apart, in which case v = u + (r, s). Now from the possible w's satisfying the hypotheses of the lemma with this u, v, pick the one which has minimum distance from v. Let i and k be the integers such that v and w are on the lines x + y = i + 1 and x + y = k, respectively. Also let Q = P + (r, s). Note that even though P and Q could intersect on x + y = i + 1, they could only do so if they entered with an N-step and an E-step, respectively. So we have x i (P ) > x i (Q). It is also clear from the choice of w that x k (P ) ≤ x k (Q). Thus we are done by the Switching Lemma.
Given two paths P, Q we say that P is northwest of Q if for every vertex v = (x, y) of P there is a vertex w = (x ′ , y ′ ) of Q southeast of v, i.e., x ≤ x ′ and y ≥ y ′ . The staircase is the path from (0, 0) to (nr, ns) with steps The dashed path in Figure 4 is the staircase for r = 3, s = 2, and n = 3. The staircase forms a natural boundary for valid paths. In following the proof of the following lemma, the reader may wish to consult Figure 4.

Lemma 2.3 (Staircase Lemma)
If P is a valid path from (0, 0) to (nr, ns) then P is northwest of S.
Proof Suppose not. Then since P ends northwest of S, we can pick a vertex v which is the first vertex of P ∩S after some vertex of P which is (strictly) southeast of S. Note that P must enter v with an N-step and so P passes weakly east of v. Note also that S must enter v with an E-step. It follows that we have points u and w in [v] which are on the lines y = 0 and y = ns, respectively, but that these points are strictly east of the corresponding points in [0, 0]. Since P begins at (0, 0) and ends at (nr, ns) which are both in [0, 0], P passes strictly west of u and weakly west of w. So P is invalid by the Three-Points Lemma, a contradiction.

The bijection
Let V n be the set of all valid lattice paths from (0, 0) to (nr, ns). Then to prove Conjecture 1.1, it suffices to find, for each n ≥ 2, a bijection φ : V n → V 1 ×V n−1 . To see this, note that every lattice path from (0, 0) to (r, s) is valid and so |V 1 | = r+s r . Iterating this map gives a bijection between V n and (V 1 ) n . And the latter is clearly counted by r+s r n .
Proof (of Conjecture 1.1 for s = 2) We construct the bijection φ when s = 2. Given P ∈ V n we wish to construct φ(P ) = (P ′ , Q ′ ) ∈ V 1 × V n−1 . By convention, we will consider P ′ as going from (0, 0) to (r, s) and Q ′ as going from (r, s) to (nr, ns). (Strictly speaking, Q ′ is not in V n−1 since it doesn't begin at the origin. But the translation of a valid path is valid, so no harm is done.) Consider the prefix of P up to and including the second N-step which is of the form E a NE b N for some a, b ≥ 0. By the Staircase Lemma, we must have a + b ≤ r. Now consider the suffix of P following the last N-step. Depending on whether the combined number of E-steps in the prefix and the suffix is at least r or less than r, we have two cases.
(1) For some path Q we have (2) For some path Q we have In the first case, we let An example of such a path P and its image is given in Figure 5 where the circles indicate the endpoints of Q and Q ′ . To show that the map and its inverse are well-defined, we will need the following concept and result. Given two paths A and B, a blocked edge is an N-edge or an E-edge of Z 2 which can not be on any valid path having A as its prefix and B as its suffix. Such edges will be marked with X's in our figures.
Proposition 3.1 In case (1), the path Q ′ is valid and begins with at most r − b E-steps.
Proof Clearly Q ′ is valid being a translate of a subpath of a valid path. For the second statement, suppose to the contrary that Q ′ begins with more than r − b E-steps. Then Q contains a point (d, 2) where d > r + a. But now it is impossible for P to get to (rn, 2n). This is because the initial E-steps of P produce a sequence of blocked N-edges starting at points (x, y(x)) for every x with d ≤ x ≤ rn, where 2 ≤ y(x) < sn and y(x) is a weakly increasing function of x. So we have a contradiction.
In the second case, we will show that Q = RE r+1 for some path R. Assuming this for the moment, we can define where R ′ = R + (c + r + 1, 1). Figure 6 illustrates this case with the endpoints of Q and Q ′ being marked with closed circles while those of R and R ′ are marked with open ones.
We now verify the claim about Q and the fact that Q ′ is valid.
Proposition 3.2 In case (2), the path Q ends with at least r + 1 E-steps. In addition, Q ′ is valid.
Proof We prove the first statement by contradiction. Note that because of the final N-step in P , any E-edge into a vertex of the class [r − c, 2] is blocked. Now the subpath QN of P passes strictly west of u = (r − c, 2) since a + b + c < r. This subpath also ends at w = u + (n − 1)(r, 2). But if Q ends with fewer than r + 1 E-steps then QN passes weakly east of v = u + (n − 2)(r, 2) since the E-edge into v is blocked. This contradicts the Three-Points Lemma as long as n ≥ 3. For n = 2, just note that P would have to contain points both east and west of the blocked edge into (r − c, 2) which is impossible.
Since R ′ is a translation of a valid path R, it is valid itself. So the only way Q ′ could be invalid is if one of the E-steps in the prefix E a+b+c+1 is in conflict with an N-step in R ′ . Note that such an N-step must be out of a point of some class [x, 3] with x ≥ 2r + 1. Suppose that this is the case and consider what this implies about the original path P . In particular, consider the class [r − c, 2] as in the previous paragraph. Using the same u and w as before, the supposed N-step forces P to contain a point weakly east of some v in this class with u < v < w. But then P must pass weakly east of v since the E-edge into v is blocked. So the Three-Points Lemma (or a direct argument when n = 2) provides the necessary contradiction.
We now describe the inverse map. Suppose we are given (P ′ , Q ′ ) ∈ V 1 × V n−1 and write for some path R ′ . Then, again, we have two cases to describe P = φ −1 (P ′ , Q ′ ).
It is easy to verify that this is a case-by-case inverse for the map φ. Furthermore, the demonstration that φ −1 is well defined is quite similar to the one just given for φ, so we omit it. This completes the proof of Conjecture 1.1 when s = 2.
We can say a little more about the case s = 2. Let Φ : V n → (V 1 ) n be the map obtained by composing φ with itself n − 1 times. Consider a path P ∈ V n and let Φ(P ) = (P ′ 1 , . . . , P ′ n ). Then directly from our definition of φ, we see that P and P ′ 1 begin with the same number of E-steps before the first N-step. So given a with 0 ≤ a ≤ r, Φ restricts to a bijection between the P with prefix E a N and the n-tuples (P ′ 1 , . . . , P ′ n ) where P ′ 1 satisfies the same restriction. But, as we mentioned before, the validity condition imposes no restriction on paths in V ′ 1 , so the number of such P ′ 1 is clearly r − a + 1. Thus we have proved the following corollary.
Corollary 3.3 Suppose s = 2. Given a with 0 ≤ a ≤ r, the number of P ∈ V n with a prefix of the form E a N is (r − a + 1) r+2 2 n−1 .