1Math::NumSeq::Catalan(3U)ser Contributed Perl DocumentatiMoanth::NumSeq::Catalan(3)
2
3
4

NAME

6       Math::NumSeq::Catalan -- Catalan numbers (2n)! / (n!*(n+1)!)
7

SYNOPSIS

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

DESCRIPTION

14       The Catalan numbers
15
16           C(n) = binomial(2n,n) / (n+1)
17                = (2n)! / (n!*(n+1)!)
18
19           1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...  (A000108)
20           starting i=0
21
22       From the factorial expression it can be seen the values grow roughly as
23       a power-of-4,
24
25           C(i) = C(i-1) * (2i)*(2i-1) / (i*(i+1))
26           C(i) = C(i-1) * 2*(2i-1)/(i+1)
27                < C(i-1) * 4
28
29   Odd
30       Option "values_type => "odd"" can give just the odd part of each
31       number, ie. with factors of 2 divided out,
32
33           values_type => "odd"
34
35           1, 1, 1, 5, 7, 21, 33, 429, 715, 2431, 4199, ...  (A098597)
36           starting i=0
37
38       The number of 2s in C(i) is
39
40           num2s = (count-1-bits of i+1) - 1
41
42       The odd part is always monotonically increasing.  When i increments
43       num2s increases by at most 1, ie. a single factor of 2.  In the formula
44       above
45
46           C(i) = C(i-1) * 2*(2i-1)/(i+1)
47
48       it can be seen that C(i) gains at least 1 factor of 2, so after
49       dividing out 2^num2s it's still greater than C(i-1).
50

FUNCTIONS

52       See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
53       classes.
54
55       "$seq = Math::NumSeq::Catalan->new ()"
56       "$seq = Math::NumSeq::Catalan->new (values_type => $str)"
57           Create and return a new sequence object.
58
59   Iterating
60       "$seq->seek_to_i($i)"
61           Move the current sequence position to $i.  The next call to
62           "next()" will return $i and its corresponding value.
63
64   Random Access
65       "$value = $seq->ith($i)"
66           Return the $i'th value.
67
68       "$i = $seq->value_to_i_estimate($value)"
69           Return an estimate of the i corresponding to $value.
70
71           The current code is based on
72
73               C(n) ~= 4^n / (sqrt(pi*n)*(n+1))
74
75           but ignoring the denominator there and so simply taking
76
77               C(n) ~= 4^n
78               hence i ~= log4(value)
79
80           The 4^n term dominates for medium to large $value (for both plain
81           and "odd").
82

SEE ALSO

84       Math::NumSeq, Math::NumSeq::Factorials, Math::NumSeq::BalancedBinary
85

HOME PAGE

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

LICENSE

90       Copyright 2012, 2013, 2014, 2016, 2018, 2019, 2020 Kevin Ryde
91
92       Math-NumSeq is free software; you can redistribute it and/or modify it
93       under the terms of the GNU General Public License as published by the
94       Free Software Foundation; either version 3, or (at your option) any
95       later version.
96
97       Math-NumSeq is distributed in the hope that it will be useful, but
98       WITHOUT ANY WARRANTY; without even the implied warranty of
99       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
100       General Public License for more details.
101
102       You should have received a copy of the GNU General Public License along
103       with Math-NumSeq.  If not, see <http://www.gnu.org/licenses/>.
104
105
106
107perl v5.34.1                      2022-06-06          Math::NumSeq::Catalan(3)
Impressum