IV
Posts:
185
Registered:
9/1/11


Re: Number of lattice paths with given steps?
Posted:
Nov 24, 2012 6:41 AM


"William Elliot" wrote in news:Pine.NEB.4.64.1211221837150.12160@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?
I already wrote: "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."
Let us look for all the unrestricted lattice paths of the task on the top above that begin at the point (0,0) and end at a point (n,k), n and k be nonnegative integers. (Without that I have thought about it, I assume: Also with no restriction of start point and end point, some statements on the lattice paths which are given by the general problem would be possible.)
I wrote: "Their number is m!/(n1!*n2!*...*nm!)." That was a typing error. Their number is n!/(n1!*n2!*...*nm!).
Thinking on the problem and reading some lattice path literature (after long, tiring and overtired working days in a complete other special scientific and nonscientific field, closed to the practice), I came to the conclusion: The description of compositions and of weak compositions of an integer was treated in MacMahon's chapter on bipartite(!) compositions of two integers (MacMahon 1915/1916).
The problem posed above on which I am interested in here is the description of the compositions of an integer that belong to a given partition of that integer. The solution of that problem only for the number of compositions or number of lattice paths is a simple combinatorial formula  the multinomial coefficient. Therefore it was presumably not worth to be treated in the literature. But I try to find by the presentation of the compositions as lattice paths a method for finding a generating formula for the lattice paths itself, for the compositions itself  not only for their number. But my problem above with given numbers of each kind of steps in the lattice should be treated somewhere in the lattice path literature.
Although, meanwhile I begin to fear that I thus will also only redirected to the detailed complete formal partition polynomials with uncertained formal variables u, s, t for the various property types of the individual compositions and partitions.
Can you help?

