Number of ways to distribute $170$ identical things in $12$ boxes where each box has different capacity.

Question

Suppose you have a lot of boxes which can accommodate either $1, 5, 10, 20$ or $50$ items. You need to arrange $170$ items in $12$ boxes only (nothing less, nothing more). In how many ways can you make this distribution? Is there any formulae based approach to this?

Example: One solution is $10 \times 7 + 20 \times 5 = 170$, i.e., $7$ boxes of $10$ capacity and $5$ boxes of $20$ capacity.

Also, all the boxes must be filled to the full capacity.

Answer 1

Before a (true) mathematician brings a closed formula, here is a recursive algorithm.

Given the constraints on the sum (170) and the number of boxes (12), the complexity remains low.

Because of that, even without a computer, the number of solutions appears to be likely reasonable (it is, as the algo gives 35 solutions only).

Here is a generic code algo for $f$, a recursive function

array arr = [ 50,20,10,5,1 ]
array mul  // multiplicands (5 items, the first is for 50 ...)

f(i, b, s) {    // i index in arr, b current nb of boxes, s current sum
     j = 0
     while ( j + b <= 12 ) 
     do
          mul[i] = j;
          sum = s + j*arr[i];
          if ( sum > 170 OR (sum = 170 AND j+b <> 12) ) return
          if ( sum = 170 ) 
          do
                for k:=0 to i
                     if (mul[k] > 0)
                          print " ", mul[k], "x", arr[k]
                
                print RETURN
                return
          end if
          if (i < 4) f(i+1, b+j, sum) // recursive call
          
          j = j + 1
     end if
end f

And a C implementation

int arr[] = { 50,20,10,5,1 };
int mul[] = { 0,0,0,0,0 };

void f(int i, int b, int s) {
     for(int j=0 ; j+b <= 12 ; j++) {
          mul[i] = j;
          int sum = s + j*arr[i];
          if ( sum > 170 || sum == 170 && j+b != 12) {
                return;
          }
          if ( sum == 170 ) {
                for(int k=0 ; k<=i ; k++)
                     if (mul[k])
                          printf(" %dx%d", mul[k], arr[k]);
                printf("\n");
                return;
          }
          if (i < 4) {
                f(i+1, b+j, sum);
          }
     }
}

Calling f(0,0,0); gives

 5x20 7x10
 6x20 4x10 2x5
 7x20 1x10 4x5
 1x50 1x20 10x10
 1x50 2x20 7x10 2x5
 1x50 3x20 4x10 4x5
 1x50 4x20 1x10 6x5
 2x50 4x10 6x5
 2x50 1x20 1x10 8x5
 2x50 2x20 2x10 1x5 5x1

Answer 2

Use casework . . .

Let $x_k$ be the number of selected boxes of capacity $k$.

Necessarily $0\le x_{50}\le 3$.

Consider $4$ cases based on the value of $x_{50}$.

Each case reduces to a subproblem using boxes of capacity at most $20$.

Each subproblem works out fairly easily, using cases based on the value of $x_{20}$.

For example, if $x_{50}=0$, then we must have

• $x_{20}\ge 5$, else if $x_{20}\le 4$, more than $12$ boxes would be needed.$\\[4pt]$
• $x_{20}\le 7$.

so the case $x_{50}=0$ yields $3$ subcases.

Using the above approach, I found $10$ ways:

$$ \begin{array} {|c|c|c|c|} \hline x_{50}&x_{20}&x_{10}&x_5&x_1\\ \hline 0&5&7&0&0\\ \hline 0&6&4&2&0\\ \hline 0&7&1&4&0\\ \hline 1&1&10&0&0\\ \hline 1&2&7&2&0\\ \hline 1&3&4&4&0\\ \hline 1&4&1&6&0\\ \hline 2&0&4&6&0\\ \hline 2&1&1&8&0\\ \hline 2&2&2&1&5\\ \hline \end{array} $$

As an alternative, if a Computer Algebra System (CAS) is allowed, the following $4$-line Maple program

verifies that the number of ways is $10$.

Answer 3

You want the coefficient of $q^{12}t^{170}$ of the product $$ \prod_{s\in S}\frac{1}{1-qt^s}$$ where $S=\{1,5,10,20,50\}$. Wolfram|Alpha says this is 10. The code

Coefficient[SeriesCoefficient[1/((1-t*q)*(1-t^5*q)*(1-t^10*q)*(1-t^20*q)*(1-t^50*q)),{q,0,A}],t^B]

will give you the answer for a total of $A$ boxes and a total sum of $B$. To see this, consider finding the coefficient of $q^At^B$ in the product above. A generic factor is of the form $(1+qt^s+q^2t^{2s}+\cdots)$ so the coefficient of $q^At^B$ can only be of the form $q^{\sum_i s_i} t^{\sum_i n_is_i}$ where the $s_i$ are distinct elements of $S$. Then the $q$ coefficients tracks the total sum, while the $t$ coefficient tracks the weighted sum.