Why if $\chi (G)=k$, then we have $S(G,k)=\frac{P(G,k)}{k!}$?

Question

Let $G$ be a finite graph of order $n$. Chromatic polynomial of $G$ is defined by $$P(G,\lambda )=\sum_{k=\chi (G)}^{n}S(G,k)(\lambda)_k $$ where $\chi (G)$ is the chromatic number of $G$ and $$(\lambda)_k =\lambda (\lambda -1) (\lambda -2) \cdots (\lambda -k+1)$$ is the falling factorial of $\lambda$. Moreover, $S(G,k)$ counts the number of stable partitions (partitions into independent sets called independent partitions) of $V(G)$ into $k$ non-empty blocks.

I have a question: why if $\chi (G)=k$, then we have $S(G,k)=\frac{P(G,k)}{k!}$?

By definition, we have $$P(G,k )=\sum_{k=\chi (G)}^{n}S(G,k)(k)_k$$ Since $(k)_k =k!$, we get $$P(G,k )=\sum_{k=\chi (G)}^{n}S(G,k)k! $$ not $$P(G,k )=S(G,k)k! $$

Answer 1

You're using $k$ to mean two different things: both the fixed value $\chi(G)$, and the variable index of summation (a so-called "dummy variable"). Don't overload letters. If we plug $\lambda=\chi(G)$ into $P(G,\lambda)$, we get

$$ P(G,\chi)=\sum_{k=\chi}^n S(G,k)(\chi)_k $$

Note that

$$ (\chi)_k=\begin{cases} \chi! & k=\chi \\ 0 & k>\chi \end{cases} $$

so the summation simply becomes $P(G,\chi)=S(G,\chi)\chi!$.