卡特蘭數相關及通項公式簡單證明

卡特蘭數有兩個遞推公式，兩個通項公式（或者說是一個）：

規定,

用折線法證明通項公式：

點即為第一次走過的點，綠線和黃線組成了一條非法的路徑

現在按照對稱，則綠線和藍線構成了另一條路徑

藍線和黃線總是一一對應的，而藍線走到的點總是

其他