Ile jest różnych doskonałych parowań grafu (drabiny; tak jak na rysunku poniżej) o \(\displaystyle{ 2n}\) wierzchołkach (czyli \(\displaystyle{ n}\) wierzchołków na dole i \(\displaystyle{ n}\) na górze)? Rozpatrzeć przypadki dla \(\displaystyle{ n}\) parzystego i nieparzystego.
Ilość parowań wierzchołków grafu
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Ilość parowań wierzchołków grafu
Domyślam się, że doskonałe parowanie to tyle co skojarzenie doskonałe.
Wskazówka: jeśli oznaczymy sobie odpowiedź dla \(\displaystyle{ n}\) przez \(\displaystyle{ a_n}\) to mamy \(\displaystyle{ a_n=a_{n-1}+a_{n-2}}\) (dlaczego? i co z tego wynika?).
Q.
Wskazówka: jeśli oznaczymy sobie odpowiedź dla \(\displaystyle{ n}\) przez \(\displaystyle{ a_n}\) to mamy \(\displaystyle{ a_n=a_{n-1}+a_{n-2}}\) (dlaczego? i co z tego wynika?).
Q.
Ilość parowań wierzchołków grafu
Myślałem i myślałem i myślałem i nie mam pojęcia czemu ten wzór jest prawdziwy (bo sprawdziłem na kilku pierwszych n i jest).