LukasiewiczPaths

Łukasiewicz paths: length-$(n+1)$ integer words $a_0, …, a_n$ (each $\ge -1$) whose prefix sums stay $\ge 0$ and end at $-1$.

OEISA000108↗

LukasiewiczPaths(n)Łukasiewicz paths: length-$(n+1)$ integer words $a_0, …, a_n$ (each $\ge -1$) whose prefix sums stay $\ge 0$ and end at $-1$

Typed signatures

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

Domain: Collections

Details

• Count is the Catalan number $C_n$ (A000108); in bijection with plane trees on $n$ edges via the preorder child-count word.

Definition

Epsil, as the implementation runs it.

count(_n)

Apply((bd: integer) => 0 if 2 * _n < 0 || (2 * _n - 0) % 2 == 1 else Binomial(2 *
                                                                              _n, bd) -
                                                                     (0 if bd ==
                                                                           0 else Binomial(2 * _n, bd - 1)), (2 * _n -
                                                                        0 - (2 *
                                                                            _n - 0) %
                                                                           2) / 2)

unrank(_n, _r)

Apply(
       (lu_p: list<integer>) => Apply(
                                       (wc_f: list<integer>) => Join([wc_f[3] -
                                                                      1], Drop(
                                                                               wc_f,
                                                                               3 +
                                                                               2 *
                                                                               (_n + 1),
                                                                             )),
                                       Fold(
                                             Function(Apply((wc_t: list<integer>) => ReplaceAt(
                                                                                                ReplaceAt(ReplaceAt(
                                                                                                                     ReplaceAt(
                                                                                                                                ReplaceAt(wc_t, 1, wc_t[1] + 1),
                                                                                                                                2,
                                                                                                                                wc_t[2] + 1,
                                                                                                                              ),
                                                                                                                     3 + wc_t[1],
                                                                                                                     wc_t[3 + wc_t[1]] +
                                                                                                                     1,
                                                                                                                   ), 3 +
                                                                                                                     wc_t[1] + 1, 0),
                                                                                                3 +
                                                                                                _n + 1 +
                                                                                                wc_t[1] + 1,
                                                                                                wc_t[2] + 1,
                                                                                              ) if wc_u == 1 else ReplaceAt(
                                                                                                                            ReplaceAt(wc_t, 1, wc_t[1] - 1),
                                                                                                                            3 +
                                                                                                                            2 *
                                                                                                                            (_n + 1) +
                                                                                                                            wc_t[3 +
                                                                                                                                 _n + 1 +
                                                                                                                                 wc_t[1]],
                                                                                                                            wc_t[3 + wc_t[1]] -
                                                                                                                            1,
                                                                                                                          ), wc_s), wc_s, wc_u),
                                             Join(
                                                   [0, 0],
                                                   Map(
                                                        Function(0, wc_z),
                                                        Range(
                                                               1,
                                                               3 * (_n + 1),
                                                               1,
                                                             ),
                                                      ),
                                                 ),
                                             lu_p,
                                           ),
                                     ),
       Drop(Fold(Function(us if us[3] == 0 else Apply(
                                                       (uc0: integer) => Join(
                                                                               [
                                                                                 us[1] - 0,
                                                                                 us[2] + 1,
                                                                                 us[3] - 1,
                                                                                 1,
                                                                               ],
                                                                               Drop(us, 4),
                                                                               [1],
                                                                             ) if us[1] < uc0 else Join([
                                                                                                         us[1] - uc0,
                                                                                                         us[2] - 1,
                                                                                                         us[3] - 1,
                                                                                                         1,
                                                                                                       ], Drop(us, 4), [0]),
                                                       Apply(
                                                              (bd: integer) => 0 if us[3] - 1 <
                                                                                    us[2] + 1 ||
                                                                                    (us[3] - 1 -
                                                                                     (us[2] + 1)) %
                                                                                    2 ==
                                                                                    1 else Binomial(us[3] - 1, bd) -
                                                                                          (0 if bd == 0 else Binomial(us[3] - 1, bd - 1)),
                                                              (us[3] - 1 - (us[2] +
                                                                            1) - (us[3] - 1 -
                                                                                 (us[2] + 1)) %
                                                                                2) /
                                                              2,
                                                            ) if 1 <= us[3] && us[2] +
                                                                              1 >=
                                                                              0 else 0,
                                                     ), us, ui), [
                                                                  _r,
                                                                  0,
                                                                  2 * _n,
                                                                  1,
                                                                ], Range(1, 2 *
                                                                           _n, 1)), 4),
     )

