Let's try this again

So it's been almost a year since I last posted here. I keep wanting to write things and then not doing it, because I don't have a vehicle for it... except I do. Silly me.

So I'll give this another shot; maybe I can actually post with some regularity this time. Right now I am slightly tired and should get to bed soon, so perhaps an interesting post will come tomorrow.

For now, I will tie up a little bit of a loose end from before by giving an indication of the solution to the problem I mentioned in my previous post. The following describes how to compute the function f(x) from just the k-subset x of [n] (no reference to other values of f). First, view x as a binary string of length n, with 1's in positions corresponding to elements of x and 0's elsewhere. Then, count along this string, beginning at the end (at the imaginary position n+1) with a cumulative count of 0, subtracting 1 every time you reach a 0 and adding 1 every time you reach a 1. So, for instance, the subset {1, 3, 4, 7} of [7] yields the binary string 1011001. Starting at the right end of this with 0, we get in the 7th position a running total of 1, then 0, then -1, then 0, then 1, then 0, then 1. This gives us the new string (1)(0)(1)(0)(-1)(0)(1) (from left to right). Now, to obtain f(x), find the leftmost position in this last string generated where the value is both minimal and at most 0. (If all the values are greater than 0 f(x) is not defined.) Notice that x does not contain the number corresponding to that position (this is easy to see by minimality) -- in the case above, we find that the leftmost minimal value occurs in position 5, and 5 is not in x. Add to x that number (in this case insert 5 into x) to obtain f(x).

It is not terribly difficult to show by induction that this actually gives us the correct function f(x). In particular, this means that f is defined on all k-subsets of [n] whenever k (which is, by just considering the sizes of the source and target sets, everywhere this could possibly be the case). I'll leave the details of the proof as an exercise. Bonus: rephrase this solution in terms of balanced pairs of parentheses.

Okay, bedtime now.