Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
I guess that balls of same colour and undistinguishable and that the order of the balls in each urn does not matter? –  leonbloy Jan 14 '13 at 21:08
    
I'm probably just dense, but I couldn't find the number in the link above :S –  Eric Stucky Jan 14 '13 at 21:14
    
Stirling numbers? There's something about distinguishable boxes that makes me believe this is possible... –  Looft Jan 14 '13 at 21:22
    
@eric-stucky - I have added more details :). Thanks –  E.D. Jan 14 '13 at 21:27
    
@leonbloy: If I understand you correctly, the answer is yes to both things. –  E.D. Jan 15 '13 at 2:18
add comment

3 Answers

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)

share|improve this answer
    
Actually, if you wouldn't mind, please send me an email. If you click my name at the bottom of the answer, you'll be taken to my profile, where on the right hand side you will find an email at which you can contact me. –  Eric Stucky Jan 14 '13 at 22:45
    
Interesting stuff. I'll need some time to digest most of the things you mention (and even then, there are some things I'm not sure I'm ready yet to grasp), but it certainly gives me something to start with. Thanks. –  E.D. Jan 15 '13 at 2:20
    
By the way, believe it or not, I don't use email... sorry. Did you want to send me some reference material or something? –  E.D. Jan 15 '13 at 2:27
    
@E.D.: No, I just want a way of communicating with you personally because this problem played a relatively foundational part in my math education. Knowing that someone else is interested in it might inspire me to continue working on it. Sharing numerical evidence, speculative patterns, etc. ("Chatty" discussion is discouraged on the main site.) How did you sign up for SE without an email? I would be willing to contact you some other way. –  Eric Stucky Jan 15 '13 at 2:30
add comment

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.

share|improve this answer
    
Another reference: www-c.eco.unibs.it/~stateap/vol1-n2_file/Greselin.pdf –  leonbloy Jan 26 '13 at 3:41
add comment

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?

share|improve this answer
    
I think this works (at least for the motivating example), but now the problem is that we have five types of indistinguishable balls with quantities $(4,4,4,3,1)$ and we are trying to determine the number of ways to partition them into four urns. This strikes me as still a difficult question. –  Eric Stucky Jan 14 '13 at 21:10
    
Oh, also you still have the "at most 4 in each urn" restriction, or else you would count putting them all in urn 1 as valid. –  Eric Stucky Jan 14 '13 at 21:18
    
I was addressing the original problem, where I would have 16 balls to put into the four urns, with exactly 4 balls in each urn. The addition of a new "type-x ball would of course complicate things. –  User58220 Jan 14 '13 at 21:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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