Show that there is a set P of (2n)!/(n! (n+1)!) sequences of 2n terms, half 1s and half 0s, such that any sequence of 2n terms, half 1s and half 0s, is either in P or can be derived from a member of P by moving one term. Moving a term means changing a1, a2, ... , a2n to a1, a2, ... , ai-1, ai+1, ... , ajaiaj+1 ... an for some i, j. For example, by moving the initial 0 we can change 0110 to 1010 or 1100, or by moving the first 1 we can change 0110 to 1010 or 0101.
Solution
Given a sequence x (of length 2n), let f(x) be the sum of the positions of the 1s mod n+1. For example, x = 0110 has 1s in positions 2 and 3, so f(x) = 2 + 3 = 5 = 2 mod 3. Take Pk to be all sequences with f(x) = k. Now suppose a sequence x has 0 in the first position. If we move it to just after the mth 1 to get the sequence y, then we shift each of those 1s one place to the left, so f(y) = f(x) - m mod n+1. So by taking a suitable m (between 1 and n) - or by making no move at all - we can get y into Pk. Similarly, if x has 1 in the first position and we move it to just after the mth 0 to get a sequence y, then if we moved it past h 1s, each of those 1s has its position reduced by 1, but the 1 we are moving has its position increased by m+h, so f(y) = f(x) + m. So we can again get y into Pk. So every sequence either belongs to Pk or can be derived from a member of Pk by a move. But the n+1 sets Pk form a partition the (2n)!/(n! n!) possible sequences, so at least one of them has at most (2n)!/(n! (n+1)!) members. [If it has less then we can add any sequences to bring it up to (2n)!/(n! (n+1)!) members].
© John Scholes
jscholes@kalva.demon.co.uk
14 Oct 2002