Os números catalães são uma sequência de números naturais que ocorre em muitos problemas interessantes de contagem, como seguir.
1) Conte o número de expressões contendo n pares de parênteses que são correspondidos corretamente. Para n = 3, as expressões possíveis são ((())),() (()),()()(), (())(), (()()).
2) Conte o número de árvores de busca binárias possíveis com n chaves (veja isto ) Veja isto para mais aplicações.
Os primeiros poucos números catalães para n = 0, 1, 2, 3, ... são 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...
<?php
// PHP Program for nth
// Catalan Number
// A recursive function to
// find nth catalan number
function catalan($n)
{
// Base case
if ($n <= 1)
return 1;
// catalan(n) is sum of
// catalan(i)*catalan(n-i-1)
$res = 0;
for($i = 0; $i < $n; $i++)
$res += catalan($i) *
catalan($n - $i - 1);
return $res;
}
// Driver Code
for ($i = 0; $i < 10; $i++)
echo catalan($i), " ";
// This code is contributed aj_36
?>
<?php
// PHP program for nth Catalan Number
// A dynamic programming based function
// to find nth Catalan number
function catalanDP( $n)
{
// Table to store results
// of subproblems
$catalan= array();
// Initialize first two
// values in table
$catalan[0] = $catalan[1] = 1;
// Fill entries in catalan[]
// using recursive formula
for ($i = 2; $i <= $n; $i++)
{
$catalan[$i] = 0;
for ( $j = 0; $j < $i; $j++)
$catalan[$i] += $catalan[$j] *
$catalan[$i - $j - 1];
}
// Return last entry
return $catalan[$n];
}
// Driver Code
for ($i = 0; $i < 10; $i++)
echo catalanDP($i), " ";
// This code is contributed anuj_67.
?>
