COMMENT ON ‘COUNTING NONINTERSECTING

LATTICE PATHS WITH TURNS’ BY C. KRATTENTHALER

Martin Rubey

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria. e-mail: a9104910@unet.univie.ac.at

The argument in the proof of Theorem 4 on pp. 11/12 that a family of two-rowed arrays with associated permutation not the identity permutation must contain a crossing point contains an error: the inequality A_{1}^{(σ(i+1))} − 1 ≤ A_{1}^{(σ(i))} on page 12 is not true in general.

The paragraph at the bottom of page 11 to the top of page 12 must be replaced by:

“Finally we have to show that, given a pair (P, σ), P = (P_{1}, …, P_{r}), σ ≠ id, there exist neighbouring two-rowed arrays having a crossing point.

If σ ≠ id then there must exist an i with σ(i+1) < i+1. Without loss of generality we may assume that i is minimal with this property. Then all two-rowed arrays P_{j} with j ≤ i have nonnegative type, whereas P_{i+1} has negative type.

Let us momentarily define a_{0}^{(i+1)} := A_{1}^{(σ(i+1))} − 1. (Recall that we denoted the entries of P_{j} by a_{ℓ}^{(j)} and b_{ℓ}^{(j)}, respectively, see (22).) Furthermore set s_{i+1} = 0. We show next that, either we find two neighbouring arrays containing a crossing point, or for any j ∈ {σ(i + 1), …, i} there is an index s_{j} ∈ {1, 2, …, k_{j}} such that

a_{s_{j}}^{(j)} ≤ a_{s_{j+1}}^{(j+1)} and b_{s_{j}}^{(j)} ≥ b_{s_{j+1}}^{(j+1)}.  (C1)

We do a reverse induction on j. Suppose we have already found indices s_{i}, s_{i−1}, …, s_{j+1} such that (C1) is satisfied. Since P_{j} has nonnegative type, the element a_{1}^{(j)} exists. If a_{s_{j+1}}^{(j+1)} < a_{1}^{(j)}, then because of (13) and (C1) we have also

b_{0}^{(j)} = A_{2}^{(σ(j))} ≤ A_{2}^{(j)} ≤ A_{2}^{(σ(i+1))} < b_{0}^{(i+1)} ≤ b_{s_{j+1}}^{(j+1)},

and thus (a_{1}^{(j)}, b_{s_{j+1}}^{(j+1)}) is a crossing point of P_{j} and P_{j+1}.

On the other hand, if a_{s_{j+1}}^{(j+1)} ≥ a_{1}^{(j)} then let s_{j} be maximal such that a_{s_{j}}^{(j)} ≤ a_{s_{j+1}}^{(j+1)}. We already know that s_{j} ≥ 1. Because of (C1) we also have

E_{1}^{(j)} ≥ E_{1}^{(σ(i+1))} ≥ A_{1}^{(σ(i+1))} − 1 = a_{0}^{(i+1)} ≥ a_{s_{j+1}}^{(j+1)},

and thus s_{j} ≤ k_{j}.

Since P_{j} has nonnegative type, the element b_{s_{j}}^{(j)} exists. If b_{s_{j}}^{(j)} < b_{s_{j+1}}^{(j+1)}, then by construction of s_{j} we have a_{s_{j+1}}^{(j+1)} < a_{s_{j}+1}^{(j)}, and thus (a_{s_{j}+1}^{(j)}, b_{s_{j+1}}^{(j+1)}) is a crossing point

of P_{j} and P_{j+1}. If, on the other hand, b_{s_{j}}^{(j)} ≥ b_{s_{j+1}}^{(j+1)}, then we have found s_{j} such that (C1) holds.

For j = σ(i + 1) though, this leads to a contradiction. For, the type of P_{j} is σ(j) − j ≥ 0, and therefore

A_{1}^{(σ(j))} ≤ a_{1}^{(j)} + j − σ(j) ≤ a_{s_{j}}^{(j)} + j − σ(j) ≤ a_{0}^{(i+1)} + j − σ(j) = A_{1}^{(j)} − 1 + j − σ(j),

where we used (C1) for the last inequality. But on the other hand, by (13) we have A_{1}^{(σ(j))} ≥ A_{1}^{(j)} + j − σ(j), a contradiction.”

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria.