Na okręgu rozmieszczono n punktów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
max123321
Użytkownik
Użytkownik
Posty: 3388
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 975 razy
Pomógł: 3 razy

Na okręgu rozmieszczono n punktów

Post autor: max123321 »

Na okręgu rozmieszczono \(\displaystyle{ n}\) punktów i poprowadzono wszystkie cięciwy, których końcami są te punkty. Zakładamy, że żadne trzy cięciwy nie przecinają się w jednym punkcie.

Ile powstało trójkątów, których boki są tymi cięciwami lub ich fragmentami? Trójkąty nie muszą mieć rozłącznych wnętrz, przykładowo dla \(\displaystyle{ n=4}\) powstało \(\displaystyle{ 8}\) trójkątów.

Jak to zrobić?
Awatar użytkownika
Gosda
Użytkownik
Użytkownik
Posty: 340
Rejestracja: 29 cze 2019, o 19:46
Płeć: Mężczyzna
Lokalizacja: Oulu
Podziękował: 42 razy
Pomógł: 60 razy

Re: Na okręgu rozmieszczono n punktów

Post autor: Gosda »

Skąd to zadanie? Wygląda na dość trudne, dla wielokątów foremnych rozwiązanie znajdziesz na ... angle.html. Gdyby strona padła, podaję kilka pierwszych wartości w ciągu: 1, 8, 35, 110, 287, 632, 1302, 2400, 4257, 6956.

Z dodatkowym warunkiem, że żadne trzy przekątne nie przecinają się w jednym punkcie, trochę łatwiejsze, odpowiedź to

\(\displaystyle{ a_n = {n + 3 \choose 6} + {n+1 \choose 5} + {n \choose 5}}\),

z wyjaśnieniem na przykład w C. L. Liu, Introduction to Combinatorial Analysis. McGraw-Hill, NY, 1968, p. 20. albo https://www.math.uni-bielefeld.de/~sillke/SEQUENCES/triangle_counting.
max123321
Użytkownik
Użytkownik
Posty: 3388
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 975 razy
Pomógł: 3 razy

Re: Na okręgu rozmieszczono n punktów

Post autor: max123321 »

To zadanie z serii prac domowych mojego ćwiczeniowca. Też uważam, że trudne. A możesz wyjaśnić skąd ten wynik:
\(\displaystyle{ {n + 3 \choose 6} + {n+1 \choose 5} + {n \choose 5}}\)
?
Pamiętam, że coś podobnego wychodziło w odpowiedziach, chyba nie dokładnie tyle, ale podobnie, niestety nie wiem jak do tego dojść.
ODPOWIEDZ