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 question appeared as an unsolved exercise in an introductory combinatorics textbook:

We have a bag with as many identical balls as necessary. We take out i balls and put them in 10 numbered boxes, such that the number of balls in box 1 $\leq $ the balls in box 2 $\leq $ ... $\leq $ the number of balls in box 10 $\leq $ 20. How many ways are there to do this?

A hint is provided (sorry for the shoddy translation): "Think of the sum of the series of differences of the amount of balls in adjacent boxes. The first difference equals the amount of balls in box 1".

Background: Earlier today I asked this question: Number of integer solutions if $x_1\leq x_2\leq x_3\leq ...\leq x_r\leq k$. The question itself was based on this exercise, so I was quite baffled to receive relatively complex answers. I figured I'll ask the question as it appeared, to see if maybe my 'generalisation' made this more complex than it should've been by omitting details.

Thank you for your help as always.

share|improve this question
    
Just to make sure, in this problem the total number of balls $i$ may vary, but there are always $10$ boxes and the maximum number of balls in the last box is fixed at $20$. Correct? –  AMPerrine Oct 28 '11 at 17:26
    
As in the hint, consider such a sequence $x_1,\dots,x_{10}$. Look at the sequence of differences $d_i$, where $d_1=x_1$, and note that $\sum d_i=x_{10}$. Counting the number of sequences $(d_k)$ is a "stars and bars" (or sum) problem. Very doable. Counting "compositions" (order matters) tends to be not hard. Counting partitions (order irrelevant) is generally hard to very hard. –  André Nicolas Oct 28 '11 at 17:38
    
Compositions and partitions are often difficult, but this case (weak composition with fixed size) is one of the simplest: goo.gl/YYiee –  leonbloy Oct 28 '11 at 17:38
add comment

1 Answer

up vote 3 down vote accepted

You didn't make this more complex by omitting details, but by adding them. In that other question, you had a fixed sum $k$. The present question doesn't place any requirements on the sum, and that makes it a lot easier. As the hint provided indicates, there's a bijection between the configurations to be counted and the ways of distributing $20$ balls into $11$ boxes: If we denote the number of balls in box $j$ by $n_j$ and add two extra numbers $n_0=0$ and $n_{11}=20$, the $11$ differences between these numbers add up to $20$, and each such sequence of differences determines one of the desired configurations and vice versa. So the desired number is

$$\binom{20+11-1}{11-1}=\binom{30}{10}=30045015\;.$$

share|improve this answer
    
But it says, "we take out i balls and put them in 10 numbered boxes," so don't we need an answer that depends on $i$? –  AMPerrine Oct 28 '11 at 17:38
    
Thank you very much. –  roel Oct 28 '11 at 17:39
    
@AMPerrine: Hmm, I guess you're right, in a sense. There seems to be a contradiction between that and "with as many identical balls as necessary". That doesn't really make any sense in your interpretation, whereas the $i$ doesn't make sense in mine. Hmm... –  joriki Oct 28 '11 at 17:43
    
This is my fault, sorry! The original question reads roughly: "We pick out some balls and put them in 10 different numbered boxes ... ". It was easier to translate with the 'i' in there, but math is a tough language and didn't want to bend its rules to my favor! I am quite convinced joriki's answer is correct. –  roel Oct 28 '11 at 17:45
    
@roel: ! That must be the most original explanation for introducing a misleading variable that I've heard in quite a while :-). How does adding a variable that isn't there in the original make it easier to translate? –  joriki Oct 28 '11 at 17:47
show 2 more comments

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.