MotzkinPathsByPeaks
Motzkin paths of length with exactly peaks — an up-step immediately followed by a down-step.
OEIS
A055151MotzkinPathsByPeaks(n, k)Motzkin paths of length with exactly peaks — an up-step immediately followed by a down-stepTyped signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>, integer<0..>) -> indexed_collection<motzkin_path> | combinatorics | always |
Details
- Row is the Motzkin triangle (A055151); rows sum to the Motzkin numbers (A001006).
Definition
Epsil, as the implementation runs it.
count(_n, _k)
Apply((pc: integer) => Apply((pu: integer) => 0 if pc > _k || 0 > (_n - _n % 2) /
2 else _tables[_n *
((_n -
_n % 2) /
2 +
1) *
(_k + 1) +
0 *
(_k + 1) +
(_k - pc) +
1] -
(_tables[(_n - 1) *
((_n -
_n % 2) /
2 +
1) *
(_k + 1) +
(0 - 1) *
(_k + 1) +
(_k - pc) +
1] -
(_tables[(_n - 1) *
((_n -
_n % 2) /
2 +
1) *
(_k + 1) +
(0 - 1) *
(_k + 1) +
(_k - pc -
1) +
1] if _k - pc >=
1 else 0) if pu ==
1 &&
0 >
0 &&
_n >=
1 else 0), 0 % 2), (0 -
0 % 2) /
2)unrank(_n, _k, _r)
Drop(Fold(Function(us if us[3] == 0 else Apply(
(uc0: integer) => Join(
[
us[1] -
0,
us[2] +
1,
us[3] -
1,
us[4] -
us[4] %
2 + 1,
],
Drop(us, 4),
[1],
) if us[1] <
uc0 else Apply(
(uc1: integer) => Join([
us[1] - uc0,
us[2] + 0,
us[3] - 1,
us[4] -
us[4] % 2,
], Drop(us, 4), [0]) if us[1] <
uc0 + uc1 else Join([us[1] -
(uc0 + uc1), us[2] - 1, us[3] - 1, us[4] +
us[4] % 2], Drop(us, 4), [-1]),
Apply(
(pc: integer) => Apply((pu: integer) => 0 if pc > _k ||
us[2] + 0 >
(_n -
_n % 2) /
2 else _tables[(us[3] - 1) *
((_n -
_n % 2) /
2 +
1) *
(_k + 1) +
(us[2] + 0) *
(_k + 1) +
(_k - pc) +
1] -
(_tables[(us[3] - 1 -
1) *
((_n -
_n % 2) /
2 +
1) *
(_k + 1) +
(us[2] + 0 -
1) *
(_k + 1) +
(_k - pc) +
1] -
(_tables[(us[3] - 1 -
1) *
((_n -
_n % 2) /
2 +
1) *
(_k + 1) +
(us[2] + 0 -
1) *
(_k + 1) +
(_k - pc -
1) +
1] if _k - pc >=
1 else 0) if pu == 1 &&
us[2] + 0 >
0 &&
us[3] - 1 >=
1 else 0), (us[4] -
us[4] % 2) %
2),
(us[4] -
us[4] % 2 -
(us[4] -
us[4] % 2) %
2) /
2,
) if 1 <= us[3] &&
us[2] + 0 >=
0 else 0,
),
Apply((pc: integer) => Apply(
(pu: integer) => 0 if pc > _k ||
us[2] + 1 >
(_n -
_n % 2) /
2 else _tables[(us[3] - 1) *
((_n -
_n % 2) /
2 +
1) *
(_k + 1) +
(us[2] + 1) *
(_k + 1) +
(_k - pc) +
1] -
(_tables[(us[3] - 1 -
1) *
((_n -
_n % 2) /
2 +
1) *
(_k + 1) +
(us[2] + 1 -
1) *
(_k + 1) +
(_k - pc) +
1] -
(_tables[(us[3] - 1 -
1) *
((_n -
_n % 2) /
2 +
1) *
(_k + 1) +
(us[2] + 1 -
1) *
(_k + 1) +
(_k - pc -
1) +
1] if _k - pc >=
1 else 0) if pu == 1 &&
us[2] + 1 >
0 &&
us[3] - 1 >=
1 else 0),
(us[4] -
us[4] %
2 +
1) %
2,
), (us[4] -
us[4] %
2 +
1 -
(us[4] -
us[4] % 2 +
1) %
2) /
2) if 1 <= us[3] &&
us[2] + 1 >=
0 else 0,
), us, ui), [_r, 0, _n, 0], Range(1, _n, 1)), 4)rank(_n, _k, _x)
Fold(Function(Apply(
(rc0: integer) => [
rs[1] + 0,
rs[2] + 1,
rs[3] - 1,
rs[4] - rs[4] % 2 + 1,
] if rx == 1 else Apply(
(rc1: integer) => [
rs[1] + rc0,
rs[2] + 0,
rs[3] - 1,
rs[4] -
rs[4] % 2,
] if rx == 0 else [
rs[1] +
rc0 + rc1,
rs[2] - 1,
rs[3] - 1,
rs[4] +
rs[4] % 2,
],
Apply(
(pc: integer) => Apply(
(pu: integer) => 0 if pc > _k ||
rs[2] + 0 >
(_n -
_n % 2) /
2 else _tables[(rs[3] - 1) *
((_n -
_n % 2) /
2 +
1) *
(_k + 1) +
(rs[2] + 0) *
(_k + 1) +
(_k - pc) +
1] -
(_tables[(rs[3] - 1 -
1) *
((_n -
_n % 2) /
2 +
1) *
(_k + 1) +
(rs[2] + 0 -
1) *
(_k + 1) +
(_k - pc) +
1] -
(_tables[(rs[3] - 1 -
1) *
((_n -
_n % 2) /
2 +
1) *
(_k + 1) +
(rs[2] + 0 -
1) *
(_k + 1) +
(_k - pc -
1) +
1] if _k - pc >=
1 else 0) if pu == 1 &&
rs[2] + 0 >
0 &&
rs[3] - 1 >=
1 else 0),
(rs[4] -
rs[4] % 2) %
2,
),
(rs[4] - rs[4] %
2 -
(rs[4] -
rs[4] %
2) % 2) / 2,
) if 1 <=
rs[3] && rs[2] +
0 >=
0 else 0,
),
Apply((pc: integer) => Apply((pu: integer) => 0 if pc > _k ||
rs[2] +
1 > (_n -
_n %
2) /
2 else _tables[(rs[3] - 1) *
((_n -
_n % 2) /
2 +
1) *
(_k + 1) +
(rs[2] + 1) *
(_k + 1) +
(_k - pc) +
1] -
(_tables[(rs[3] - 1 -
1) *
((_n -
_n % 2) /
2 +
1) *
(_k + 1) +
(rs[2] + 1 -
1) *
(_k + 1) +
(_k - pc) +
1] -
(_tables[(rs[3] - 1 -
1) *
((_n -
_n % 2) /
2 +
1) *
(_k + 1) +
(rs[2] + 1 -
1) *
(_k + 1) +
(_k - pc -
1) +
1] if _k - pc >=
1 else 0) if pu == 1 &&
rs[2] + 1 >
0 &&
rs[3] - 1 >=
1 else 0), (rs[4] -
rs[4] % 2 +
1) %
2), (rs[4] -
rs[4] % 2 +
1 -
(rs[4] -
rs[4] % 2 +
1) %
2) /
2) if 1 <= rs[3] &&
rs[2] + 1 >=
0 else 0,
), rs, rx), [0, 0, _n, 0], _x)[1]valid(_n, _k, _x)
Apply(
(ve: list<integer>) => ve[1] == 0 && ve[2] == _n && (ve[4] - ve[4] % 2) /
2 == _k,
Fold(
Function(vs if vs[1] < 0 else [
vs[1] + 1,
vs[2] + 1,
Max(vs[3], vs[1] + 1),
vs[4] - vs[4] % 2 + 1,
] if vx == 1 else [
vs[1] + 0,
vs[2] + 1,
Max(
vs[3],
vs[1] + 0,
),
vs[4] - vs[4] % 2,
] if vx == 0 else [
vs[1] -
1,
vs[2] +
1,
Max(vs[3], vs[1] - 1),
vs[4] +
vs[4] %
2,
] if vx == -1 else [-1, 0, 0, 0], vs, vx),
[0, 0, 0, 0],
_x,
),
)tables(_n, _k)
Fold(
Function(Join(pk_t, Fold(Function(
ReplaceAt(
pk_row,
pk_c + 1,
(pk_t[(pk_s - 1) * ((_n - _n %
2) /
2 + 1) *
(_k + 1) + ((pk_c -
pk_c %
(_k +
1)) /
(_k +
1) + 1) *
(_k +
1) + pk_c %
(_k +
1) +
1] -
(pk_t[(pk_s - 2) * ((_n - _n %
2) /
2 + 1) *
(_k + 1) + (pk_c -
pk_c %
(_k +
1)) /
(_k +
1) * (_k +
1) +
pk_c %
(_k +
1) + 1] -
(pk_t[(pk_s - 2) * ((_n -
_n %
2) / 2 +
1) * (_k +
1) +
(pk_c - pk_c % (_k +
1)) /
(_k + 1) * (_k + 1) + (pk_c %
(_k +
1) - 1) +
1] if pk_c % (_k + 1) >=
1 else 0) if pk_s >= 2 else 0) if (pk_c - pk_c % (_k + 1)) /
(_k + 1) + 1 <= (_n - _n % 2) /
2 else 0) +
pk_t[(pk_s - 1) * ((_n - _n %
2) /
2 + 1) *
(_k + 1) + (pk_c -
pk_c %
(_k +
1)) / (_k +
1) *
(_k + 1) + pk_c %
(_k +
1) + 1] +
(pk_t[(pk_s - 1) * ((_n - _n %
2) /
2 + 1) *
(_k + 1) + ((pk_c -
pk_c %
(_k +
1)) /
(_k +
1) - 1) *
(_k +
1) + pk_c %
(_k +
1) +
1] if (pk_c - pk_c % (_k +
1)) /
(_k + 1) > 0 else 0),
),
pk_row,
pk_c,
), Map(
Function(0, pk_z),
Range(
0,
((_n - _n % 2) / 2 + 1) *
(_k + 1) - 1,
1,
),
), Range(
0,
((_n - _n % 2) / 2 + 1) *
(_k + 1) - 1,
1,
))), pk_t, pk_s),
Fold(
Function(
ReplaceAt(pk_row, pk_c + 1, 1 if pk_c == 0 else 0),
pk_row,
pk_c,
),
Map(
Function(0, pk_z),
Range(0, ((_n - _n % 2) / 2 + 1) * (_k + 1) - 1, 1),
),
Range(0, ((_n - _n % 2) / 2 + 1) * (_k + 1) - 1, 1),
),
Range(1, _n + 1 - 1, 1),
)Enumeration
Examples
1 more kept as data, checked against the oraclesAbout
| Examples | 3 |
|---|---|
| Crosswalk | OEIS |
See also: DyckPaths