## 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 $\textstyle n^k$. 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: $\textstyle \frac{1}{n!} \frac{d^n\left( \frac{1}{\prod_{i=1}^k(1-x^i)} \right)}{dx^n}(0)$, 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: $\sum_{i=0}^n \left\{\begin{matrix} k \\ i \end{matrix}\right\}$.

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), $\textstyle\int_0^{2\pi}sin^2(x)dx=\pi$ by comparison with $\cos^2(x)$ 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.

You are not allowed to comment on this entry as it has restricted commenting permissions.

## October 2011

Mo Tu We Th Fr Sa Su
Sep |  Today  | Nov
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31

## Galleries

• Nice proof! Does this mean you're going to specialize in analysis and differential equations next ye… by Nick on this entry
• Hi Chris, It was most interesting to read your various reflections – thank you for sharing them. I'm… by Ceri Marriott on this entry
• Feel free. Chris by Christopher Midgley on this entry
• Hi Chris This is an honest final entry for the WSPA. Im glad that you have found the WSPA journey wo… by Samena Rashid on this entry
• Knowing the maximum price you would be comfortable with paying for X is extremely useful for compani… by Nick on this entry