rank(_n, _x)

Apply(
       (lr_x: list<integer>) => Fold(Function(Apply(
                                                     (rc0: integer) => [
                                                                         rs[1] +
                                                                         0,
                                                                         rs[2] +
                                                                         1,
                                                                         rs[3] -
                                                                         1,
                                                                         1,
                                                                       ] if rx ==
                                                                           1 else [
                                                                                   rs[1] + rc0,
                                                                                   rs[2] - 1,
                                                                                   rs[3] - 1,
                                                                                   1,
                                                                                 ],
                                                     Apply(
                                                            (bd: integer) => 0 if rs[3] - 1 <
                                                                                  rs[2] + 1 ||
                                                                                  (rs[3] - 1 -
                                                                                   (rs[2] + 1)) %
                                                                                  2 ==
                                                                                  1 else Binomial(rs[3] - 1, bd) -
                                                                                        (0 if bd == 0 else Binomial(rs[3] - 1, bd - 1)),
                                                            (rs[3] - 1 - (rs[2] +
                                                                          1) - (rs[3] -
                                                                               1 -
                                                                               (rs[2] + 1)) %
                                                                              2) /
                                                            2,
                                                          ) if 1 <= rs[3] && rs[2] +
                                                                            1 >=
                                                                            0 else 0,
                                                   ), rs, rx), [0, 0, 2 * _n, 1], lr_x)[1],
       Apply((cw_q: list<integer>) => Apply(
                                             (cw_d: list<integer>) => Map(
                                                                           Function(Fold(
                                                                                          Function(cw_c +
                                                                                                   (1 if 2cw_i - cw_d[cw_i] ==
                                                                                                         cw_t else 0), cw_c, cw_i),
                                                                                          0,
                                                                                          Range(1, _n, 1),
                                                                                        ), cw_t),
                                                                           Range(
                                                                                  1,
                                                                                  2 * _n,
                                                                                  1,
                                                                                ),
                                                                         ),
                                             Map(
                                                  Function(Fold(
                                                                 Function(
                                                                           [
                                                                             cw_q[cw_m],
                                                                             cw_s[2] +
                                                                             1,
                                                                           ] if cw_q[cw_m] <=
                                                                               cw_s[1] else cw_s,
                                                                           cw_s,
                                                                           cw_m,
                                                                         ),
                                                                 [
                                                                   cw_q[cw_k + 1],
                                                                   0,
                                                                 ],
                                                                 Range(
                                                                        cw_k,
                                                                        1,
                                                                        -1,
                                                                      ),
                                                               )[2], cw_k),
                                                  Range(1, _n, 1),
                                                ),
                                           ), Fold(
                                                   Function(Join(
                                                                  cw_p,
                                                                  [cw_p[Length(cw_p)] +
                                                                   cw_a],
                                                                ), cw_p, cw_a),
                                                   [0],
                                                   _x,
                                                 )),
     )

valid(_n, _x)

Length(_x) == _n + 1 && Fold(Function(
                                       -1 if lv_s <= 0 || lv_a < -1 else lv_s +
                                                                         lv_a,
                                       lv_s,
                                       lv_a,
                                     ), 1, _x) == 0

Enumeration

Examples

1 more kept as data, checked against the oracles

Basic #

$Count(LukasiewiczPaths(4)) = 14$

live ↗

In$\mathrm{Count}(\mathrm{LukasiewiczPaths}(4))$Out$14$

The first element in enumeration order

live ↗

In$\mathrm{LukasiewiczPaths}(4)[1]$Out${\operatorname{LukasiewiczPath}}([0, 0, 0, 0, -1])$

About

Examples	3
Crosswalk	OEIS

See also: DyckPaths