I've been reading and studying about Permutations, Dispositions and Combinations recently. The problem I've facing since yesterday (and I've not been able to find a solution either in my own or on the Internet) is the following:
Suppose we want to fill an amount $n$ of distinguishable boxes with $k$ indistinguishable elements, but each box has a maximum capacity. It is, the $i$-th box will have a capacity $c_i$, so we can't place more than $c_i$ elements in the $i$-th box. The amount of elements $k$ is lower than the sum of all capacities, or: $\sum_{i=1}^n c_i > k$, meaning that we could place all elements inside the boxes.
We could also denote this problem as trying to find how many solutions will have the following equation: $$ \sum_{i=1}^n c'_i = k $$ where $0 \leq c'_i \leq c_i$ (by following the Example 2 here).
It will be understood as we can split $k$ in the sum of $1$s (or elements) that can be placed (or not) in the $n$ boxes. So, we have the boxes $b_1$, $b_2$, …, $b_n$, and in the box $b_i$, which capacity is $c_i$ we can place $c'_i$ elements inside of it, where $0 \leq c'_i \leq c_i$, and we want to know the amount of ways in which we can do it. (Note: It is allowed that some boxes remain empty in some cases, since $c'_i$ could be also $0$).
Is there a formula for that? I've found formulas for other cases but not for this one in particular, involving a fixed capacity for each of the boxes.
Thanks for your help!
Best Answer
I think I figured it out. I was looking at this this post (which is not the same problem as the one I'm describing, but it's similar) and by reading the solution proposed by the user Jyrki Lahtonen (thank you!) I was able to work out the solution for what I was looking for.
So, the thing is the following:
We can start by considering the case in which all boxes have infinity capacity. We can proceed by using the result of the series: $$\sum_{i=0}^\infty x^i = \frac{1}{1-x}, \quad \text{ for } |x| < 1$$ If we derivative this equation a total of $k-1$ times, and manipulate the results we will have: $$(1-x)^{-k} = \sum_{p=0}^\infty \binom{p+k-1}{k-1} x^p, \quad \text{ where } \binom{p+k-1}{k-1} = \frac{(p+k-1)!}{(k-1)!p!}$$
Here, $x^p$ is just a place holder, its only purpose is to label the term that multiplies it, which is a combinatoric term which corresponds to the number of ways in which we can arrange an amount $p$ of elements in an amount $k$ of boxes, all of the boxes with an infinity capacity.
The boxes are distinguishable (we will know the difference between box 1 and box 2, for example) but the objects are not (we know that a box contain 2 elements, but all elements are the same).
The useful thing about this is that we can rewrite $(1-x)^{-k}$ as: $$(1-x)^{-k} = (1 + x + x^2 + x^3 + \cdots )^k$$
And consider that $k$ is the amount of boxes and the exponent of the higher exponent of $x$ will correspond to the capacity of each of the boxes, being infinity up to now.
So, if we consider the following: $$(1 + x + x^2 + x^3 + \cdots + x^c)^k$$ we will think about an amount $k$ of boxes, each of which has a capacity $c$ of elements you can place inside.
We can think for one box first $k=1$) which capacity $c$. We can place any number of elements from $0$ to $c$ inside, and we will have then $1$ possible combination for each fixed amount of element, and $c$ combinations if we consider all the possibilities of choice for the amount of elements.
For two boxes ($k=2$), the way in which we can arrange them is the multiplication of all the possible ways we can arrange each of the boxes, being: $$(1 + x + x^2 + x^3 + \cdots + x^c) \times (1 + x + x^2 + x^3 + \cdots + x^c) = (1 + x + x^2 + x^3 + \cdots + x^c)^2$$
This can be seen as for each of the combinations of the first box we can have all combinations of the second one, if the amount of elements allows it.
The same will go then for an amount $k$ of boxes. If we expand that term we will have a polynomial of degree equal to $k \cdot c$, like this: $$(1 + x + x^2 + x^3 + \cdots + x^c)^k = \sum_{p=0}^{k \cdot c} \alpha_p \: x^p$$
So, if we want to know the number of ways in which we could arrange $p$ elements in $k$ boxes of capacity $c$, we only have to expand the previous term and look for the coefficient of the term $x^p$, which will be $\alpha_p$.
Finally, if each box has a particular capacity $c_i$ (for the $i$-th box) we will have a possible number of ways to arrange the $i$-th box based on $(1 + x + \cdots x^{c_i})$, and we have to multiply all of the possible number of ways for each box to get all the possible number of ways for the set of $k$ boxes, having: $$\prod_{j=i}^k \left( \sum_{i=0}^{c_j} x^i \right) = \sum_{l=0}^{c_1 + \cdots + c_k} \alpha_l \: x^l$$ and here, by choosing a value of elements $p$, such that $0 \leq p \leq c_1 + \cdots + c_k$, the coefficient $\alpha_p$ will tell us the number of ways in which we can arrange $p$ elements in $k$ boxes with capacities $c_i$ individually. And if we want to know the number of ways for all possible values of $p$, we only need to sum all the possible values of the $\alpha$'s, and that's it.
Hope it helps somebody else!