2
$\begingroup$

We have $E$ balls of $N$ colors. Let's call $e_i$ the number of balls of color $i$ (of course across group balls are distinguishable while within a color they are not). We can split these balls among $N$ labelled (i.e. distinguishable) jars.

I would like to count the number of ways the balls can be distributed in the jars such as:

  • the $i$-th jar contains exactly $o_i$ balls
  • the $j$-th color is divided exactly among $k_j$ jars

Both conditions should hold. For simplicity we can initially assume $e_i = o_i = k_i$, but the dependency on $i$ should remain.

I know that the problem is highly not-trivial so even a sketch (or a non closed form) solution is wellcome!

$\endgroup$
1
1
$\begingroup$

Hint:

Seems to understand that, called $n_{\,i,\,j}$ the number of balls of color $j$ into box $k$, we have a $N \times N$ matrix in which the sums of the columns, as well as those of the rows are determined as $e_j$ and $o_i$.
Moreover, the $e_j$ shall be equally parted into $k_j$ boxes.

We can summarize the whole as $$ \left\{ \matrix{ 1 \le i,j \le N \hfill \cr u_{\,i} \in \left\{ {0,1} \right\} \hfill \cr \left. \matrix{ k_{\,j} \backslash e_{\,j} ,\quad m_{\,j} \backslash e_{\,j} ,\quad e_{\,j} = m_{\,j} \,k_{\,j} \hfill \cr n_{\,i,\,j} = u_{\,i} \,m_{\,j} \hfill \cr} \right\}\quad \Rightarrow \quad n_{\,i,\,j} \in \left\{ 0 \right\} \cup \left\{ {m_{\,j} :m_{\,j} \backslash e_{\,j} } \right\} \hfill \cr \sum\limits_i {n_{\,i,\,j} } = e_{\,j} ,\quad \sum\limits_j {n_{\,i,\,j} } = o_{\,i} ,\quad \sum\limits_{i,\,j} {n_{\,i,\,j} } = E \hfill \cr} \right. $$ where of course all the variables are non-negative integers.

Now, it is not clear what you want to keep fixed: only $N$ and $E$ ? or else ?

2nd step

In trying and find, at least, a "possible" approach to the problem, I am presenting a second step.
So, as you commented you are going to keep $e_j$ and $o_i$ as fixed.
Then we may write $$ \left\{ \matrix{ 1 \le i,j \le N \hfill \cr e_{\,j} = m_{\,j} \,k_{\,j} \hfill \cr u_{\,i,j} \in \left\{ {0,1} \right\},\;\;n_{\,i,\,j} = u_{\,i,\,j} \,m_{\,j} \hfill \cr e_{\,j} = \sum\limits_i {n_{\,i,\,j} } = m_{\,j} \sum\limits_i {u_{\,i,\,j} } \quad \Rightarrow \quad \sum\limits_i {u_{\,i,\,j} } = k_{\,j} \hfill \cr o_{\,i} = \sum\limits_j {n_{\,i,\,j} } = \sum\limits_j {u_{\,i,\,j} \,m_{\,j} } \quad \Rightarrow \quad o_{\,i} \le \sum\limits_j {\,m_{\,j} } \hfill \cr} \right. $$ and with an obvious matrix symbolism we can put it as $$ \left\{ \matrix{ \overline {\bf u} \;{\bf U} = \overline {\bf k} \hfill \cr {\bf U}\;{\bf m} = {\bf o} \hfill \cr \overline {\bf u} \;{\bf U}\;{\bf m} = \overline {\bf k} \;{\bf m} = \overline {\bf u} \;{\bf o} = E \hfill \cr} \right. $$

3rd step

The previous can be considered a linear system in the unknowns $u_{i,j}$ (which can be only $0,1$), and given the $o_i$'s and the $m_j$'s and $k_j$'s, which are related between them as to give $m_jk_j=e_j$.

Starting with $N=2$, and then passing to $N=3$, the system above can be rewritten as

Gruppi_Balls_Bins_1

where a possible recursive pattern is appearing.

$\endgroup$
8
  • $\begingroup$ Basically yes : we have an NxN matrix with E entries equal to one, we fix the sum of each row and column and we want to calculate the way to shuffle the entries $\endgroup$ Jul 17 '18 at 18:13
  • $\begingroup$ G Cab any idea? $\endgroup$ Jul 19 '18 at 8:49
  • $\begingroup$ Uhm, quite difficult, seems a problem of tomographic scanning $\endgroup$
    – G Cab
    Jul 19 '18 at 23:47
  • $\begingroup$ @NinjaWarrior: added a possible step forward: pls. give your feedback $\endgroup$
    – G Cab
    Jul 20 '18 at 17:24
  • $\begingroup$ I am not sure to understand the role of $m$, why did you introduce it ? We have a NxN matrix with E non zero entries and we need to calculate the number of ways we can reshuffle them in order to leave the sum of the rows and the columns the same (we can also assume the sum on the i-th column to be the same of the sum on the i-th row, i.e. symmetric matrix) $\endgroup$ Jul 21 '18 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.