How to count proper vertex colorings of a path graph with $n$ vertices using at most $r$ colors with the condition that a specific color is used exactly $k$ times?
When the condition is relaxed, the answer is $r(r-1)^{n-1}$.
When the condition is hold, but the coloring can be improper, the answer is $\binom{n}{k}(r-1)^{n-k}$. If it is additionally assumed that the specific color is not used for adjacent vertices, while the other colors can (kind of partially proper coloring), the answer is $\binom{n+1-k}{k}(r-1)^{n-k}$.
Is there a closed form solution to it? I find it challenging, while only a simple condition is imposed.
It is also related to budgeted graph coloring studied in this paper.
In general, is there any efficient algorithm that enumerates or counts proper $r$-colorings of a given simple graph where the number of times that each color appears is exactly given or lies in a given interval? In the above question, the specific color appears exactly $k$ times and there are no restrictions on the other colors.
Best Answer
The argument that gives $\binom{n+1-k}{k}(r-1)^{n-k}$ can be refined to count proper colorings. The idea is that deleting the $k$ vertices colored with the special color leaves, in most cases, $k+1$ paths with $n-k$ vertices total, and there are $(r-1)^{k+1}(r-2)^{n-2k-1}$ ways to color these paths.
We cannot simply say $\binom{n+1-k}{k}(r-1)^{k+1}(r-2)^{n-2k-1}$, because if the first and/or the last vertex gets the special color, then fewer components are left over. There are $\binom{n-k-1}{k-2}$ cases where both the first and last vertex get the special color, $2\binom{n-k-1}{k-1}$ cases where only one of them does, and $\binom{n-k-1}{k}$ cases where neither of them does. We can combine these into $$\binom{n-k-1}{k-2}(r-1)^{k-1}(r-2)^{n-2k+1} + 2 \binom{n-k-1}{k-1}(r-1)^k (r-2)^{n-2k} + \binom{n-k-1}{k} (r-1)^{k+1}(r-2)^{n-2k-1}$$ total $r$-colorings.