Combinations or Counting general formula

Question

Assume you have 5 numbered bins and you have 2 red balls, 2 blue balls and 2 green balls (You can assume that there are equal number of red, blue and green balls). I am trying to derive a general formula for the following case: Number of possible ways you can arrange the 6 balls into 5 bins such that each bin contains:

1. At most 2 balls (i.e, 1 or 2 balls or empty)
2. No 2 balls of same color go into same bin (i.e, you cannot have 2 red balls or 2 blue balls or 2 green balls together)

I need to satisfy both constraints.

I tried the following approach: Say you have 3 numbered bins and 2 balls each of colors Red, Blue and Green. You can distribute the 2 Red balls into 3 bins in 3 ways. Then you can place one Blue ball into the remaining empty bin and then second Blue ball can be placed into the two bins with one red-ball each in 2 ways. Now the Green balls can go into the remaining two places. So there are a total of 6 ways to do this. But I want to generalize the solution to larger number of bins and larger number of balls.

Answer 1

A generalization

There are many ways to generalize this problem.

For instance, let there be $n$ bins indexed by $j=1,2,\ldots,n,$ each capable of holding no more than $b_j$ balls, into which $k_1$ balls of color $1$, $k_2$ balls of color $2,$ ..., and $k_m$ balls of color $m$ are to be placed in such a way that for each color $i,$ bin $j$ must contain no more than $u_{ij}$ balls of color $i.$ Let any such placement be called a "configuration:" we wish to count distinct configurations.

The example of the question is specified by vectors $\mathbf{k}=(2,2,2)$ (color counts), $\mathbf{b}=(2,2,2,2,2)$ (bin capacities), and an $m\times n=3\times 5$ matrix $(u_{ij})=(1)$ (per-color bin limits).

Limiting the generalization to achieve a tractable problem

It looks difficult, if not impossible, to produce a program, much less a formula, for this level of generality. In some special cases, however, simple formulas are possible. One of these still generalizes the example of the question. We suppose there are equal numbers $k$ of each color and each of $n$ bins must contain fewer than $m$ balls, all of different colors. Thus, $\mathbf{k}=(k,k,\ldots, k)$ is an $m$-vector, $\mathbf{b}=(m-1,m-1,\ldots,m-1)$ is an $n$-vector, and it remains the case that $(u_{ij})=1.$

Solution of the limited generalization

To count the configurations in this special case, note that without any restrictions on bin contents the disposition of $k$ monochromatic balls with no more than one per bin corresponds to the selection of $k$ bins in which to place them, of which there are $\binom{n}{k}$ possibilities. This yields $\binom{n}{k}^m$ possible configurations for all $km$ balls.

Some of these configurations are "bad" in the sense that they violate the bin capacity restriction: one or bins will contain all $m$ colors. Let's call these the "loaded" bins. We may count the bad configurations by focusing on the loaded bins.

There are $n$ possibilities for the loaded bins. That bin contains one ball of each color, leaving $k-1$ balls of each color to be placed in the remaining $n-1$ bins. There are $\binom{n-1}{k-1}$ ways to do that for each of the $m$ colors. Thus, by summing over all $n$ possible loaded bins, we find there are at most $n\binom{n-1}{k-1}^m$ bad configurations.

That sum counts any bad configurations with two or more loaded bins as many times as it has loaded bins: that's why it potentially over-counts the bad configurations. We need to adjust it. Consider the case of two loaded bins. Arguing as before, we see (a) there are $\binom{n}{2}$ distinct possible subsets of two loaded bins and (b) in such cases there remain $k-2$ balls of each color to be placed into the remaining $n-2$ bins. Thus, we should subtract $\binom{n}{2}\binom{n-2}{k-2}^m$ from the previous overestimate.

This, however, subtracts too much, because we have not accounted for ay bad configurations with three or more loaded bins. The continuation of the argument should be clear: it is an application of the Principle of Inclusion-Exclusion, or "PIE." The alternating addition and subtraction continues until there are no balls left to account for, giving the formula

$$f(n,m,k) = \sum_{i=0}^k (-1)^i \binom{n}{i}\binom{n-i}{k-i}^m.$$

