Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Number of lattice paths with given steps?
Replies: 7   Last Post: Nov 24, 2012 6:41 AM

 Messages: [ Previous | Next ]
 IV Posts: 356 Registered: 9/1/11
Re: Number of lattice paths with given steps?
Posted: Nov 22, 2012 2:20 PM

"William Elliot" wrote in
news:Pine.NEB.4.64.1211211817090.2445@panix1.panix.com...
IV wrote:
>>> I'm looking for a formula for calculating the number of lattice paths
>>> in a rectangular quadratic integer lattice with given kind of steps and
>>> given numbers of steps of each kind.
>>> That means all lattice paths with n1 steps (1,1), n2 steps (1,2), n3
>>> steps
>>> (1,3) and so on - the numbers n1, n2, n3, ... are given.

IV wrote:
>> Please concentrate your mind on this: I assume, the problem of given
>> numbers of steps of each kind is a new quality of lattice path problems.
>> Has someone experiences, literature references or ideas for this kind of
>> problems?

> Who's to know what your talking about when you don't define your terms?

I mean only lattice paths, not lattice walks.

Fray, R. D.; Roselle, D. P.: Weighted lattice paths. Pacific J. Math. 37
(1971) (1) 85-96: "The number, binomial(m+n,n), of unrestricted minimal
lattice paths from (0,0) to (m,n) is an old and well-known result, see
MacMahon (MacMahon, P. A.: Combinatory Analysis, 1915/1916) or Feller
(Feller, W.: An Introduction to Probability Theory and Its Applications,
1968)."

Ch. A. Charalambides: "Enumerative Combinatorics", 2002: "Consider an
orthogonal system of axes on the plane xy and the lattice defined by the
straight lines x=i, i=0,+-1, +-2,..., and y=j, j=0,+-1,+-2,..., that are
orthogonal to the (horizontal) axis x and the (vertical) axis y,
respectively. A directed polygonal line on the lattice that leads from the
point (r,s) to the point (n,k), r<=n, s<=k, through horizontal and vertical
straight sections, positively directed, is called lattice path (or, more
precisely, minimal lattice path) from the point (r,s) to the point (n,k)."

A step is a line from one lattice point to an adjacent lattice point.

My steps (1,y), better: (1,s), mean one move of length 1 in the x-direction
and one move of length s in the y-direction, s a nonnegative integer.

The lattice paths with n1 steps (1,1), n2 steps (1,2), n3 steps (1,3), ...
and nm steps (1,m) - the numbers n1, n2, n3, ... - nm are given, describe
the compositions of an integer n which belong to a given partition of the
integer n. Their number is m!/(n1!*n2!*...*nm!). If the lattice paths would
be not restricted, we can construct the binomial expression of their numbers
by summing up the numbers of a number triangle of the lattice path numbers,
e.g. Pascal's triangle. But how can we get a formula for the construction of
the single lattice paths which are restricted by my conditions above?

Date Subject Author
11/20/12 IV
11/20/12 William Elliot
11/21/12 IV
11/21/12 William Elliot
11/22/12 IV
11/22/12 William Elliot
11/24/12 IV
11/20/12 trj