One of balls and urns

Question

This is a question I came up with while reading the description of an algorithm for solving a classic puzzle. I'm asking this just to satisfy my own curiosity and maybe learn some useful things from combinatorics.

There's many ways to model the problem, but let's use balls and urns:

Let's say that you have 4 distinguishable urns (let's call them $A$, $B$, $C$ and $D$) and 15 balls of 4 distinguishable types (let's call them $a$, $b$, $c$ and $d$) such that you have 4 balls of each of $(a, b, c)$ and 3 $d$ balls. As you can see, one (natural) way of placing the balls in the urns is putting the four a's in A, the four b's in B, and so on.

So far so good. Now here's the complication I don't know how to deal with: let's assume that the four urns have a fixed capacity to hold a maximum of four balls. So, you can notice that no matter how you divide the balls in the urns, there will always be 3 urns completely full, and one with a single "empty" space.

The question is, how many different ways are there to divide the balls in the urns? There's a number in the URL I referenced in the first paragraph, and I guess I could verify it by writing a program to do it by brute force, but I'd like to know if there's a way to tackle this purely with mathematical reasoning.

In addition, how about if we generalize the problem? Instead of 4 urns, we have $X$ urns, and we have $K$ balls of $X$ types (feel free to assume anything you want for the rest of the details of the general problem).

Thanks.

---

Edit 1: In case it helps, here's a few more details. As you can gather from the link, this problem is somewhat related to the 15-puzzle. Think of the urns as the rows in the puzzle. Think of the balls as the tiles with the numbers 1 to 15. A "type" of ball represents the row a certain tile belongs to; for example, tiles 1 to 4 belong to row 1 (so they're balls of type $a$), tiles 5 to 8 belong to row 2 (they're balls of type $b$), etc.

The number is in the URL under the section "WK (Walking Distance)", in the paragraph that says "The number of distinct tables is...".

Also, you could certainly represent this as having 5 types of balls, and then you have 16 balls (4 of type $a$, 4 $b$, 4 $c$, 3 $d$ and 1 $e$). The question remains, how many ways are there to put all the balls inside the four urns, considering their capacities?

Answer 1

I've worked on something related to this. It's not strong enough to solve this problem, but it might send you down the right path.

This same urn-ball model solves the following problem: Consider the number $277830000$, which is $2^4*3^4*5^4*7^3$. How many ways are there to write this number as the product of four factors such that each factor itself has no more than four prime factors? I found$^*$ a result for this problem without the size restriction.

The number of ways to write $\prod_{j=1}^N p_j^{n_j}$ (with $p_j$ prime) as the product of $k$ factors is $$\sum_{i=0}^{k-1}\left[ (-1)^i {k \choose i} \prod_{j=1}^N T(n_j\!+\!1,~k\!-\!2\!-\!i)\right]~,$$ where $T(a,b)$ is the multichoose coefficient ($a$ multichoose $b$).

I cannot provide the proof of this right now, but it is written in one of my books at school, so I can post it here within 10 days. In any case, I do have some of the big ideas:

We interpret $i$ to be the number of factors which are one, and so the ${k\choose i}$ counts the ways to choose which factors are one. The multichoose coefficient counts the ways to put the copies of the primes into the various final factors. That's why we take the product over $j$, which is just the index of the number of primes we have in the original number (which means the number of rows in the 15-puzzle interpretation). The -1 obviously comes from inclusion-exclusion, but I admit I have forgotten why it is needed.

As I have said, it doesn't answer your question. In particular having a factor of one translates to an empty row, which is obviously not possible. Although I'd have to see the details of the proof to be sure, I think that means we can bound the number from above (poorly) by the $i=0$ case: $$\prod_{j=i}^N T(n_j+1,~k-2)$$ In the 15-puzzle application, this works out to $T(5,2)^3T(4,2)=33750$, which is indeed greater than the known answer $24964$. In this case, it is also bounded by including the $i=1$ case, but this seems more likely to be a coincidence.

($^*$ I did discover it independently, although it may be a well-known result)

Answer 2

As suggested, add an extra ball type $*$, and as many balls of type $*$ as are needed to fill all urns to their maximum capacity. Then, encode a placement of balls into urns as the matrix $(m_{ij})$ whose $(i,j)$th entry is the number of balls of type $i$ in urn $j$. The problem then becomes the problem of counting rectangular matrices of nonnegative integers such that each row has a specified sum (the number of balls of a given type) and such that each column has a specified sum (the maximum urn capacity.)

Many people have looked at this problem and similar problems. See for example, here, here, here, here, and here.

Supposing that the matrix is $m$ by $n$, the row sums are $r_1$, $\dots$, $r_m$, and the column sums are $c_1$, $\dots$, $c_n$, the count is the coefficient of $$ T({\bf x}, {\bf y}):=x_1^{r_1}\dots x_m^{r_m} y_1^{c_1} \dots y_n^{c_n} $$ in the generating function $$ G({\bf x}, {\bf y}):=\prod_{i,j} \frac{1}{1-x_i y_j}. $$ This is obvious but can immediately give an upper bound: the count is no more than $$ \inf_{0<x_i<1, 0<y_j<1} \frac{G({\bf x}, {\bf y})}{T({\bf x}, {\bf y})}. $$ See the fourth paper above for some related estimates.

Answer 3

Could you not add a ball of type "x" to the pre-distribution collection, proceed with the solution to the more complicated problem, then throw the "x" ball away?