Counting pattern avoiding ballot paths begins with a careful analysis of the pattern. Not the length, but the characteristics of the pattern are responsible for the difficulties in finding explicit ...solutions. Certain features, like overlap and difference in number of
→
and
↑
steps determine the solution of the recursion formula. If the recursion can be solved by a polynomial sequence, we apply the Finite Operator Calculus to find an explicit form of the solution in terms of binomial coefficients.
The purpose of this work is to extend
the theory of finite operator calculus to the multivariate setting, and
apply it to the enumeration of certain lattice paths. The lattice paths we
consider are ...ballot paths. A ballot path is a path that stays weakly above
the diagonal
, starts at the origin, and takes steps from the set
. Given a string
from the set
, we want to count the ballot paths with a given number of
occurrences of
. In order to use finite operator calculus, we must put
some restrictions on the string
we wish to keep track of. A ballot path
ending on the diagonal can be viewed as a Dyck path, thus all of our results
also apply to the enumeration of Dyck paths with a given number of
occurrences of
. Finally, we give an example of counting ballot paths
with a given number of occurrences of two patterns.
Random walks in octants, and related structures Niederhausen, Heinrich
Journal of statistical planning and inference,
11/2005, Letnik:
135, Številka:
1
Journal Article, Conference Proceeding
Recenzirano
A diffusion walk in
Z
2
is a (random) walk with unit step vectors
→
,
↑
,
←
, and
↓
. Particles from different sources with opposite charges cancel each other when they meet in the lattice. This ...cancellation principle is applied to enumerate diffusion walks in shifted half-planes, quadrants, and octants (a three-dimensional version is also considered). Summing over time we calculate expected numbers of visits and first passage probabilities. Comparing those quantities to analytically obtained expressions leads to interesting identities, many of them involving integrals over products of Chebyshev polynomials of the first and second kind. We also explore what the expected number of visits means when the diffusion in an octant is bijectively mapped onto other combinatorial structures, like pairs of non-intersecting Dyck paths, vicious walkers, bicolored Motzkin paths, staircase polygons in the second octant, and
{
→
↑
}
-paths confined to the third hexadecant enumerated by left turns.
We give a short history of the so-called tennis ball problem, and discuss its relation to lattice path enumeration. We also prove a conjecture related to a solution of the symmetric case, namely when ...the number of balls removed each turn is exactly half the number inserted.
Catalan Traffic at the Beach Niederhausen, Heinrich
The Electronic journal of combinatorics,
01/2002, Letnik:
9, Številka:
1
Journal Article
Recenzirano
We design a lattice path problem in ${\bf Z}^{2}$ (the Catalan traffic) with step set $\{\rightarrow,\uparrow\}$ strictly above the line $y=( x-1) /2$, and with step set $\{\downarrow,\searrow\}$ ...below that same line, except for the gates at $(2y,y)$ (with $\{\uparrow,\downarrow ,\searrow\}$-steps) and the closed intersections at $( 2y+1,y) $ (no traffic). The step sets prevent any traffic from going below the diagonal $y=-x$ (the beach). If we denote by $t(n,m)$ the number of paths from the origin to $(n,m)$, then the ubiquitous Catalan numbers $C_{n}={{2n}\choose {n}}/ ( n+1) $ occur as $t( n,-n) $ along the beach. We prove this with the help of hypergeometric identities, and also by solving an equivalent lattice path problem. On the way we pick up several identities and discuss other known sequences of numbers occurring in the Catalan traffic scheme, like the Motzkin numbers in row $m=-1$, and the "Tri-Catalan numbers" $1,1,3,12,55,\dots$ at the gates.
We enumerate two-dimensional walks inside a band parallel to an axis of symmetry, using an algebraic approach. The restrictions along the boundary lines can be more complicated than just initial ...values of zeroes; we consider
recursive initial values prescribing which predecessors a position at the boundary can have. More general, the initial conditions are expressed by certain linear operators which vanish along the axis of symmetry.
We consider certain systems of linear operator equations where the
nth-order solution is made unique by an initial value taken from the preceding solution. Such conditions arise in the enumeration of ...lattice paths with weighted left turns, if the paths are restricted by a lower linear barrier of integer slope.
PDF
