scientific article; zbMATH DE number 1522339
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.
- On two related questions of Wilf concerning standard Young tableaux
- Preimages under the stack-sorting algorithm
- On the log-convexity of combinatorial sequences
- A criterion for the log-convexity of combinatorial sequences
- Oscillating rim hook tableaux and colored matchings
- New sufficient conditions for log-balancedness, with applications to combinatorial sequences
- Further results on paths in an \(n\)-dimensional cubic lattice
- scientific article; zbMATH DE number 812035 (Why is no real title available?)
- scientific article; zbMATH DE number 812072 (Why is no real title available?)
- scientific article; zbMATH DE number 7309235 (Why is no real title available?)
- Asymptotics of Selberg-like integrals: the unitary case and Newton's interpolation formula
- The log-behavior of the sequence for the partial sum of a log-convex sequence
- On some properties of generalized Narayana numbers
- Powers of Catalan generating functions for bounded operators
- Counting Lattice Walks in the Plane
- Moments of one-level densities in families of holomorphic cusp forms in the level aspect
- The signs of three-term recurrence sequences
- Two integer sequences related to Catalan numbers
- Low-lying zeros of L-functions with orthogonal symmetry
- Block-connected set partitions
- Riordan matrices and higher-dimensional lattice walks
- Anonymity, monotonicity, and quota pair systems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4510684)