Examples

(1) The problem in the question.

In the case of $n=5$ bins to be filled with balls of $m=3$ colors ($k=2$ of each color available) with at most $m-1$ balls in each bin, we find

$$f(5,3,2) = \binom{5}{0}\binom{5}{2}^3 - \binom{5}{1}\binom{4}{1}^3 + \binom{5}{2}\binom{3}{0}^3 = 10^3 - 5(4^3) + 10(1^3) = 690.$$

If we vary the numbers of bins, still keeping to two balls each of three colors, the sequence $f(3,3,2), f(4,3,2), \ldots, f(n,3,2)$ begins

$$6, 114, 690, 2640, 7770, 19236, 42084, 83880, 155430, 271590, \ldots$$

This sequence is not in the OEIS, indicating it has not specifically been studied before (although likely it is related to some well-known sequence).

(2) A binomial identity

When the total number of balls, $km,$ exceeds $n(m-1),$ the Pigeonhole Principle implies at least one bin must contain at least $m$ balls. Thus, all configurations are bad and the answer is $0.$ In such cases

$$0 = f(n,m,k) = \sum_{i=0}^k (-1)^i \binom{n}{i}\binom{n-i}{k-i}^m$$

yields an interesting Binomial identity. A special case occurs when $n=aN$ is a multiple of $a=2,3,4,$ etc; $k=(a-1)N+1,$ and $m=a,$ for then

$$km = ((a-1)N+1)a = a(a-1)N + a \gt a(a-1)N = n(m-1).$$

The identity is

$$0 = f(aN, a, (a-1)N+1)=\sum_{i=0}^{(a-1)N+1} (-1)^i \binom{aN}{i}\binom{aN-i}{(a-1)N+1-i}^a.$$

Answer 2

When we refer to a "general formula" to solve a problem, we usually mean some function that takes variable inputs and produces an output that solves the problem over the scope of allowable inputs. You only get a general formula when you have a problem involving variables as inputs. Right now you have specified the number of bins, the number of balls of each colour, and the constraints, so there are no variables in the problem. (Similarly, the reader does not have to assume that there are an equal number of red, blue and green balls, since you have already specified the number of each of these balls; the fact that $2=2=2$ is not an assumption.)

Since you have no variables in your problem, there is a specific number of arrangements as the answer, which means that the "general formula" for this problem is the trivial function with no inputs and with the numeric answer as an output.$^\dagger$ So, as whuber correctly points out in the comments, the simplest (and indeed only) formula for the problem (taking $A$ to denote the number of possible arrangements satisfying the constraints) is $A = 2640$.

---

Generalising your problem: If you want a "general formula" for this type of problem, you first need to generalise the problem itself, so that it involves variables. This would be done by removing the specific numbers you have attached and replacing them with variables in an allowable range. The way you would do this would depend on exactly how much you want to generalise the problem, but here is an example of a generalised problem:

General problem: Suppose we have $n \in \mathbb{N}$ numbered bins and we have $k \in \mathbb{N}$ copies of each of $m \in \mathbb{N}$ different coloured balls (so we have $mk$ balls in total). We want to arrange these balls into the bins subject to the following constraints:

1. Each bin has no more than two balls in it (i.e., it can have zero, one or two balls); and
2. There cannot be more than one ball of the same colour in a bin.

Consider the case where $m \leqslant n \leqslant mk$ (which encompasses the specific problem in your question). Find a general formula for the number of possible arrangements of balls $A(n,m,k)$.

This is just one example of how you could generalise your problem. As you can see, I generalised the number of bins, colours, and multiples of balls, but I did not generalise the constraints. I will not attempt to solve this generalised problem here, because suffice to say, it is complicated. If you are interested in a generalised problem like this one then I would suggest you post a new question specifying the general problem you want to solve, with variable inputs.

---

$^\dagger$ Formally, such a function is a mapping from the empty set to a codomain of values. (We can specify the latter as broadly as we want, so long as it contains the answer.) So we can write this function formally as a mapping $A: \varnothing \mapsto \mathbb{N}_{0}$, where it is most natural to specify the codomain as the set of non-negative integers.