No label defined (Q4510684)

This is a preprint from 1991, which is referenced by numerous sequences in the Encyclopedia of Integer Sequences. This is the reason that it was now finally published after more than a decade. The reason for the delay of publication was that it was somehow ``superseded'' by the article [Ars Comb. 34, 3--15 (1992; Zbl 0770.05003)] by the author, the reviewer, and B. E. Sagan. The subject of the preprint is the enumeration of walks in the plane integer lattice with positive and negative unit steps (i.e., the allowed steps are \((\pm1,0)\), \((0,\pm1)\)). Results are given for the problem of counting such walks confined to a half-plane, respectively to a quarter plane, with either fixed or varying starting and end point. The original motivation of this work was the observation (by Bill Sands) that the number of such 4-directional walks of length \(n\) starting from the origin and remaining in the upper half-plane is \(\binom {2n+1}n\). Most of the results are proven by inductive arguments. These were ``replaced'' by combinatorial (mostly bijective) ones in the above mentioned article [loc. cit.], where also more general results were derived. The preprint comes with the bonus of an addendum where (some of) the proofs from that article are sketched, and of a long annotated bibliography on lattice path counting up to 1990. Reviewer's remark: The reader must be warned that the preprint is not brought up to date. In particular, all the open problems that are mentioned are solved (with the possible exception of one). More precisely, a bijective proof of (14) results from the bijection between the 4-directional walks in the first quadrant which start at \((0,0)\) and the union of two sets of 4-directional walks given in [loc. cit., pp.~10/11], if composed with the bijection between 4-directional walks and up-down lattice paths (see the proof of (1.2) in [loc. cit.]). Furthermore, for the formula for \(w'_{2n-1}(0,1)\) there is a (highly nontrivial) bijective proof in [\textit{R.~Cori, S.~Dulucq} and \textit{X.~Viennot}, J. Comb. Theory, Ser. A 43, 1--22 (1986; Zbl 0662.05004)]. Finally, regarding \(w'_n(y)\) (the number of four-directional walks in the first quadrant starting at the origin and ending at height \(y\)), one must mention that in [loc. cit.] a bijective proof for the counting formula for such paths which end at height \textit{at least} \(y\) is given (see (2.10) in [loc. cit.]). This can be probably made into a purely bijective proof for the formula for \(w'_n(y)\) itself.