Consider the following generalization of the Catalan numbers: let Cₙ,ₖ denote the number of sequence of n + k symbols, consisting of n paarentheses ( and k closing parentheses ) such
that, as the sequence is read from right to left, you have always seen at least as many ( as ) s . In other words, these sequences are those that may be extended to a "nest of parentheses" as we discussed in class. Note in particular that Cₙ,ₙ = Cₙ, the usual nth Catalan number.
( a ) Prove the following properties of the numbers
Cₙ,₀ = 1 for all n>0.
If>and>0,then Cₙ,ₖ = Cₙ₋₁,ₖ + Cₙ,ₖ₋₁
If=and>0,then Cₙ,ₖ = Cₙ,ₖ₋₁
