Matematyka.pl

Chcę znaleźć wielomian chromatyczny grafu \(\displaystyle{ K_{3,3}}\). Na wikipedii napisali, że za różne uznajemy takie kolorowania, która różnią się nawet tylko permutacją kolorów.

Wydaje mi się, że będzie tak:
\(\displaystyle{ P_{K_{3,3}}(x) = x^{\underline{2}} + 2 \cdot {3 \choose 2} \cdot x^{\underline{3}} + 2 \cdot 3! \cdot x^{\underline{4}} + {3 \choose 2} \cdot {3 \choose 2} \cdot x^{\underline{4}} + 2 \cdot 3! \cdot {3 \choose 2} \cdot x^{\underline{5}} + 6! \cdot x^{\underline{6}}}\)

Po kolei:
- pierwszy składnik: kolorujemy dwoma kolorami, nie łamiemy symetrii
- drugi: wybieramy stronę grafu na dwa sposoby, wybieramy na 3 sposoby dwa wierzchołki z trzech, kolorujemy je jednym kolorem, trzeci kolorujemy drugim, a drugą stronę nowym kolorem
- trzeci: wybieramy stronę, każdy wierzchołek z tej strony kolorujemy innym kolorem. Więc wybieramy kolory i mnożymy przez liczbę ich permutacji. Drugą stronę kolorujemy nowym kolorem
- czwarty (z obu stron kolorujemy dwoma kolorami) - wybieramy dwa wierzchołki z lewej, i dwa z prawej, kolorujemy je dwoma kolorami kolorami. Dwa pozostałe wierzchołki kolorujemy dwoma nowymi kolorami. Nie łamiemy symetrii
- piąty (z jednej trzy, a z drugiej strony dwa kolory) - wybieramy stronę, kolorujemy trzema kolorami, mnożymy przez liczbę permutacji, z drugiej strony wybieramy dwa wierzchołki, kolorujemy jednym kolorem, a ostatni wierzchołek nowym
- szósty (każdy innym kolorem) - wybieramy sześć kolorów i mnożymy przez liczbę permutacji

Pytanie czy dobrze?

Heniek1991 pisze: - trzeci: wybieramy stronę, każdy wierzchołek z tej strony kolorujemy innym kolorem. Więc wybieramy kolory i mnożymy przez liczbę ich permutacji. Drugą stronę kolorujemy nowym kolorem

Nie mnożymy przez liczbę permutacji. Wybieramy stronę, która będzie pokolorowana trzema kolorami: \(\displaystyle{ 2}\), wybieramy kolory dla kolejnych trzech wierzchołków po tej stronie: \(\displaystyle{ x(x-1)(x-2)}\), wybieramy kolor dla drugiej strony: \(\displaystyle{ x-3}\). Razem \(\displaystyle{ 2\cdot x^{\underline{4}}}\).

Heniek1991 pisze: - piąty (z jednej trzy, a z drugiej strony dwa kolory) - wybieramy stronę, kolorujemy trzema kolorami, mnożymy przez liczbę permutacji, z drugiej strony wybieramy dwa wierzchołki, kolorujemy jednym kolorem, a ostatni wierzchołek nowym
- szósty (każdy innym kolorem) - wybieramy sześć kolorów i mnożymy przez liczbę permutacji

To samo.

Czyli: \(\displaystyle{ P_{K_{3,3}}(x) = x^{\underline{2}} + 2 \cdot {3 \choose 2} \cdot x^{\underline{3}} + 2 \cdot x^{\underline{4}} + {3 \choose 2} \cdot {3 \choose 2} \cdot x^{\underline{4}} + 2 \cdot {3 \choose 2} \cdot x^{\underline{5}} + x^{\underline{6}}}\)

Tak.

Powiedz jeszcze dlaczego nie mnożymy przez te permutacje?

A dlaczego mielibyśmy mnożyć?