LatticePaths

The monotone lattice paths from $(0,0)$ to $(a,b)$ using unit north/east steps, each written as a $0/1$ step sequence ($1$ = north). Count $\binom{a+b}{a}$.

✓ checked against that system · ! checked, with disagreements (hover a chip)OEISA046899✓↗

LatticePaths(a, b)the monotone north/east lattice paths in an $a \times b$ grid

Typed signatures

Type	Package	Applies
(integer<0..>, integer<0..>) -> indexed_collection<list<integer>>	combinatorics	always

Domain: Collections

Definition

Epsil, as the implementation runs it.

count(_a, _b)

Binomial(_a + _b, _a) if 0 <= _a && _a <= _a + _b else 0

unrank(_a, _b, _r)

Drop(Fold(Function(Apply(
                          (lu_o: integer) => Join([
                                                    lu_s[1] - lu_o,
                                                    lu_s[2] - 1,
                                                    1,
                                                  ], Drop(lu_s, 2)) if lu_s[1] >=
                                                                      lu_o else Join(
                                                                                  [lu_s[1], lu_s[2], 0],
                                                                                  Drop(lu_s, 2),
                                                                                ),
                          Binomial(lu_j - 1, lu_s[2]) if 0 <= lu_s[2] && lu_s[2] <=
                                                                         lu_j -
                                                                         1 else 0,
                        ), lu_s, lu_j), [_r, _a], Range(_a + _b, 1, -1)), 2)

rank(_a, _b, _x)

Fold(Function([
                lr_s[1] +
                ((Binomial(lr_s[3] - 1, lr_s[2] + 1) if 0 <= lr_s[2] + 1 && lr_s[2] +
                                                                            1 <=
                                                                            lr_s[3] -
                                                                            1 else 0) if lr_t == 1 else 0),
                lr_s[2] + (1 if lr_t == 1 else 0),
                lr_s[3] + 1,
              ], lr_s, lr_t), [0, 0, 1], _x)[1]

valid(_a, _b, _x)

Length(_x) == _a + _b && Fold(Function(
                                        ok_lv_t && 0 <= lv_t && lv_t <= 1,
                                        ok_lv_t,
                                        lv_t,
                                      ), True, _x) && Fold(Function(
                                                                    lv_c + lv_u,
                                                                    lv_c,
                                                                    lv_u,
                                                                  ), 0, _x) == _a

Examples

Basic #

$\binom{5}{3} = 10$

live ↗

In$\mathrm{Count}(\mathrm{LatticePaths}(3, 2))$Out$10$

$1$ = north

live ↗

In$\mathrm{Take}(\mathrm{LatticePaths}(2, 2), 6)$Out$\bigl\lbrack\bigl\lbrack1, 1, 0, 0\bigr\rbrack, \bigl\lbrack1, 0, 1, 0\bigr\rbrack, \bigl\lbrack0, 1, 1, 0\bigr\rbrack, \bigl\lbrack1, 0, 0, 1\bigr\rbrack, \bigl\lbrack0, 1, 0, 1\bigr\rbrack, \bigl\lbrack0, 0, 1, 1\bigr\rbrack\bigr\rbrack$

About

Examples	2
Crosswalk	OEIS

See also: PartitionsInBox