Number of ways of coloring boxes following a partition and a restriction I want to color $n$ ordered boxes, the coloring is specified by $(a_1,\cdots,a_d)$ meaning that one color is used $a_1$ times and another different color is used $a_2$ times and so on.... with the property that $a_1+\cdots + a_d=n$. 
Now I want to add a restriction by specifying which boxes should not have the same color. This is specified by the set of couples 
$$E=\{(i,j)\} \,\text{where}\,i,j\in \{1,...,n\}$$
My question is do we have a formula to compute how  many ways we can color $n$ boxes with the partition $(a_1,\cdots,a_d)$ and under the restriction of the set $E$ ? Thank you very much for your help !
 A: There is no "easy" formula for this. There are plenty exponential-sized formulas like the most dummy one: 
$$\sum\limits_{
    \substack{c_1, \ldots, c_n \in \{1,\ldots,d\}\\
               c_i \neq c_j \text{ for } (i,j) \in E\\
               \forall k|\{j\colon c_j = k\}| = a_k}} 1$$
On the other hand, a formula which could be evaluated in polynomial time does not exist unless $\mathbf{P} = \mathbf{NP}$. Suppose there exists a formula $\phi(n, E, a_1, \ldots, a_d) = \#\text{correct colorings}$. Then using this formula we could tell if a graph $G = \langle [n], E\rangle$ could be colored with $d$ colors. Let's add $n' -n = nd\left\lceil {n \over d}\right\rceil - n$ isolated vertices to $G$ add evaluate $\phi(n',E, {n' \over d}, \ldots, {n' \over d})$. If there exists arbitrary coloring of $G$ in $d$ colors then we can color all isolated vertices such that the number of vertices with each color is ${n' \over d}$. Thus $G$ could be colored with $d$ colors iff $\phi(n',E, {n' \over d}, \ldots, {n' \over d}) \neq 0$. Since $\mathrm{COLORING}$ is $\mathbf{NP}$-complete problem, if $\phi$ could be polynomially evaluated, then $\mathbf{P}=\mathbf{NP}$.
I guess there is a representation using chromatic polynomial but I couldn't come up with any. 
