A balanced assignment from from $N$ objects to $K$ classes is a mapping $\sigma\colon \{ 1, \ldots, N\} \rightarrow \{ 1, \ldots, K\}$ such that $$ \textrm{Card}( \sigma^{-1} \{j \} ) = \textrm{Card} ( \{ i\colon \sigma (i) = j\} ) = N /K,~~ \forall j \in \{ 1, \ldots, K\}. $$ That is, $\sigma$ maps exactly $N/K$ elements to each class. Here we assume $N/K$ is an integer. We denote by $\mathcal P_{N,K}$ the set of all balanced assignments.

For $\sigma, \tau \in \mathcal P_{N,K}$, we define the distance between $\sigma$ and $\tau$ as $$ d(\sigma, \tau) = \min_{\phi \in \Pi_K} \sum_{i=1}^N \mathbf{1} \{ \sigma (i) \neq \phi ( \tau(i) ) \}, $$ where $\Pi_K$ is the set of all permutations of $\{ 1, \ldots, K\}$. Thus $d(\sigma, \tau)$ is the minimum number of elements assigned to different classes up to permutation of labels.

Now we fix $\tau $ to be any fixed balanced assignment and let $\sigma$ be chosen uniformly over $\mathcal{P}_{N,K}$, what is the distribution of $d(\sigma, \tau)$?