Użycie kombinacji do wyznaczenia wzoru na ilość przekatnych nkąta

[MichalProg]

Dzień dobry.

Mam wykazać, że ilość przekątnych n-kąta wypukłego wyraża się wzorem:
\(\displaystyle{ P_n = \frac{n(n-3)}{2}}\)

Szukając w internecie natrafiłem na wzór:
\(\displaystyle{ C_{n}^{2} - n}\)

Nie wiem tylko czemu tu użyto kombinacji.
\(\displaystyle{ {n \choose 2} - n = \frac{n(n-3)}{2}}\)

Michał

Ps dowód wzoru miał być indukcyjny, o kombinacje pytam z ciekawości i dla poszerzenia horyzontów.

[Tmkk]

Przekątną można jednoznacznie wyznaczyć przez wybór dwóch wierzchołków, stąd kombinacje. Należy jednak odjąć przypadek, kiedy wybrane wierzchołki leżą obok siebie.

[MichalProg]

Aha. A czy czasem nie chodzi o odjęcie tych samych przekątnych np. \(\displaystyle{ AC = CA}\) ?

[Tmkk]

Nie, ponieważ kombinacje wybierają nam podzbiory - kolejność elementów nie ma znaczenia. Jeśli wylosujemy zbiór \(\displaystyle{ \left\{ A,C\right\} }\), to daje nam jedną przekątną - \(\displaystyle{ AC}\)

[MichalProg]

Aha. Dzięki.

[Tmkk]

Możesz to również inaczej. Każdy punkt możesz połączyć z \(\displaystyle{ n-3}\) innymi punktami, które dadzą przekątną (odrzucamy ten punkt i jego sąsiadów). Wszystkich punktów jest \(\displaystyle{ n}\), co daje \(\displaystyle{ (n-3)n}\) przekątnych. Ale nietrudno zauważyć, że każdą przekątną liczymy dwukrotnie. Po podzieleniu, wychodzi co trzeba.

[MichalProg]

Dzięki. A czy da się to jakoś dowieść indukcyjnie? Mając wzór, że \(\displaystyle{ P_n = \frac{n(n-3)}{2}}\)
Czy tylko w taki sposób, jak pokazałeś?

[Tmkk]

Jasne, ale jest to trochę na siłę i sposoby jakie znam, mają duży związek z rozwiązaniami, które tu już padły. Napiszę w skrócie ideę.

sposób nr 1
Od \(\displaystyle{ (n+1)}\)-kąta odcinamy jeden wierzchołek - tak, że powstaje trójkąt i \(\displaystyle{ n}\)-kąt. W \(\displaystyle{ n}\)-kącie wiemy ile jest przekątnych z założenia indukcyjnego i zastanawiamy się ile dodatkowych przekątnych daje nam odcięty punkt. Możemy go połączyć z \(\displaystyle{ n+1-3}\) wierzchołkami, co da nowe przekątne. Dodatkowo odcinek, którym przecięliśmy nasz \(\displaystyle{ (n+1)}\)-kąt, też jest przekątną. Razem mamy
\(\displaystyle{ \frac{n(n+3)}{2} + 1 + n- 2 = \frac{(n+1)(n-2)}{2}}\)

sposób nr 2
Dowodzimy w sposób indukcyjny (a nie z interpretacji kombinatorycznej), że \(\displaystyle{ n}\) punktów, z których żadne \(\displaystyle{ 3}\) nie są współliniowe, można połączyć \(\displaystyle{ {n\choose 2}}\) odcinkami. Dalej rozpatrujemy wielokąt i tak, jak w pierwszym sposobie, odejmujemy \(\displaystyle{ n}\) - sąsiednie wierzchołki w wielokącie.