#
All entries for Sunday 30 October 2011

## October 30, 2011

### Balls in boxes and other miscellaneous thoughts

It is a reasonably common statement in probability that problems can be simplified down to spinners or balls in boxes. So:

Let there be k balls that we wish to place in n boxes. If we can distinguish between the balls, then each ball can go in n different places, so the total is . If we cannot distinguish between the balls, this is answered by the occupancy theorem: the multiset formula for n and k.

What, then, if it is the boxes we cannot distinguish between? If the balls also cannot be distinguished between, this is equivalent to partitioning k into at most n parts. The OEIS implies that this has a closed-form solution: , which is nice to know, even if it suggests there’s no ‘nice’ combinatorial solution.

If we can distinguish between the balls but not the boxes, I believe this would come to a sum of Stirling numbers of the second kind: .

Other miscellany: Mario Micallef told us a few integration tricks this week: being able to cancel entire functions while integrating from 0 to 2pi (due to them containing sine), by comparison with across the same interval. Massively time-saving tricks I’d never considered before. Great!

From combinatorics: wondered if there was a way to check transitivity of a relation expressed in matrix form quickly. Found nothing more than checking each row one step at a time, but I least I can do that fairly quickly now.