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.

I'm trying to find a way to calculate a problems such as this: if you have $n$ objects and $k$ indistinguishable boxes, how do you put in $n$ objects such that each box has no more than $C$, where $C \le k$.

For example, I have $6$ objects that need to be placed in $4$ boxes, where no box can have more than $4$ objects in it. I tried $\displaystyle\binom{n+k-1} {k-1}$. I got $84$ ways. But that is too big. When I do it by hand, I get $74$.

Would like actual explanation.

share|improve this question
add comment

2 Answers 2

Added: The answer below is based on the assumption that your calculation with $\binom{n+k-1}{k-1}$ was relevant. However, this is the case if and only if the it is the objects that are indistinguishable, and the boxes can be distinguished, which (I now note) contradicts your statement of the problem. If in fact the boxes are indistinguishable, then the problem is altogether different. If the objects are distinguishable, the answer will involve Stirling numbers of the second kind; if not, it will involve partitions of an integer and be even messier.


You start with the $84$ ways that you calculated, but then you have to subtract the distributions that violate the upper limit. This is a standard inclusion-exclusion argument; the actual result for essentially this problem can be found in this question and answer.

In more detail: A first approximation to the desired result is, as you tried, $\dbinom{n+k-1}{k-1}$. However, this counts all possible distributions, not just that have at most $C$ objects in each box, so it’s necessary to subtract the distributions that violate this limit. We’ll first count the distributions that violate it for the first box. Those all have at least $C+1$ objects in the first box, so we can count them by first putting $C+1$ objects in Box 1 and then distributing the remaining $n-C-1$ objects freely amongst the $k$ boxes. This can be done in $$\binom{n-C-1+k-1}{k-1}=\binom{n-C+k-2}{k-1}$$ ways. There are just as many distributions that violate the limit on the second box, just as many again that violate it on the third box, and so on through the $k$ boxes, so there are (to a first approximation) $$k\binom{n-C+k-2}{k-1}$$ distributions that violate it for at least one box. That leaves us with $$\binom{n+k-1}{k-1}-k\binom{n-C+k-2}{k-1}\tag{0}$$ acceptable distributions as a second approximation.

Unfortunately, we’ve now subtracted too much, if $n$ is large enough: a distribution that violates the limit for two boxes has been subtracted twice. Thus, we must add back in all distributions that violate the limit for two boxes. Pick a pair of boxes; how many distributions violate the limit for both boxes of that pair? Those are the distributions that have $C+1$ objects in each of the two boxes and the remaining $n-2C-2$ objects distributed arbitrarily amongst the $k$ boxes. There are $$\binom{n-2C-2+k-1}{k-1}=\binom{n-2C+k-3}{k-1}$$ such distributions. And there are $\binom{k}2$ pairs of boxes, so altogether we must add back in $$\binom{k}2\binom{n-2C+k-3}{k-1}$$ distributions to get a third approximation of $$\binom{n+k-1}{k-1}-k\binom{n-C+k-2}{k-1}+\binom{k}2\binom{n-2C+k-3}{k-1}$$ acceptable distributions.

This time we’ve potentially added too much: distributions that violate the limit for three boxes have been added back in more than once, so we have to subtract a correction. And then we’ll have to correct for having subtracted too much in the case of distributions that go over the limit for four boxes. And so on.

The correction for distributions violating the limit for $i$ boxes must be made for every one of the $\binom{k}i$ sets of $i$ boxes, so it will have a factor of $\binom{k}i$. As you can see from the pattern up to this point, it will be a positive correction if $i$ is even and a negative correction if $i$ is odd; this can be handled with a factor of $(-1)^i$. Finally, the number of distributions that go over the limit on a particular set of $i$ boxes is

$$\binom{n-iC-i+k-1}{k-1}=\binom{n-iC+k-(i+1)}{k-1}\;,$$

so the correction term is $$(-1)^i\binom{k}i\binom{n-iC+k-(i+1)}{k-1}\;.\tag{1}$$

The original approximation of $\dbinom{n+k-1}{k-1}$ is simply $(1)$ with $i=0$, so the final answer is $$\sum_{i\ge 0}(-1)^i\binom{k}i\binom{n-iC+k-(i+1)}{k-1}\;.$$ Of course all terms with $i>k$ are $0$, so this is a finite sum.

