Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Counting Lattice Paths

Subject: Counting Lattice Paths

From: Ulrik Nash

Date: 6 Jun, 2013 08:51:11

Message: 1 of 4

Perhaps some of you can help me on this one.

I need to display the different possible paths through a lattice in matrix form, where there is a row for each path, and where the columns contain 0 for left and 1 for right, so that the number of columns equals the size of the lattice.

For example, there are six paths through a 2x2 lattice:

[LLRR;LRLR;RLLR;LRRL;RLRL;RRLL] -->

[0 0 1 1;0 1 0 1;1 0 0 1;0 1 1 0;1 0 1 0;1 1 0 0]

I realize that the binomial coefficient provides the number of combinations, but I am interested in displaying the combinations using MatLab as described for further manipulation.

FYI: A good example of the Lattice Problem is here:

http://www.robertdickau.com/lattices.html

Subject: Counting Lattice Paths

From: Josh Meyer

Date: 6 Jun, 2013 14:08:31

Message: 2 of 4

The nchoosek() function displays combinations, and the perms() function
displays permutations in MATLAB.

Notice that the 1-norm of all paths for a given n x n lattice is constant
(for n=2 it is 4, for n=3 it is 6, etc...)

I'll tackle the n=2 case. If you use any vector of 0's and 1's whose
elements add to 2 (can never go three times in same direction since the
1-norm is conserved), then permutate the entries and find the unique rows,
you get the answer:

v = [0 1 0 1];
P = perms(v);
U = unique(P,'rows')

U =

     0 0 1 1
     0 1 0 1
     0 1 1 0
     1 0 0 1
     1 0 1 0
     1 1 0 0

As a check,

norm(U',1)

ans =

     2

For n=3, you could start with v = [0 0 0 1 1 1]. If you automate the
generation of v using the norm constraint, this could work for much larger
n.

"Ulrik Nash" <uwn@sam.sdu.dk> wrote in message
news:kopihv$eni$1@newscl01ah.mathworks.com...
> Perhaps some of you can help me on this one.
> I need to display the different possible paths through a lattice in matrix
> form, where there is a row for each path, and where the columns contain 0
> for left and 1 for right, so that the number of columns equals the size of
> the lattice.
>
> For example, there are six paths through a 2x2 lattice:
>
> [LLRR;LRLR;RLLR;LRRL;RLRL;RRLL] -->
>
> [0 0 1 1;0 1 0 1;1 0 0 1;0 1 1 0;1 0 1 0;1 1 0 0]
> I realize that the binomial coefficient provides the number of
> combinations, but I am interested in displaying the combinations using
> MatLab as described for further manipulation.
>
> FYI: A good example of the Lattice Problem is here:
> http://www.robertdickau.com/lattices.html

Subject: Counting Lattice Paths

From: Josh Meyer

Date: 6 Jun, 2013 14:19:48

Message: 3 of 4

> Notice that the 1-norm of all paths for a given n x n lattice is constant
> (for n=2 it is 4, for n=3 it is 6, etc...)
> As a check,
> norm(U',1)
> ans =
> 2
To be sure, this is all 'correct' but using 0's instead of -1's produces the
small discrepancy (getting 2 instead of 4):

v = [-1 -1 1 1];
.. .. .. .. .. ..
norm(U',1)

ans =

     4

Subject: Counting Lattice Paths

From: Ulrik Nash

Date: 6 Jun, 2013 20:07:09

Message: 4 of 4

"Josh Meyer" <jmeyer@mathworks.com> wrote in message <koq5q6$8jj$1@newscl01ah.mathworks.com>...
> > Notice that the 1-norm of all paths for a given n x n lattice is constant
> > (for n=2 it is 4, for n=3 it is 6, etc...)
> > As a check,
> > norm(U',1)
> > ans =
> > 2
> To be sure, this is all 'correct' but using 0's instead of -1's produces the
> small discrepancy (getting 2 instead of 4):
>
> v = [-1 -1 1 1];
> .. .. .. .. .. ..
> norm(U',1)
>
> ans =
>
> 4


Thank you so much Josh! I really appreciate your help. Kind regards, Ulrik.

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us