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: 16
Rejestracja: 24 kwie 2021, o 12:00
Płeć: Mężczyzna
wiek: 22
Podziękował: 3 razy

Zamalowywanie wierzcholkow kwadratu

Post autor: kondzio34 » 10 cze 2021, o 20:05

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.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7977
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 262 razy
Pomógł: 3124 razy

Re: Zamalowywanie wierzcholkow kwadratu

Post autor: kerajs » 10 cze 2021, o 21:16

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: 16
Rejestracja: 24 kwie 2021, o 12:00
Płeć: Mężczyzna
wiek: 22
Podziękował: 3 razy

Re: Zamalowywanie wierzcholkow kwadratu

Post autor: kondzio34 » 11 cze 2021, o 11:17

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: 7977
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 262 razy
Pomógł: 3124 razy

Re: Zamalowywanie wierzcholkow kwadratu

Post autor: kerajs » 11 cze 2021, o 15:08

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: 4128
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 97 razy
Pomógł: 414 razy

Re: Zamalowywanie wierzcholkow kwadratu

Post autor: arek1357 » 17 cze 2021, o 10:50

A jeżeli wierzchołki nie są rozróżnialne?

ODPOWIEDZ