Search All of the Math Forum:

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

Topic: Number of lattice paths with given steps?
Replies: 2   Last Post: Nov 30, 2012 3:38 PM

 Messages: [ Previous | Next ]
 James Waldby Posts: 539 Registered: 1/27/11
Re: Number of lattice paths with given steps?
Posted: Nov 28, 2012 3:34 PM

On Sat, 24 Nov 2012 12:41:39 +0100, IV wrote: ...
> 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?

>
> "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!).

That is the number of distinct ways to order the elements of the multiset
P = { 1*n1, 2*n2, 3*n3 ... m*nm}. Let T be the sum of the elements of P,
and let U = sum(n1, n2, ... nm). If a path from (0,0) has n1 steps of
form (1,1), n2 steps of form (1,2), and so forth, in some order, with
each step beginning where the previous step ends, then it is a path
from (0,0) to (U, T), and there are n!/(n1!*n2!*...*nm!) such paths.

From previous posts it seems obvious you already know all this. I've
merely introduced some names for things, for concreteness. What isn't
clear is what else you want to determine. You say (below) you want a
"description of the compositions of an integer that belong to a given
partition of that integer". It seems to me that given a partition of
an integer, expressed as a multiset P, the corresponding compositions
are merely all the distinct reorderings of the elements of P. Did you
have some other meaning in mind?

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

...
--
jiw

Date Subject Author
11/28/12 James Waldby
11/30/12 IV