(1) ist klar. (2). Die rechte Abschätzung ist klar, da rechts die Anzahl der Färbungen mit
Farben überhaupt ohne Zulässigkeitsbedingung steht. Die linke Seite ist klar für
.
Für
.
ist die Zahl links
nach Fakt
die Anzahl der injektiven Abbildungen von
nach
, und diese sind stets zulässig.
(3). Eine zulässige Färbung mit
(höchstens)
Farben ist eine zulässige Färbung mit genau
Farben für ein
.
Es sei
die Anzahl der zulässigen Färbungen mit genau
Farben. Dann ist die Anzahl der zulässigen Färbungen mit
Farben unter Verwendung von
Fakt
gleich
![{\displaystyle {}{\begin{aligned}\sum _{\ell =0}^{n}{\binom {k}{\ell }}Q(\ell )&=\sum _{\ell =0}^{n}{\binom {k}{\ell }}{\left(\sum _{j=0}^{\ell }(-1)^{j}{\binom {\ell }{j}}P_{G}\left(\ell -j\right)\right)}\\&=\sum _{\ell =0}^{n}{\binom {k}{\ell }}{\left(\sum _{j=0}^{\ell }(-1)^{\ell -j}{\binom {\ell }{j}}P_{G}\left(j\right)\right)}\\&=\sum _{j=0}^{n}{\left(\sum _{\ell =j}^{n}(-1)^{\ell -j}{\binom {k}{\ell }}{\binom {\ell }{j}}\right)}P_{G}\left(j\right).\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/82e159744fdd9d2f87d8019bfb665dbb1e30709b)