Math::N...:Catalan(3)

💖 Math::N...:Catalan(3) — User Contributed Perl Documentation 💖

okay bestie, buckle up, because we're doing Catalan numbers today and they are so much cuter than they sound 🎀. This lil page lives in the User Contributed Perl Documentation section of your manual, so it's giving community-contributed, hand-crafted, artisanal manpage energy ✨.

---

✨ NAME ✨

Math::NumSeq::Catalan — Catalan numbers (2n)! / (n!*(n+1)!) 💅

---

🌸 SYNOPSIS 🌸

use Math::NumSeq::Catalan;
my $seq = Math::NumSeq::Catalan->new;
my ($i, $value) = $seq->next;

that's it. that's the whole vibe. go forth and iterate 🦋

---

💜 DESCRIPTION 💜

So the Catalan numbers, right? They're literally this:

C(n) = binomial(2n,n) / (n+1)
     = (2n)! / (n!*(n+1)!)

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...  (A000108)
starting i=0

starting at i=0, no cap. and if you clock the factorial expression, you can see the values grow roughly like a power-of-4 situation, which is honestly iconic of them:

C(i) = C(i-1) * (2i)*(2i-1) / (i*(i+1))
C(i) = C(i-1) * 2*(2i-1)/(i+1)
     < C(i-1) * 4

so it's multiplying by something less than 4 every step, lowkey chill growth for such a dramatic formula 😭

---

🌈 Odd

okay so there's this option, values_type => "odd", and it gives you just the odd part of each number — like, with all the factors of 2 divided out 🧚

values_type => "odd"

1, 1, 1, 5, 7, 21, 33, 429, 715, 2431, 4199, ...  (A098597)
starting i=0

the number of 2s sitting inside C(i) is:

num2s = (count-1-bits of i+1) - 1

ngl that formula is a whole mood but it's accurate, bestie.

The odd part is always monotonically increasing. 💖 when i increments, num2s increases by at most 1 — like, a single factor of 2, that's it. and in the formula up there:

C(i) = C(i-1) * 2*(2i-1)/(i+1)

you can see that C(i) gains at least 1 factor of 2, so after you divide out 2^num2s it's still greater than C(i-1). math said "monotonic" and meant it, periodt 💅

---

👑 FUNCTIONS 👑

heads up: for behaviour common to all the sequence classes, go check "FUNCTIONS" in Math::NumSeq 🫶

• $seq = Math::NumSeq::Catalan->new ()
• $seq = Math::NumSeq::Catalan->new (values_type => $str)

Create and return a new sequence object. that's your main character constructor moment ✨

---

⭐ Iterating

• $seq->seek_to_i($i) — moves the current sequence position to $i. the next call to next() will return $i and its corresponding value. it's giving teleportation 🦋

---

🔥 Random Access

• $value = $seq->ith($i) — return the $i'th value. just grab it directly, no scrolling required 💅
• $i = $seq->value_to_i_estimate($value) — returns an estimate of the i corresponding to $value (emphasis on estimate, she's approximating).

the current code is based on:

C(n) ~= 4^n / (sqrt(pi*n)*(n+1))

but it ignores the denominator there and so simply takes:

C(n) ~= 4^n
hence i ~= log4(value)

the 4^n term dominates for medium to large $value — and that's true for both plain and "odd" 🎀

---

🌟 SEE ALSO 🌟

• Math::NumSeq
• Math::NumSeq::Factorials
• Math::NumSeq::BalancedBinary

go read them, they're all friends, it's a whole squad 💜

---

🌈 HOME PAGE 🌈

<http://user42.tuxfamily.org/math-numseq/index.html>

---

🎀 LICENSE 🎀

Copyright 2012, 2013, 2014, 2016, 2018, 2019, 2020 Kevin Ryde

Math-NumSeq is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. 👀

You should have received a copy of the GNU General Public License along with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.

fr fr, read the license, it's the whole point of free software 💖

---

and that's the page, bestie!! 🫶 this was perl v5.42.0, dated 2025-07-25, and honestly? iconic of it. slay, go compute some Catalan numbers, you've got this 👑💅✨