combinat::catalan
--
Catalan numbers
combinat::catalan
(n) returns the n
-th Catalan number.
combinat::catalan(n)
n | - | nonnegative integer |
A positive integer.
combinat::catalan
(n) counts the Dyck words of size n
, the
ordered trees with n
nodes, the binary trees with n+1
nodes, the complete binary trees with 2n+1
nodes, the
standard tableaux with two rows of size n
,
the triangulations of a regular n+2
-gone, or the non-crossing
partitions of 1,2,...,n.
combinat::catalan
(n) is calculated using the formula catalan(n) = binomial(2*n,n) / (n+1)
We compute the 5-th Catalan number:
>> combinat::catalan(5)
42
Correct answer. But what was the question ?
We compute the first Catalan numbers:
>> combinat::catalan(n) $ n = 0..6
1, 1, 2, 5, 14, 42, 132
They coincide with the number of Dyck words:
>> combinat::dyckWords::count(n) $ n = 0..6
1, 1, 2, 5, 14, 42, 132
They also coincide with the numbers of tableaux with two rows or two columns of the same size:
>> 1, nops(combinat::tableaux::list([2 $ n])) $ n = 1..6;
1, nops(combinat::tableaux::list([n $ 2])) $ n = 1..6;
1, 1, 2, 5, 14, 42, 132 1, 1, 2, 5, 14, 42, 132
If one uses a wrong argument, an error message is returned
>> combinat::catalan(-1)
Error: Wrong type of 1. argument (type 'Type::NonNegInt' expec\ ted, got argument '-1'); during evaluation of 'combinat::catalan'
MuPAD Combinat, an open source algebraic combinatorics package