Bipartiter Graph/Vollständig/2 s/Chromatisches Polynom/Aufgabe/Lösung

Es stehen ${}k$ Farben zur Verfügung, wobei die beiden Teilmengen der bipartiten Zerlegung ${}V=A\uplus B$ auf verschiedene Farben Bezug nehmen. Wenn die zweielementige Menge ${}A$ auf nur eine Farbe Bezug nimmt, so gibt es ${}(k-1)^{s}$ zulässige Färbungen von diesem Typ, da für die ${}s$-elementige Menge ${}B$ genau ${}k-1$ Farben zur Verfügung stehen ohne weitere Bedingung. Für die Farbe für ${}A$ haben wir ${}k$ Möglichkeiten, das ergibt insgesamt ${}k(k-1)^{s}$. Wenn die zweielementige Menge auf zwei Farben Bezug nimmt, so gibt es ${}(k-2)^{s}$ zulässige Färbungen von diesem Typ. Für die Farben für ${}A$ haben wir ${}{\binom {k}{2}}$ Möglichkeiten, was wir mit ${}2$ wegen der beiden möglichen Reihenfolgen multiplizieren müssen. Das ergibt insgesamt ${}k(k-1)(k-2)^{s}$.

Insgesamt ist also

${}P_{}\left(k\right)=k(k-1)^{s}+k(k-1)(k-2)^{s}\,.$

Zur gelösten Aufgabe