Liczby Catalana i uściski dłoni

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Nuna
Użytkownik
Użytkownik
Posty: 99
Rejestracja: 7 gru 2019, o 19:36
Płeć: Kobieta
wiek: 19
Podziękował: 56 razy

Liczby Catalana i uściski dłoni

Post autor: Nuna » 8 maja 2020, o 17:58

Pokaż, że \(\displaystyle{ 2n}\) osób siedzących przy okrągłym stole może uścisnąć sobie dłonie (bez przecięć) na \(\displaystyle{ C_{n}}\) sposobów (\(\displaystyle{ C_{n} }\) to \(\displaystyle{ n}\)-ta liczba Catalana).

Chciałam to podejść indukcją, jednak mam problem z krokiem indukcyjnym. Nie potrafię opisać skąd mogłaby tam być zależność rekurencyjna \(\displaystyle{ C_{n+1} = \sum_{i=0}^{n}C_{i}C_{n-i} }\).
Ostatnio zmieniony 8 maja 2020, o 20:33 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3962
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 94 razy
Pomógł: 386 razy

Re: Liczby Catalana i uściski dłoni

Post autor: arek1357 » 14 maja 2020, o 11:10


ODPOWIEDZ