This is my techlab page for my third quarter project at TJHSST.

Title: A Recurring Reoccurance in Counting Permutations

Student: Yan Zhang

2002-2003

Background:
If we define a_n to be the number of square permutations of size n, then a_n follows a curious recurrence: a_(2n) (2n+1) = a_(2n+1). The original paper analyzing this sequence was written by Blum in an article in 1974. A proof exists, though needing some non-trivial generating functions techniques, and offers nothing to a combinatorial understanding of the pattern. Richard Stanley revisited this problem in his text "Enumerative Combinatorics" (1999). The paper gives the basic definitions and mathematical notation necessary, though some elementary knowledge in combinatorics would be helpful. Otherwise, it is easy to understand.

Description:
(Includes Exam component 3)
This research was started at the Clay Mathematics Institute. Our "team" was consisted of Philip Sung (CA) and me, under the guidance of other Academy participants, conducted by Dr. Richard Stanley of MIT.
We were looking at the integer sequence a_n which enumerates the number of square permutations of fixed length n (mathematical background, including the definition of square permutations, can be found in the paper below). In 1974, when this sequence was analyzed, a difficult proof with advanced combinatorics was given to prove that the sequence satisfied the recurrence a_(2n) (2n+1) = a_(2n+1). Our task was to prove this with elementary combinatorics, which gives a clearer picture of what is actually happening in the strucutre of the problem.
After some work at the Institute, we managed to give a combinatorial proof. However, what is interesting is not just that such a proof have been found, but rather that we've discovered a certain independence inside this problem, i.e. we can generalize the problem to a whole class of similar sequences, in each one the recurrence will occur again.
To handle this, we created our own mathematical definition, the concept of "Odd-cycle invariance". We have also proved that the general class of sequences which satisfy this invariance also satisfies the given recurrence.
We are working hard to generalize this result, namely to classify such sequences in more complicated context.

Visuals, files, tables:
Following things may or may not be included here in the future: data tables, the mathematica notebooks, and transparencies for the presentation.

The Notebook (Mathematica format) This is the (not commented) mathematica notebook from which values were achieved for the desired (and other) sequences.
The Paper:
(Includes exam components 1 - 2)
The Paper (Incomplete) (PDF) This paper is not yet complete, but contains the main elements of the proof. Some parts are handwavy, and we haven't included data tables yet.
The Paper (Incomplete) (HTML Above created with latex2html. Really messy.

The Scientific Method:
The Scientific Method As required, here's a look at the project via the scientific method.

The Future:
(Includes exam components 4 and 5)
By the end of the fourth quarter, with already a good head start, I shoudl be able to finish the final version of the paper including the main proof and new mahematical strucutres introduced in the proof. All I have remaining to do is to clean up the language, make sure that the proofs work, find more similar sources to extract information from, and inserting tables. Then we will have a finalized, professional-looking paper suitable for submission to a mathematical jounral.
However, I am also actively trying to go in new directions. Many of these directions were outlined in the Scientific Method link about:
*Are there other types of invariance in permutations which follow a similar pattern? If so, how do we prove that they work also?
*How can we generalize this counting technique to other sequences, and not just counting permutations?
*In our proof, we have found that the analogue of our simple counting technique can be reinforced by ann application of generating functions. From this, can we find a deeper connection between the algebra of generating functions and the combinatorial theory of bijective proofs.
Any breakthrough in these directions would call for additional work on the paper.

As for college plans, seeing that my mentors are from MIT, and that I will probably go to college in Boston, further research is certainly possible. The mathematics involved also isn't very intricate, so I can take a good advanced course of combinatorics no matter where I go to foster the project's improvement. A bright future indeed.
Yan Zhang
Last modified: Wed Apr 2 14:00:23 EST 2003