Re: 2015 permutation X2 marathon
[*]
Warning: beyond high school difficulty
12 counters numbered 1 to 12 are to be distributed one at a time in ascending numerical order between two distinguishable boxes A and B so that we finish with 6 in each box.
In how many ways can this be done so that at any time during the distribution process there are never more counters in box B than in box A?
Answer: 132
You can visualise this problem as counting the number of paths (consisting of moves right and moves up) along the edges of a 6x6 grid from the bottom left corner to the top right corner that always stay below the diagonal.
We will solve the generalisation to an nxn grid.
There are C(2n,n) paths in total, as we must have n horizontal and n vertical segments in our path, and we simply need to put them in some order.
We solve this problem by counting the "bad" paths.
If a path is bad it must hit the superdiagonal (the diagonal right above the main diagonal, consisting of points with y=x+1 if you were to coordinatise.)
If a path hits the superdiagonal then we can "reflect about the superdiagonal" the part of it's journey after the initial collision and obtain a path between the opposite corners of the (n-1)x(n+1) grid. (Because up until the collision with the superdiagonal we have one more vertical step than horizontal step, and afterwards we have one more horizontal step than vertical step. The reflection swaps vertical and horizontal steps so we are left with n+1 vertical steps and n-1 horizontal steps.)
As this reflection map is a bijection, we have that the number of "bad" paths is therefore the number of paths between opposite corners of an (n-1)x(n+1) grid consisting of up and right steps. This is just C(2n,n+1).
So the answer to the original problem is:
C(2n,n)-C(2n,n+1)=C(2n,n)/(n+1)
which is actually the n-th Catalan number.
(So there is probably also a nice recursive approach to this problem.)
Edit:
Aha yes, you could also split into cases depending on whether you hit the main diagonal in the middle of your journey or not, and you can get the Catalan recurrence from this. As 6 is small you could then compute the 6th Catalan number without too much difficulty, or you could use something like generating functions to derive their formula.