In general there isn’t a simple closed form. To get that, you have to know something about $C$ and $n$. For example, you can’t exceed the upper limit on more than one box if $n<2C+2$; if that’s the case, only one correction term is non-zero, and you can simplify the answer to $(0)$.

share|improve this answer
    
@user9915: If you simply want to be able to compute the result correctly, you should be able to plug into the formula that I gave in the other answer. Yes, you’ll have to change the names of the quantities, but that’s a triviality. If you want a full explanation, it would have been helpful to have said so in the question, rather than simply asking for ‘a way to calculate’ the result. And if you got no help from the cited article on inclusion-exclusion, it would be helpful if you said just what you don’t understand. –  Brian M. Scott Mar 15 '12 at 2:53
    
Yes, I want a full explanation. Also, from linked answer: "Place 10 identical balls in 5 distinct containers with no more than 4 balls in any container. We see that if left unconstrained, 1 or 2 containers may violate the restriction, so we allot 5 balls each to 1 or 2 containers, and correct for such configurations to get..." Why do only 1 or 2 containers violate the restriction? –  larry Mar 15 '12 at 2:55
    
The inclusion - exclusion argument is what I don't understand. Only one guy said anything remotely about it, and it didn't make any sense. –  larry Mar 15 '12 at 3:10
    
(n−C+1+k−1k−1)=(n−C+k−2k−1) ... mmm... where is this coming from. And is the first 1, supposed to be -1 or +1? –  larry Mar 15 '12 at 3:46
1  
@user9915: Without a clearer idea of just what it is that you don’t understand, I doubt that I can help much; I’ve already included explanation of where every part of the formula comes from. –  Brian M. Scott Mar 15 '12 at 14:10
show 2 more comments

First, I want to be clear about your problem. There are, in general, 4 types of such problems: you may place distinguishable/indistinguishable objects into distinguishable/indistinguishable boxes.

Consider this example: you have 3 objects and 2 boxes. If neither objects nor boxes are distinguishable, then you have 2 cases only: either put all three objects into one box, or put one in a box and put two others in the other box. If the objects are distinguishable, then you have 1+3=4 cases: when you put one object separately, you have 3 choices to decide which one. If the boxes are distinguishable but objects are not, then you have 2+2=4 different combinations (this case is where your expression $\binom{n+k-1}{k-1}$ belongs to). Finally, if everything is distinguishable, then you have 2+2*3=8 combinations.

Then, there are some variations of each type of the problem, like the minimum number of objects in each box (e.g. the boxes must be non-empty), or the maximum number of objects (your problem) etc.

So, I think your expression $\binom{n+k-1}{k-1}$ is for the case when there is no restriction ($C\ge n$), and, more importantly, the boxes are distinguishable, while in your original question your clearly say that the boxes are indistinguishable. Although, I have no idea how you got 74...

This little difference leads to a lot of trouble.

If objects and boxes are indistinguishable, then this problem is closely related to the the one of partitioning of integer numbers. Consider the following question: what is the number of ways one can represent a positive integer number $n$ as a sum of positive integer numbers? This question must be MUCH EASIER to address: first, there is no restriction $C$ on how big the terms of the sum could be (i.e. the case $C\ge n$), and, second, there is no restriction on the number of terms in the sum (which corresponds to no restriction on number of boxes in your problem, i.e. the case $k\ge n$).

As an example on how the problems are related: suppose you have $n=C=k=4$, then you can either put all 4 objects into one box, or put one in a box and three others in another, or put 2 in a box and two others in another, or put 2 and 1 and 1, or all four in different boxes. This corresponds to the partitioning of 4 as a sum: 4=4=3+1=2+2=2+1+1=1+1+1+1.

Once again, this is an easier question, and often referred as the number of unrestricted partitions. Yet, this has no closed form solution, only generating function (thanks to Euler) and recursive expressions.

Here is the sequence of the number of partitions of $n$ into at most $k$ parts (still, no restriction by $C$): OEIS A026820. You can also start reading about the partition function, for example, here: Wolfram MathWorld on Partition Function.

share|improve this answer
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.