Intereting Posts

Consider the series $ ∑_{n=1}^∞ x^2+ n/n^2$ . Pick out the true statements:
Illustration Proof that every sequence of real numbers has monotone subsequence
Convergence of a sequence with assumption that exponential subsequences converge?
What is the dot product and why do we need it?
Why don't analysts do category theory?
self similar solution for porous medium equation 3
value of $\tan(A)$
Understanding the Fokker-Planck equation for non-stationary processes
How do I get a sequence from a generating function?
Why is polynomial regression considered a kind of linear regression?
Prove that $f′(x)=f′(0)f(x)$ derivatives
How many $N$ digits binary numbers can be formed where $0$ is not repeated
Preparing for Mathematics Olympiad
Finite Sum $\sum\limits_{k=1}^{m-1}\frac{1}{\sin^2\frac{k\pi}{m}}$
A proof that the “set of all sets” does not exist in ZFC using Cantor's Theorem?

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.

- Comparing probabilities of drawing balls of certain color, with and without replacement
- About counting number of n-tuples
- To find the total no. of six digit numbers that can be formed having property that every succeeding digit is greater than preceding digit.
- How to show $\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{n}$
- Trying to find $\sum\limits_{k=0}^n k \binom{n}{k}$
- How many different sums of parts of a vector

- How many arrangements of the letters in the word CALIFORNIA have no consecutive letter the same?
- Prove that there are two frogs in one square.
- A variant of assignment problem (different sizes of sets)
- Simplifying Catalan number recurrence relation
- Bound the Number of Acute-angled Triangles
- sum of all the numbers that can be formed using the digits 2,3,3,4,4,4..
- Bijection between derangements and good permutations
- Number of partitions of $n$ with $k$ parts equals the number of partitions of $n + \binom k {2}$
- Balls in bins, probability that exactly two bins are empty
- No of n-digit numbers with no adjacent 1s.

**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)$.

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.

- how to solve this PDE
- Prove: If $\sum \limits_{n=1}^{\infty}|f_n|$ converges uniformly, so does $\sum \limits_{n=1}^{\infty}f_n$.
- Is there a bijective continuous function $f: \Bbb R \to \Bbb R$ whose inverse $f^{-1}$ is not continuous?
- A sequence of random variables that does not converge in probability.
- On the spectrum of the sum of two commuting elements in a Banach algebra
- average value theorem and calculus integration
- Do the lengths of all three segments necessarily have the same distribution?
- limit $\lim\limits_{n\to\infty}\left(\sum\limits_{i=1}^{n}\frac{1}{\sqrt{i}} – 2\sqrt{n}\right)$
- Does $i^4$ equal $1?$
- Show that if $ab$ has finite order $n$, then $ba$ also has order $n$. – Fraleigh p. 47 6.46.
- Lang's treatment of product of Radon measures
- What is the significance of the three nonzero requirements in the $\varepsilon-\delta$ definition of the limit?
- Regular monomorphisms of commutative rings
- A definite integral $\int_0^\infty\frac{2-\cos x}{\left(1+x^4\right)\,\left(5-4\cos x\right)}dx$
- Probability of two events