Intereting Posts

Can $x^{n}-1$ be prime if $x$ is not a power of $2$ and $n$ is odd?
which are positive definite matrix
If $xy+xz+yz=3$ so $\sum\limits_{cyc}\left(x^2y+x^2z+2\sqrt{xyz(x^3+3x)}\right)\geq2xyz\sum\limits_{cyc}(x^2+2)$
$\epsilon – \delta$ definition to prove that f is a continuous function.
Iterating through the integerial points of $f(x)$
Bezouts Identity for prime powers
Continuity of the Characteristic Function of a RV
Find the norm of the following operator.
Mathematical and Theoretical Physics Books
Proof that $\dim(U_1+U_2) = \dim U_1 + \dim U_2 – \dim(U_1\cap U_2)$
What are some counter-intuitive results in mathematics that involve only finite objects?
$2 \otimes_{R} 2 + x \otimes_{R} x$ is not a simple tensor in $I \otimes_R I$
How do you use the BBP Formula to calculate the nth digit of π?
Diophantine quartic equation in four variables
pigeonhole principle and division

I think there are $\binom{b+ c – 1}{c-1}$ ways to distribute $b$ balls in $c$ containers. (Please correct me if that’s a mistake.) How does this change if I am not allowed to place more than $n$ balls in any given container?

If we call this number $N(b,c,n)$ then I can come up with

$$N(b,c,n) = \sum_{k=0}^n N(b-k, c-1, n)$$

- Proof of $k {n\choose k} = n {n-1 \choose k-1}$ using direct proof
- Nice problem of combinatorics..
- Number of solutions to $a_1 + a_2 + \dots + a_k = n$ where $n \gt 0$ and $0 \lt a_1 \leq a_2 \leq \dots \leq a_k$ are integers.
- Permutations with a cycle $>\frac{n}{2}$
- Exponential generating function for restricted compositions
- Symmetry of bicycle-lock numbers

with the base cases

$$N(b,c,n) = \binom{b+ c – 1}{c-1}$$

for $n\geq b$, and

$$N(b,c,n) = 0$$

for $n<b/c$.

Is there some better way of writing this than that recursion relation?

- Subsets with small interaction.
- How to find the number of anti-symmetric relations?
- Probability question - arranging 20 pupils in a row - 8 boys and 12 girls
- How many numbers between $100$ and $900$ have sum of their digits equal to $15$?
- A positional number system for enumerating fixed-size subsets?
- No. of possible solutions of given equation
- Number of positive integral solution of product $x_{1} \cdot x_{2} \cdot x_{3}\cdot x_{4}\cdot x_{5}=1050$ is
- Distinct digits in a combination of 6 digits
- No two identical ranks together in a standard deck of cards
- Maximal Hamming distance

If you carry out the inclusion-exclusion argument mentioned by true blue anil in general, you get

$$N(b,c,n)=\sum_i(-1)^i\binom{c}i\binom{b+c-1-i(n+1)}{c-1}\;;$$

whether this is actually any more useful than the recurrence is another question.

You could use inclusion-exclusion.

I’ll illustrate with a concrete case, you can then work out the formula.

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

C(14,4) – C(5,1)*C(9,4) + C(5,2)*C(4,4) = 381

Now generalise.

This is the number of solutions to $x_1+x_2+ \cdots + x_c = b$ where $0 \leq x_i \leq n$ for $i = 1, \dots, c$.

For $n\gt 2$ you can reduce the number of additions in the recursion if you replace

$$N(b,c,n) = \sum_{k=0}^n N(b-k, c-1, n)$$

by

$$N(b,c,n) = N(b-1, c, n)+N(b, c-1, n)-N(b-k-1, c-1, n).$$

It may not be a saving, but you can avoid multiplication and division if you replace the base cases by $N(0,c,n)=1$ and $N(b,c,n)=0$ for $b\lt 0$.

As Thomas pointed out, you can use generating functions to help with this problem. Also, Brian rightly notes you could use PIE and also he observes which method is more useful computationally is a different question altogether.

Below, I will produce a standard (and in my opinion still a beautiful and more expressive) argument to prove why is $N(b,c) = {{b+c-1}\choose{c-1}}$.

So, let us assume that you have got $b$ bananas you want to distribute among $c$ children. Some children can get $0$ bananas and you want to give away all $b$ bananas. Now let us imagine that you have $c-1$ “fake bananas” which are added to your initial stock giving a total of $b+c-1$ bananas. You can imagine that the bananas left to the first fake banana $c_1$ are reserved for child $C_1$. The bananas between fakes $c_i$ and $c_{i+1}$ are reserved for child $C_i$ for all $i < c-1$ and the last child gets all bananas to the right of fake banana $c_{c-1}$. Thus, the number of ways you can distribute these bananas is precisely equal to the places where you can have $c-1$ fake bananas among $b+c-1$ bananas. And the number of bananas, therefore is ${{b+c-1}\choose{c-1}}$.

I know this does not really answer your question but it is good to know about this argument in case you do not know it already.

- If $X$ is a connected subset of a connected space $M$ then the complement of a component of $M \setminus X$ is connected
- Topology and Arithmetic Progressions
- $u$ is a $C^2$ solution of $u_t – \Delta u = f(u)$ and $u=0$ on $\partial\Omega \times (0,\infty)$. Show if $u(x,0) \geq 0$, then $u(x,t) \geq 0$
- Is $1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\frac{1}{5}-\cdots=\ln 2$ true?
- Express roots in polynomials of equation $x^3+x^2-2x-1=0$
- How to evaluate the integral $\int \sqrt{1+\sin(x)} dx$
- 5-color graph problem
- Are there an equal number of positive and negative numbers?
- A polynomial can be considered a number?
- Splitting of the tangent bundle of a vector bundle and connections
- d'Alembert functional equation: $f(x+y)+f(x-y)=2f(x)f(y)$
- On average, how many times must I roll a dice until I get a $6$?
- Limit evaluate $\lim_{x\to0}{{\frac{\ln(\cos(-5x))}{\ln(\cos(-3x))}}}$
- How does one compute the sign of a permutation?
- Are these two statements equivalent?