++ed by:
Kevin Ryde
and 1 contributors

# NAME

Math::NumSeq::Catalan -- factorials i! = 1*2*...*i

# SYNOPSIS

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

# DESCRIPTION

The Catalan numbers 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 power-of-4,

C(5) = 42 = 14 * 2*(2*5-1)/6

``````    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,

``    1, 1, 1, 5, 7, 21, 33, 429, 715, 2431, 4199, ...``

The number of 2s in C(i) is

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

When i increments this num2s increases by at most 1, which can eat the "2*" factor shown in the C(i) formula above. But because num2s doesn't increase by more than that the OddC(i) values are monotonically increasing.

# 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.

`\$seq->seek_to_i(\$i)`

Move the current sequence position to `\$i`. The next call to `next()` will return `\$i` and 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 just estimating i=log4(value) since the 4^n term dominates for medium to large `\$value` (for both plain and "odd").