/ 
Math-NumSeq-73
River stage zero No dependents
/ Math::NumSeq::Catalan

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)!)

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

From the factorial expression it can be seen the values grow roughly as a power-of-4,

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

Odd

Option values_type => "odd" can give just the odd part of each number, ie. with 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 in C(i) is

num2s = (count-1-bits 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(i-1) * 2*(2i-1)/(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(i-1).

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 to next() 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 ignoring the denominator there and so simply taking

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

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/math-numseq/index.html

LICENSE

Copyright 2012, 2013, 2014, 2016, 2018 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/>.