IV
Posts:
51
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 x-direction
and one move of length s in the y-direction, 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 non-scientific 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 re-directed
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?
|
|
