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;
DESCRIPTION
The Catalan numbers
C(n) = binomial(2n,n) / (n+1)
= (2n)! / (n!*(n+1)!)
# starting i=0
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...
From the factorial expression it can be seen the values grow roughly as a powerof4,
C(i) = C(i1) * (2i)*(2i1) / (i*(i+1))
C(i) = C(i1) * 2*(2i1)/(i+1)
< C(i1) * 4
Odd
Option values_type => "odd"
can give just the odd part of each number, ie. with factors of 2 divided out,
values_type => "odd"
# starting i=0
1, 1, 1, 5, 7, 21, 33, 429, 715, 2431, 4199, ...
The number of 2s in C(i) is
num2s = (count1bits of i+1)  1
The odd part is always monotonically increasing. When i increments num2s increases by at most 1, ie. a single factor of 2. In the formula above
C(i) = C(i1) * 2*(2i1)/(i+1)
it can be seen that C(i) gains at least 1 factor of 2, so after dividing out 2^num2s it's still greater than C(i1).
FUNCTIONS
See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence classes.
$seq = Math::NumSeq::Catalan>new ()
$seq = Math::NumSeq::Catalan>new (values_type => $str)

Create and return a new sequence object.
Iterating
$seq>seek_to_i($i)

Move the current sequence position to
$i
. The next call tonext()
will return$i
and its corresponding value.
Random Access
$value = $seq>ith($i)

Return the
$i
'th value. $i = $seq>value_to_i_estimate($value)

Return an estimate of the i corresponding to
$value
.The current code is based on C(n) ~= 4^n / (sqrt(pi*n)*(n+1)), but estimating simply i=log4(value) since the 4^n term dominates for medium to large
$value
(for both plain and "odd").
SEE ALSO
Math::NumSeq, Math::NumSeq::Factorials, Math::NumSeq::BalancedBinary
HOME PAGE
http://user42.tuxfamily.org/mathnumseq/index.html
LICENSE
Copyright 2012, 2013 Kevin Ryde
MathNumSeq 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.
MathNumSeq 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 MathNumSeq. If not, see <http://www.gnu.org/licenses/>.