Lattice path

⁠ of length k with steps in the set S, is a sequence of vectors ⁠

An example of a lattice path in ⁠

s. NE lattice paths most commonly begin at the origin.

This convention allows encoding all the information about a NE lattice path

in a single permutation word.

The length of the word gives the number of steps of the lattice path,

s in the word determines the end point of

If the permutation word for a NE lattice path contains

Lattice paths are often used to count other combinatorial objects.

Similarly, there are many combinatorial objects that count the number of lattice paths of a certain kind.

This occurs when the lattice paths are in bijection with the object in question.

For example, NE lattice paths have close connections to the number of combinations, which are counted by the binomial coefficient, and arranged in Pascal's triangle.

The diagram below demonstrates some of these connections.

The number of lattice paths from

is equal to the binomial coefficient

If one rotates the diagram 135° clockwise about the origin and extends it to include all

, then one obtains Pascal's triangle.

row of Pascal's Triangle is the binomial coefficient

The graphical representation of NE lattice paths lends itself to many bijective proofs involving combinations.

Proof: The right-hand side is equal to the number of NE lattice paths from

Each of these NE lattice paths intersects exactly one of the lattice points in the rectangular array with coordinates

: Every NE lattice path from

intersects exactly one of the colored nodes.

On the left-hand side, the binomial coefficient squared,

, represents two copies of the set of NE lattice paths from

Rotating the second copy 90° clockwise does not change the combinatorics of the object:

So the total number of lattice paths remains the same.

Superimpose the NE lattice paths squared onto the same rectangular array, as seen in the figure below.

We see that all NE lattice paths from

In particular, any lattice path passing through the red lattice point (for example) is counted by the squared set of lattice paths (also shown in red).