Prove this logically

The number of ways you can place five idistinguishable ping pong balls in 14 numbered bowls, with no bowl containg more than one ball, is exacly the same as the number of ways you can place five ping pong balls in ten bowls where any number of balls are in a bowl.

There are 14 places at your dining room table and a bowl at each place. Place the 5 ping pong balls in the bowls in all possible ways. The number of different ways to arrange all the balls is X.


Now, stack all the bowls on one place. There are still X ways to arrange all the balls in the 14 bowls.


The same holds true for 1 bowl at 9 places and 5 bowls at one place. There are still X ways to arrange the balls in the 14 bowls.

First try: It seems intuitive that this will probably be so because you are reducing the number of bowls by the same amount that you are increasing the number of balls allowed in any bowl. In a very simple case it works with 3 bowls/2 balls only one ball per bowl vs. 2 bowls, one or two balls per bowl. I picture a sort of 3-D matrix or geometrical figure and sense that you are merely shifting length from one side to another, thus keeping the volume the same.


I just had a cup of green tea and maybe it will become clearer after a brisk walk.

picture the four extra bowls as 'virtual' bowls 'above' one or more real bowls.


brad

OK, everyone so far seems to be getting this in concept I think...but nobody has yet PROVED it.


I usually found proofs rather difficult.

My first post missed a lot.


"There are 14 places at your dining room table and a bowl at each place. Place the 5 ping pong balls in the bowls in all possible ways. The number of different ways to arrange all the balls is X."


This is ok. In fact, the number of ways is 14choose5 = 2002.


If you start "stacking" bowls, you run into a problem. For example, if we stack bowl 14 on bowl 13, we can see the difference between an empty bowl 13 and ball in bowl 14 and vice versa. However, in the actual problem, those orderings look exactly the same because the ball in bowl 14 will "drop" into bowl 13.


Because the two arrangements will look exactly the same in the problem, we don't have to consider any ordering with one bowl stacked on another that does not have balls in both bowls. Thus, instead of stacking bowls, its better to break the problem into parts. In this example, it would be: 1) arrangements with a single ball per bowl; and 2) arrangements with one double ball and three single balls.


Expanding this back to the original problem, the five balls will appear in the bowls as 5 singles, a double and 4 singles, two doubles and a single, a triple and a double, a quadruple and a single, or a quintuple. It's convenient to break up the problem accordingly. However, with all but the singles and the quintuple, the "objects" placed in the bowls are different (a single is different than a double), so we have to take order into account.


Looking at the double and three singles, we can further break it down by realizing that the double doesn't affect the relationship of the singles ordering to each other. We can save a place for the double, calculate the number of combinations for the singles, and then multiply by the number of possible places for the double. Thus for this part, there are 10*(9choose3) arrangements for the double and three singles in the ten bowls. Applying this to parts of the problem with multiple kinds of the same object gives us:


10choose5 ways to place single balls;

10*(9choose3) ways to place a double and 3 singles,

10*(9choose2) ways to place a single and two doubles, and

10*(9choose2) ways to place a triple and two singles.


The parts with 2 distinct objects to place are simple permutations:


10permut2 ways to place a triple and a double, and

10permut2 ways to place a quadruple and a single.


Finally, there are 10 ways to place a quintuple. Adding them all up we get 2002 = 14choose5.


Sheesh, there goes my day.

I didn't follow all your figures, but I feel intuitively that if you consider it as a 3D matrix rather than a 2D, it might work better. The original line of 14 bowls is already 2D once we consider the different arrangements of balls, perhaps.


Why does this stuff seem so hard (to me too, in certain ways). It isn't all that complicated is it? I think many of us just aren't used to it.

you can do a rigorous proof showing that the two sets are equivalent or have a one to one correpsondence or something, but its a little advanced for me.


brad

I just now went for my walk and I guess it cleared away a few cobwebs.


When you take away the 4 bowls, imagine that they become "invisible bowls" to be used only when more than one ball is placed in any standard bowl. Now whenever you place an extra ball in a bowl, it resides inside one of the "invisible bowls." Thus you still have 14 slots in which to place the 5 balls in. Also, to illusrate this more clearly, since the bowls are each numbered, let's leave their respective numbers on the "invisible bowls." Now nothing has really changed.


Is it a proof? I doubt it, but it shows how it works.

Any combination of 5 balls in 10 bowls can be represented by a string of 0s and 1s where the 0s represent a bowl and the following 1s represent the number of balls in that bowl. For example 011011010000000 would represent 2 balls in the first bowl, 2 in the second and 1 in the third. The sequence always starts with a 0 and is 15 digits long. The number of ways to form these strings is the same as the number of ways to put 5 1s in 14 positions, which is the number of ways to put 5 balls in 14 bowls.

Except I would have use B's and P's.