liczba catalana a iloczyn n-elementowy

[mike_btls]

Witam
Jak udowodnic że liczba sposobów w jakie można rozmiescic nawiasy w iloczynie n-elementowym jest rowna liczbie Catalana?

[pawels]

Należy zobaczyć, że rozmieszczeń nawiasów jest tyle co monotonicznych dróg w kwadracie mieszczących się pod przekątna- teraz zliczamy je odejmując od wszystkich złe, a złe zliczamy odbijając kawałek od początku, do pierwszej felernej wartości względem przekątnej przesuniętej o wektor \(\displaystyle{ [0,1]}\)- są to wszystkie drogi w pewnym prostokącie.

Możesz też napisać rekurencję i ja rozwiązać- zauważamy związek funkcji tworzącej z własnym splot, rozwiązujemy równanie kwadratowe, odrzucamy jeden pierwiastek niezgodny z warunkami początkowymi i rozwijamy w szereg z dwumianu Newtona.