Teeter-totter transpositions

In attempting to write problems for the USAMO, I came across an interesting variant of Knuth equivalence whose structure is rather intricate.

Suppose we start with the numbers $1,2,3,\ldots,n$ written in a row. At each step, we may choose three adjacent numbers in the sequence, say $a,b,c$, and if either $a\lt b \lt c$ or $c\lt b\lt a$ then we can switch $a$ and $c$. So for instance, we might start with 12345 and change it to 32145. At this point we cannot use the subsequence 2,1,4 to change the 2 and 4, but we can use 1,4,5 and end up with 32541. The question is, how many possible sequences can we end up with after a sequence of such moves? (I call them `teeter-totter moves’, since you can either change three consecutive elements from increasing to decreasing or vice versa.)

Tropical polynomials and your federal tax return

It’s Tax Day here in the United States, and I spent a larger portion of the past weekend than I would have liked filling out the appropriate forms. But even among tax forms and legal documents you can find a mathematical gemstone or two!

The instructions for filling out, say, IRS form 1040, are rather peculiar in that they try give the reader very simple mathematical operations to carry out, one at a time, to end up with a complicated function of many variables. As far as I could tell, the valid operations are:

• Entering a value for a variable (e.g. income, standard deduction, etc.)
• $+$: Addition of two entries
• $\times$: Multiplication
• $\min$: Taking the minimum of two entries
• $\overset{\cdot}{-}$: A modified version of subtraction, where $a \overset{\cdot}{-} b$ is defined to be $a-b$ if $a\ge b$ and $0$ otherwise.

I found it interesting that every complicated tax computing formula can be broken down into steps of this form. In fact, it says something about the tax formulae: they can all be written as a composition of addition, multiplication, scalar multiplication, min, and $\overset{\cdot}{-}$.

The q-factorial in terms of the major index

EDIT: As pointed out in the comments, the following proof is found in Knuth’s book, The Art of Computer Programming, Vol. 3, and is attributed to MacMahon.

There are several nice series expansions involving basic permutation statistics which I’ve been reviewing lately. One of these involves the number of inversions of a permutation.

An inversion of a permutation of the numbers $1,2,\ldots,n$ is a pair of numbers which appear ``out of order’’ in the sequence, that is, with the larger number appearing first. For instance, for $\DeclareMathOperator{\maj}{maj} \DeclareMathOperator{\inv}{inv} n=4$, the permutation $3,1,4,2$ has three inversions: $(3,1)$, $(3,2)$, and $(4,2)$. We write \[\inv(3142)=3.\]

Growth patterns of desert bushes?

I spent most of Spring Break hiking in Death Valley National Park with Bryan Gillespie. It was stunningly beautiful and rather otherworldly in some ways, especially in the way that so much hardy desert life keeps on surviving on 1.5 inches of rainfall per year.

One such hardy desert plant that we encountered a number of times, especially near the Ubehebe Crater, was the creosote bush. It looked like this:

Bryan’s first reaction was, “Wow, look at the way it grows! I’d love to know what its fractal structure is.” He walked around the plant and took several more photos:

It appeared that whatever angle you viewed the bush from, there was (approximately) a single layer of leaves visible with no leaf covering another and no big gaps between the leaves. This, we realized, is an optimal use of its resources: no matter the angle of the sun, it is using every leaf to absorb its energies while not wasting water keeping other buried leaves alive.

A q-analog of the decomposition of the regular representation of the symmetric group

It is a well-known fact of representation theory that, if the irreducible representations of a finite group $\DeclareMathOperator{\maj}{maj} \DeclareMathOperator{\sh}{sh} G$ are $V_1,\ldots,V_m$, and $R$ is the regular representation formed by $G$ acting on itself by left multiplication, then \[R=\bigoplus_{i=1}^{m} (\dim V_i) \cdot V_i\] is its decomposition into irreducibles.

I’ve recently discovered a $q$-analog of this fact for $G=S_n$ that is a simple consequence of some known results in symmetric function theory.

In Enumerative Combinatorics, Stanley defines a generalization of the major index on permutations to standard tableaux. For a permutation \[w=w_1,\ldots,w_n\] of $1,\ldots,n$, a descent is a position $i$ such that $w_i>w_{i+1}$. For instance, $52413$ has two descents, in positions $1$ and $3$. The major index of $w$, denoted $\maj(w)$, is the sum of the positions of the descents, in this case \[\maj(52413)=1+3=4.\]