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 \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.

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

Search this blog


Most recent comments

  • 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

Blog archive

Not signed in
Sign in

Powered by BlogBuilder