The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
William Elliot

Posts: 2,637
Registered: 1/8/12
Re: Number of lattice paths with given steps?
Posted: Nov 22, 2012 9:44 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Thu, 22 Nov 2012, IV wrote:
> "William Elliot" wrote in

> > > > 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. Was this
> > > > problem already discussed in the literature?

> I mean only lattice paths, not lattice walks.
> Fray, R. D.; Roselle, D. P.: Weighted lattice paths. Pacific J. Math. 37

Weighted paths don't apply.

> 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 notation is inconsistent unto usless meaningless.

> The lattice paths with n1 steps (1,1), n2 steps (1,2), n3 steps (1,3), ... and

Is (1,1) in the x direction or the y direction?
Is (1,2) in the x direction or the y direction?
Is (1,3) in the x direction or the y direction?

What ever the direction, does the first 1 means a single
step from one point to an adjecent point?

> 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?

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.