CatalanNumbers

The Catalan numbers $1, 1, 2, 5, 14, 42, …$ as a lazy indexed collection.

WikipediaCatalan numberMathWorldCatalanNumberWikidataQ270513nLabCatalan numberDLMF26.5.E1OEISA000108Wolfram LanguageCatalanNumberSageMathsage.combinat.combinat.catalan_number(n)mathlib4catalan

CatalanNumbers

C_n = \binom{2n}{n}/(n+1)

, an infinite indexed collection.

Domain: Collections

Details

A lazy indexed collection: $Count(CatalanNumbers) = +\infty$ , and $At(CatalanNumbers, k)$ unranks $C_{k-1}$ exactly (bigint arithmetic; $C_{30}$ already exceeds $2^{53}$ ) -- $At(CatalanNumbers, 1) = C_0 = 1$ .
OEIS A000108, starting exactly at its offset-0 term: $1, 1, 2, 5, 14, 42, 132, …$ ; counts balanced parenthesizations, binary trees, Dyck paths and more.
Membership goes through Element: $Element(14, CatalanNumbers)$ is true, $Element(10, CatalanNumbers)$ is false.

Definition

Epsil, as the implementation runs it.

count()

PositiveInfinity

unrank(_r)

Fold(Function([Apply(
                      (ct_g: integer) => Apply((ct_m: integer) => Apply(
                                                                         (ct_q: integer) => Apply(
                                                                                                   (ct_u: integer) => ct_q * ct_u,
                                                                                                   (4wk_n + 2) /
                                                                                                   ct_g,
                                                                                                 ),
                                                                         wk_w[1] /
                                                                         ct_m,
                                                                       ), (wk_n +
                                                                          2) /
                                                                         ct_g),
                      GCD(4wk_n + 2, wk_n + 2),
                    )], wk_w, wk_n), [1], Range(0, _r - 1, 1))[1]

rank(_x)

Fold(
      Function(wk_w if wk_n >= 0 && wk_w[1] > _x else [Apply(
                                                              (ct_g: integer) => Apply(
                                                                                        (ct_m: integer) => Apply((ct_q: integer) => Apply(
                                                                                                                                           (ct_u: integer) => ct_q * ct_u,
                                                                                                                                           (4wk_n + 2) /
                                                                                                                                           ct_g,
                                                                                                                                         ), wk_w[1] / ct_m),
                                                                                        (wk_n + 2) /
                                                                                        ct_g,
                                                                                      ),
                                                              GCD(
                                                                   4wk_n + 2,
                                                                   wk_n + 2,
                                                                 ),
                                                            ), wk_n if wk_w[2] <
                                                                      0 && wk_w[1] ==
                                                                          _x else wk_w[2]], wk_w, wk_n),
      [1, -1],
      Range(
             0,
             1 * (Apply(
                         (fl_r: list<integer>) => fl_r[2],
                         Fold(Function(
                                        [
                                          (fl_s[1] - fl_s[1] % 2 ^ fl_k) / 2 ^
                                                                           fl_k,
                                          fl_s[2] + fl_k,
                                        ] if fl_s[1] >= 2 ^ fl_k else fl_s,
                                        fl_s,
                                        fl_k,
                                      ), [_x + 2, 0], [
                                                       8_192,
                                                       4_096,
                                                       2_048,
                                                       1_024,
                                                       512,
                                                       256,
                                                       128,
                                                       64,
                                                       32,
                                                       16,
                                                       8,
                                                       4,
                                                       2,
                                                       1,
                                                     ]),
                       ) + 1) + 12,
             1,
           ),
    )[2] if _x >= 0 else -1

valid(_x)

Fold(
      Function(wk_w if wk_n >= 0 && wk_w[1] > _x else [Apply(
                                                              (ct_g: integer) => Apply(
                                                                                        (ct_m: integer) => Apply((ct_q: integer) => Apply(
                                                                                                                                           (ct_u: integer) => ct_q * ct_u,
                                                                                                                                           (4wk_n + 2) /
                                                                                                                                           ct_g,
                                                                                                                                         ), wk_w[1] / ct_m),
                                                                                        (wk_n + 2) /
                                                                                        ct_g,
                                                                                      ),
                                                              GCD(
                                                                   4wk_n + 2,
                                                                   wk_n + 2,
                                                                 ),
                                                            ), wk_n if wk_w[2] <
                                                                      0 && wk_w[1] ==
                                                                          _x else wk_w[2]], wk_w, wk_n),
      [1, -1],
      Range(
             0,
             1 * (Apply(
                         (fl_r: list<integer>) => fl_r[2],
                         Fold(Function(
                                        [
                                          (fl_s[1] - fl_s[1] % 2 ^ fl_k) / 2 ^
                                                                           fl_k,
                                          fl_s[2] + fl_k,
                                        ] if fl_s[1] >= 2 ^ fl_k else fl_s,
                                        fl_s,
                                        fl_k,
                                      ), [_x + 2, 0], [
                                                       8_192,
                                                       4_096,
                                                       2_048,
                                                       1_024,
                                                       512,
                                                       256,
                                                       128,
                                                       64,
                                                       32,
                                                       16,
                                                       8,
                                                       4,
                                                       2,
                                                       1,
                                                     ]),
                       ) + 1) + 12,
             1,
           ),
    )[2] >= 0 if _x >= 0 else False

Enumeration

Examples

1 more kept as data, checked against the oracles

About

Examples	1
Crosswalk	Wikipedia MathWorld Wikidata nLab DLMF OEIS Wolfram Language SageMath mathlib4

CatalanNumbers ​

Definition

Enumeration

Examples

CatalanNumbers