DelannoyPaths

Lattice paths from $(0,0)$ to $(n,n)$ using East, North, and Diagonal steps.

OEISA001850↗

DelannoyPaths(n)Lattice paths from $(0,0)$ to $(n,n)$ using East, North, and Diagonal steps

Typed signatures

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

Domain: Collections

Details

• Count is the central Delannoy number (A001850).

Definition

Epsil, as the implementation runs it.

count(_n)

Fold(
      Function(
                dc_c + (Binomial(_n, dc_k) if 0 <= dc_k && dc_k <= _n else 0) *
                       (Binomial(_n, dc_k) if 0 <= dc_k && dc_k <= _n else 0) *
                       2 ^ dc_k,
                dc_c,
                dc_k,
              ),
      0,
      Range(0, Min(_n, _n), 1),
    )

unrank(_n, _r)

Drop(Fold(
           Function(du_s if du_s[2] == 0 && du_s[3] == 0 else Apply(
                                                                     (du_e: integer) => Apply(
                                                                                               (du_n: integer) => Join(
                                                                                                                        [du_s[1], du_s[2] - 1, du_s[3]],
                                                                                                                        Drop(du_s, 3),
                                                                                                                        [0],
                                                                                                                      ) if du_s[1] < du_e else Join(
                                                                                                                                                    [du_s[1] - du_e, du_s[2], du_s[3] - 1],
                                                                                                                                                    Drop(du_s, 3),
                                                                                                                                                    [1],
                                                                                                                                                  ) if du_s[1] <
                                                                                                                                                      du_e + du_n else Join([du_s[1] -
                                                                                                                                                                  (du_e + du_n), du_s[2] - 1, du_s[3] - 1], Drop(du_s, 3), [2]),
                                                                                               _tables[du_s[2] *
                                                                                                       (_n + 1) +
                                                                                                       (du_s[3] - 1) +
                                                                                                       1] if du_s[2] >= 0 &&
                                                                                                            du_s[3] - 1 >=
                                                                                                            0 else 0,
                                                                                             ),
                                                                     _tables[(du_s[2] -
                                                                              1) *
                                                                             (_n +
                                                                              1) +
                                                                             du_s[3] +
                                                                             1] if du_s[2] - 1 >=
                                                                                  0 &&
                                                                                  du_s[3] >= 0 else 0,
                                                                   ), du_s, du_j),
           [_r, _n, _n],
           Range(1, 2 * _n, 1),
         ), 3)

rank(_n, _x)

Fold(
      Function(
                Apply(
                       (dr_e: integer) => Apply(
                                                 (dr_n: integer) => [
                                                                      dr_s[1],
                                                                      dr_s[2] -
                                                                      1,
                                                                      dr_s[3],
                                                                    ] if dr_t ==
                                                                        0 else [
                                                                                dr_s[1] + dr_e,
                                                                                dr_s[2],
                                                                                dr_s[3] - 1,
                                                                              ] if dr_t == 1 else [
                                                                                                   dr_s[1] + dr_e + dr_n,
                                                                                                   dr_s[2] - 1,
                                                                                                   dr_s[3] - 1,
                                                                                                 ],
                                                 _tables[dr_s[2] * (_n + 1) +
                                                         (dr_s[3] - 1) + 1] if dr_s[2] >= 0 && dr_s[3] -
                                                                              1 >=
                                                                              0 else 0,
                                               ),
                       _tables[(dr_s[2] - 1) * (_n + 1) + dr_s[3] + 1] if dr_s[2] -
                                                                          1 >= 0 &&
                                                                          dr_s[3] >=
                                                                          0 else 0,
                     ),
                dr_s,
                dr_t,
              ),
      [0, _n, _n],
      _x,
    )[1]

valid(_n, _x)

Fold(Function(ok_dv_a && 0 <= dv_a && dv_a <= 2, ok_dv_a, dv_a), True, _x) &&
Fold(Function(dv_c + (0 if dv_t == 1 else 1), dv_c, dv_t), 0, _x) == _n && Fold(
                                                                                 Function(dv_c +
                                                                                          (0 if dv_t == 0 else 1), dv_c, dv_t),
                                                                                 0,
                                                                                 _x,
                                                                               ) ==
                                                                           _n

tables(_n)

Fold(
      Function(Join(
                     dt_t,
                     Fold(Function(ReplaceAt(
                                              dt_row,
                                              dt_c + 1,
                                              1 if dt_c == 0 else Fold(
                                                                        Function(dt_a +
                                                                                 dt_t[(dt_s - 1) *
                                                                                      (_n + 1) + dt_j + 1] +
                                                                                 dt_t[(dt_s - 1) *
                                                                                      (_n + 1) +
                                                                                      (dt_j - 1) +
                                                                                      1], dt_a, dt_j),
                                                                        1,
                                                                        Range(1, dt_c, 1),
                                                                      ),
                                            ), dt_row, dt_c), Map(
                                                                  Function(
                                                                            0,
                                                                            dt_z,
                                                                          ),
                                                                  Range(
                                                                         0,
                                                                         _n + 1 -
                                                                         1,
                                                                         1,
                                                                       ),
                                                                ), Range(
                                                                         0,
                                                                         _n + 1 -
                                                                         1,
                                                                         1,
                                                                       )),
                   ), dt_t, dt_s),
      Fold(
            Function(ReplaceAt(dt_row, dt_c + 1, 1), dt_row, dt_c),
            Map(Function(0, dt_z), Range(0, _n + 1 - 1, 1)),
            Range(0, _n + 1 - 1, 1),
          ),
      Range(1, _n + 1 - 1, 1),
    )

Enumeration

Examples

1 more kept as data, checked against the oracles

Basic #

$Count(DelannoyPaths(3)) = 63$

live ↗

In$\mathrm{Count}(\mathrm{DelannoyPaths}(3))$Out$63$

The first element in enumeration order

live ↗

In$\mathrm{DelannoyPaths}(3)[1]$Out${\operatorname{DelannoyPath}}([0, 0, 0, 1, 1, 1])$

About

Examples	3
Crosswalk	OEIS

See also: DyckPaths