Zamalowywanie wierzcholkow kwadratu

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
kondzio34
Użytkownik
Użytkownik
Posty: 18
Rejestracja: 24 kwie 2021, o 12:00
Płeć: Mężczyzna
wiek: 22
Podziękował: 3 razy

Zamalowywanie wierzcholkow kwadratu

Post autor: kondzio34 »

Danych jest \(\displaystyle{ n}\) kolorów, którymi kolorujemy wierzchołki kwadratu. Na ile sposobów można pokolorować wierzchołki kwadratu tak, aby wierzchołki połączone krawędzią miały różne kolory?
Ostatnio zmieniony 10 cze 2021, o 20:28 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Zamalowywanie wierzcholkow kwadratu

Post autor: kerajs »

Ta ilość dla rozróżnialnych wierzchołków to \(\displaystyle{ n \cdot 1 \cdot (n-1)^2+n \cdot (n-1)\cdot (n-2)^2}\) .
kondzio34
Użytkownik
Użytkownik
Posty: 18
Rejestracja: 24 kwie 2021, o 12:00
Płeć: Mężczyzna
wiek: 22
Podziękował: 3 razy

Re: Zamalowywanie wierzcholkow kwadratu

Post autor: kondzio34 »

A mógłbyś pokrótce to wytłumaczyć?
Ostatnio zmieniony 11 cze 2021, o 11:26 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości: pokrótce.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Zamalowywanie wierzcholkow kwadratu

Post autor: kerajs »

OKI.
W kwadracie ABCD wierzchołek A mogę zamalować na \(\displaystyle{ n}\) sposobów. Rozróżniam dwie sytuacje:
1) Wierzchołek C ma ten sam kolor co A, więc dla B i dla D mogę wybrać dowolne z pozostałych \(\displaystyle{ n-1}\) kolorów.
2) Wierzchołek C ma inny kolor niż A (na \(\displaystyle{ n-1}\) sposobów), więc dla B i dla D mogę wybrać dowolne z pozostałych \(\displaystyle{ n-2}\) kolorów.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Zamalowywanie wierzcholkow kwadratu

Post autor: arek1357 »

A jeżeli wierzchołki nie są rozróżnialne?
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Zamalowywanie wierzcholkow kwadratu

Post autor: kerajs »

a) Układy uzyskane w wyniku obrotu uznaję za ten sam układ (kwadrat bez oznaczeń na płaszczyźnie)
\(\displaystyle{ il= {n \choose 2}+ {n \choose 1} {n-1 \choose 2}+ \frac{ n(n-1)(n-2)(n-3) }{4} }\)

b) Układy uzyskane w wyniku obrotu lub symetrii względem przekątnej uznaję za ten sam układ (kwadrat bez oznaczeń w przestrzeni)
\(\displaystyle{ il= {n \choose 2}+ {n \choose 1} {n-1 \choose 2}+ \frac{ n(n-1)(n-2)(n-3) }{8} }\)

PS
W obu sumach składniki to liczby kolorowań dwoma, trzema i czterema kolorami.
ODPOWIEDZ