Liczba trójkątów różnobarwnych

Question

Witam, 

robiłem zadanie z informatyki "Trójkąty jednobarwne" ( https://szkopul.edu.pl/problemset/problem/UU2Uj-barjiONnRxd9aEVoDj/site/?key=statement ). W skrócie: jest n punktów, są podane połączenia punktów o kolorze czerwonym, reszta połączeń jest czarna. Ile jest takich trójkątów, że każdy z boków jest jednego koloru; ile jest trójkątów jednobarwnych?

Rozwiązanie proponowane przez autora wygląda mniej więcej tak:

n - liczba punktów 

d(k) - liczba czerwonych krawędzi wychodzących z punktu k

Zatem liczba trójkątów RÓŻNOBARWNYCH o wierzchołku w k wynosi d(k)*(n-1-d(k)) [???] 

Dalej należy zsumować dla każdego punktu i podzielić na 2, a ten wynik odjąć od ilości wszystkich trójkątów - n nad 3.

Moje pytanie jednak, dotyczy wyrażenia obok znaków zapytania. Skąd to się w ogóle wzięło? Dlaczego iloczyn ilości połączeń czerwonych i czarnych to ilość różnobarwnych trójkątów o wierzchołku w k? 

Z góry dzięki. 

 

Answer 1

Liczba różnobarwnych trójkątów o wierzchołku k wynosi iloczyn ilości połączeń czerwonych i czarnych krawędzi wychodzących z wierzchołka k, ponieważ każdy taki trójkąt składa się z dwóch krawędzi o różnych kolorach i trzeciej krawędzi o kolorze przeciwnym do jednej z nich.

Załóżmy, że wierzchołek k ma d(k) krawędzi czerwonych i n-d(k) krawędzi czarnych wychodzących z niego. Możemy wybrać dwie różne krawędzie spośród tych d(k) czerwonych krawędzi na d(d(k)) sposobów. Następnie wybieramy jedną krawędź spośród n-d(k) czarnych krawędzi, co daje d(k) * (n-d(k)) możliwości wyboru trójkąta o wierzchołku k i krawędziach o różnych kolorach.

Mamy jednakże dwa takie trójkąty dla każdej pary krawędzi o różnych kolorach, ponieważ możemy wybrać każdą z tych krawędzi jako pierwszą krawędź trójkąta. Z tego powodu, liczba różnobarwnych trójkątów o wierzchołku k wynosi d(k) * (n-d(k)) / 2.

Ostatecznie, aby uzyskać liczbę wszystkich różnobarwnych trójkątów, należy zsumować wynik dla każdego wierzchołka i podzielić przez 3!, ponieważ każdy trójkąt został policzony 6 razy (raz dla każdej z trzech krawędzi) i trzeba usunąć tę wielokrotność.

Mam nadzieje, że pomogłem.