IV
Posts:
343
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. >>> Was this problem already discussed in the literature?
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) 8596: "The number, binomial(m+n,n), of unrestricted minimal lattice paths from (0,0) to (m,n) is an old and wellknown 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 xdirection and one move of length s in the ydirection, 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?

