An example of a QS function is given by

which is clearly not symmetric. In general, is quasi-symmetric if for all and :

.

Let be the space of QS functions of degree with infinitely many variables as usual. And . Then strictly contains the symmetric function algebra . One basis of is given by the analogue of monomial polynomials, indexed instead by the set of compositions of :

So , the latter is the number of compositions, because clearly forms a basis. Now given a composition , i.e., , we associate a subset . If we just get the empty set. With this construction, another basis is given by

where strict inequality is required for if . As a set of exercises, check that

Please note that French mathematicians call ‘s ‘s, called the fundamental/ Gessel’s basis. We also define to be the inverse operation of , i.e., given , we first order the elements into an increasing array, then take successive difference, with the last difference taken from . So for example, given , .

Proposition 13for ,

A bit about shuffling: the GSR shuffling is described by first cut c cards from a deck of n with chance . Drop the next from left with probability with being the size of the left deck etc. One can easily check this has the uniform measure on as stationary distribution. Inverse shuffling: choose each card with probability 1/2 independently then take those out and put on top. Exercise: this indeed gives the transpose of the Markov matrix for GSR. The idea is to check that once we cut c cards, the arrangements of c cards interwoven with cards are equally likely. This is obvious in light of the fact that the dropping process can be seen as drawing cards of black and white kinds from a box in which they are mixed up.

More generally, if one is given , and . The one could label cards independently with with probability . Next

- Remove all cards labeled 1 and put in a separate pile.
- Remove all cards labeled 2 and put on top of the 1’s, etc.

This defines the Inverse X shuffle. In the forward direction, we pick with , independently. Standardize in the following sense

i.e., put 1,2,3 in the positions of the three 1’s in left to right order, etc. The end result is a permutation, which is the result of one round of forward X shuffle, i.e., it gives the distribution of . This is clearly the inverse of the procedure described before.

This forward shuffle can be usefully alternatively described as follows: pick as before. Remove the first cards of the lowest symbol and place it into pile , next cards of the second lowest symbol and put in pile , etc, then start dropping cards from these piles one by one according to the same rule as GSR. For fixed , the number of possible shuffle outcomes (of one round) is , because that’s how many ways of intermixing these symboled cards. Also this set of permutations forms the shortest (under inversion distance) length coset representations of (it’s clear that two different shuffle outcomes lie in different cosets because their difference do not fixed the positions of the cards within each symbol class). To show X shuffling theory is the same as quasisymmetric function theory, Stanley proved the following

Theorem 14Fix , with , then

where is the CO of the descent set of .

*Proof:* Choose independently with distribution given by the ‘s. Set . If we write

then appears right below (check this for yourself).

Now using the standardizing interpretation of forward X shuffle, standardizes to if and only if

- and
- . for .

This takes some combinatorial thinking, first we have the following characterization of descent set of :

Basically a descent at indicates that will be mapped to but it appears before which gets mapped to. Thus if and have the same symbol, would get mapped to a number smaller than under standardization. So they must have different symbols. The first condition is clear because if get mapped to under standardization, they must be weakly increasing. This gives one direction of the above claim. The converse follows because all the ‘s of a particular symbol occur before the descent for which ; so procedurally it’s clear how the standardization of ‘s would look like.

The standardizations of some sequence exhaust the possible outcomes of one X shuffle. For a particular sequence , its probability of being chosen is given by . Thus by the previous argument giving all sequences that standardize to ,

But this is just the definition of .

If we specialize to , then we get the usual GSR shuffle. More generally, if , we have

If we let , we have

This is seen intuitively as follows: as , the chance that two are equal goes to , then when doing the forward shuffling by dropping cards, we are essentially choosing a uniform ordering of .

Any formula involving can be seen as a -deformation of formula for the uniform measure.