Documentation

A basis for the shuffle algebra. As a vector space, the shuffle algebra is identical to the tensor algebra. However, we consider a different algebra structure, based on the shuffle product. Together with the deconcatenation coproduct, this leads to a Hopf algebra structure.

Construct a basis element of the shuffle algebra

The fundamental basis for the Malvenuto-Reutenauer Hopf algebra of permutations, SSym.

Construct a fundamental basis element in SSym. The list of ints must be a permutation of [1..n], eg [1,2], [3,4,2,1].

An alternative "monomial" basis for the Malvenuto-Reutenauer Hopf algebra of permutations, SSym. This basis is related to the fundamental basis by Mobius inversion in the poset of permutations with the weak order.

Construct a monomial basis element in SSym. The list of ints must be a permutation of [1..n], eg [1,2], [3,4,2,1].

Convert an element of SSym represented in the monomial basis to the fundamental basis

Convert an element of SSym represented in the fundamental basis to the monomial basis

The isomorphism from SSym to its dual that takes a permutation in the fundamental basis to its inverse in the dual basis

A type for (rooted) planar binary trees. The basis elements of the Loday-Ronco Hopf algebra are indexed by these.

Although the trees are labelled, we're really only interested in the shapes of the trees, and hence in the type PBT (). The Algebra, Coalgebra and HopfAlgebra instances all ignore the labels. However, it is convenient to allow labels, as they can be useful for seeing what is going on, and they also make it possible to define various ways to create trees from lists of labels.

The fundamental basis for (the dual of) the Loday-Ronco Hopf algebra of binary trees, YSym.

Construct the element of YSym in the fundamental basis indexed by the given tree

An alternative "monomial" basis for (the dual of) the Loday-Ronco Hopf algebra of binary trees, YSym.

Construct the element of YSym in the monomial basis indexed by the given tree

List all trees with the given number of nodes

The covering relation for the Tamari partial order on binary trees

The up-set of a binary tree in the Tamari partial order

The Tamari partial order on binary trees. This is only defined between trees of the same size (number of nodes). The result between trees of different sizes is undefined (we don't check).

Convert an element of YSym represented in the monomial basis to the fundamental basis

Convert an element of YSym represented in the fundamental basis to the monomial basis

List the compositions of an integer n. For example, the compositions of 4 are [[1,1,1,1],[1,1,2],[1,2,1],[1,3],[2,1,1],[2,2],[3,1],[4]]

A type for the monomial basis for the quasi-symmetric functions, indexed by compositions.

Construct the element of QSym in the monomial basis indexed by the given composition

A type for the fundamental basis for the quasi-symmetric functions, indexed by compositions.

Construct the element of QSym in the fundamental basis indexed by the given composition

Convert an element of QSym represented in the monomial basis to the fundamental basis

Convert an element of QSym represented in the fundamental basis to the monomial basis

qsymPoly n is is the quasi-symmetric polynomial in n variables for the indices is. (This corresponds to the monomial basis for QSym.) For example, qsymPoly 3 [2,1] == x1^2*x2+x1^2*x3+x2^2*x3.

A type for the monomial basis for Sym, the Hopf algebra of symmetric functions, indexed by integer partitions

Construct the element of Sym in the monomial basis indexed by the given integer partition

The elementary basis for Sym, the Hopf algebra of symmetric functions. Defined informally as > symE [n] = symM (replicate n 1) > symE lambda = product [symE [p] | p <- lambda]

Convert from the elementary to the monomial basis of Sym

The complete basis for Sym, the Hopf algebra of symmetric functions. Defined informally as > symH [n] = sum [symM lambda | lambda <- integerPartitions n] -- == all monomials of weight n > symH lambda = product [symH [p] | p <- lambda]

Convert from the complete to the monomial basis of Sym

A basis for NSym, the Hopf algebra of non-commutative symmetric functions, indexed by compositions

Given a permutation p of [1..n], we can construct a tree (the descending tree of p) as follows:

• Split the permutation as p = ls ++ [n] ++ rs
• Place n at the root of the tree, and recursively place the descending trees of ls and rs as the left and right children of the root
• To bottom out the recursion, the descending tree of the empty permutation is of course the empty tree

This map between bases SSymF -> YSymF turns out to induce a morphism of Hopf algebras.

A Hopf algebra morphism from YSymF to QSymF

Given a permutation of [1..n], its descents are those positions where the next number is less than the previous number. For example, the permutation [2,3,5,1,6,4] has descents from 5 to 1 and from 6 to 4. The descents can be regarded as cutting the permutation sequence into segments - 235-16-4 - and by counting the lengths of the segments, we get a composition 3+2+1. This map between bases SSymF -> QSymF turns out to induce a morphism of Hopf algebras.

The injection of Sym into QSym (defined over the monomial basis)

A surjection of NSym onto Sym (defined over the complete basis)