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.

A Combinatorics Problem

A bit over four years ago I was given what remains one of my favorite combinatorics problems. It goes like this:

Define A_n,k to be the set consisting of all k-element subsets of the set [n] (the integers 1 to n). For instance, we have A_4,2 = {{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}}. (Thus, |A_n,k| is equal to the binomial coefficient.) For each n > k ≥ 0, we define a (possibly partial) function f : A_n,k → A_n,k+1 by the following "greedy inclusion algorithm".

First, order the sets in both A_n,k and A_n,k+1 in lexicographic order (in increasing order of smallest element, then, in increasing order of second-smallest element, etc., so that they are in an order as in the example of A_4,2 above). Initially mark each element of A_n,k+1 as unused. For each set x ∈ A_n,k, in lexicographic order, do the following. Find out if there is some y ∈ A_n,k+1 such that x ⊆ y and y is marked as unused. If there is not, f(x) is undefined. If there is, take the earliest such y (in lexicographic order), define f(x) = y, and then mark that y as used. In either case, continue on to the next element of A_n,k.

This algorithm gives a partial function f which is defined on some (possibly all) elements of A_n,k. The question is this:
(a) Find the pairs (n, k) where f is defined on all of A_n,k.
(b) Find a simple, fast (linear time in n is good; if you are pedantic about integer comparisons not actually taking constant time this might be instead O(n log n)) method for taking an element x of A_n,k and determining whether f(x) is defined and, if so, its value.

As it's been four years since I solved the problem, I don't remember the details of the solution. Thus, I'll put the solution in a later post when I figure them out again.