Cześć,
czy ktoś byłby w stanie polecić mi jakąś polską literaturę, w której występuje zagadnienie liczb Catalana?
Z góry dziękuję.
Liczby Catalana - literatura
Liczby Catalana - literatura
Dziękuję. Mam jeszcze jedno pytanie odnośnie liczb Catalana.
Dlaczego liczba wszystkich możliwych monotonicznych dróg, prowadzących z lewego dolnego wierzchołka do prawego górnego w kwadracie \(\displaystyle{ n \times n}\) wynosi \(\displaystyle{ {2n \choose n}}\)?
Dlaczego liczba wszystkich możliwych monotonicznych dróg, prowadzących z lewego dolnego wierzchołka do prawego górnego w kwadracie \(\displaystyle{ n \times n}\) wynosi \(\displaystyle{ {2n \choose n}}\)?
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Liczby Catalana - literatura
Każda taka droga składa się z \(\displaystyle{ 2n}\) odcinków (łatwe), przy czym musimy wykonać po \(\displaystyle{ n}\) kroków „w górę" i „w prawo". Indeksujemy sobie ruchy (tj. przemierzenie odcineczka długości \(\displaystyle{ 1}\) to ruch) składające się na daną drogę od \(\displaystyle{ 1}\) do \(\displaystyle{ 2n}\). Wybierzmy \(\displaystyle{ n}\) indeksów z tych \(\displaystyle{ 2n}\), które będą odpowiadać ruchom „w górę" (czyli przy pozostałych \(\displaystyle{ n}\) mamy ruch „w prawo").
Liczby Catalana - literatura
Dzięki za odpowiedź.
To pytanie nie wiąże się bezpośrednio z liczbami Catalana, ale skąd wiadomo, że środkową kolumnę w trójkącie Pascala można policzyć ze wzoru \(\displaystyle{ \frac{(2n)!}{(n!) ^{2} }}\)?
-- 4 cze 2019, o 22:33 --
Jeszcze jedna prośba:
Czy ktoś mógłby wyprowadzić po kolei przybliżenie n-tej liczby Catalana ze wzoru Stirlinga?
Byłbym bardzo wdzięczny.-- 5 cze 2019, o 00:40 --Ja próbowałem zrobić to tak:
\(\displaystyle{ \frac{1}{n+1} \frac{(2n)!}{n!n!} \approx \frac{1}{n+1} \frac{ (\frac{2n}{e})^{2n} \cdot \sqrt{ 4 \pi n} }{( \frac{n}{e})^{2n} \cdot \sqrt{2 \pi n}\cdot \sqrt{2 \pi n} )}= \frac{1}{n+1} \frac{ (\frac{2n}{e})^{2n} \cdot \sqrt{ 4 \pi n} }{ (\frac{n}{e})^{2n} \cdot \sqrt{4 \pi n} \cdot \sqrt{ \pi n} }= \frac{1}{n+1} \frac{4^{n}}{ \sqrt{ \pi n} }= \frac{4^{n}}{(n+1) \sqrt{ \pi n} }}\)
Wynik nie zgadza się z podanym przybliżeniem, czyli \(\displaystyle{ \frac{4^{n}}{n^{ \frac{3}{2} } \cdot \sqrt{ \pi } }}\)
To pytanie nie wiąże się bezpośrednio z liczbami Catalana, ale skąd wiadomo, że środkową kolumnę w trójkącie Pascala można policzyć ze wzoru \(\displaystyle{ \frac{(2n)!}{(n!) ^{2} }}\)?
-- 4 cze 2019, o 22:33 --
Jeszcze jedna prośba:
Czy ktoś mógłby wyprowadzić po kolei przybliżenie n-tej liczby Catalana ze wzoru Stirlinga?
Byłbym bardzo wdzięczny.-- 5 cze 2019, o 00:40 --Ja próbowałem zrobić to tak:
\(\displaystyle{ \frac{1}{n+1} \frac{(2n)!}{n!n!} \approx \frac{1}{n+1} \frac{ (\frac{2n}{e})^{2n} \cdot \sqrt{ 4 \pi n} }{( \frac{n}{e})^{2n} \cdot \sqrt{2 \pi n}\cdot \sqrt{2 \pi n} )}= \frac{1}{n+1} \frac{ (\frac{2n}{e})^{2n} \cdot \sqrt{ 4 \pi n} }{ (\frac{n}{e})^{2n} \cdot \sqrt{4 \pi n} \cdot \sqrt{ \pi n} }= \frac{1}{n+1} \frac{4^{n}}{ \sqrt{ \pi n} }= \frac{4^{n}}{(n+1) \sqrt{ \pi n} }}\)
Wynik nie zgadza się z podanym przybliżeniem, czyli \(\displaystyle{ \frac{4^{n}}{n^{ \frac{3}{2} } \cdot \sqrt{ \pi } }}\)