Safe Haskell	None
Language	Haskell98

Math.Combinatorics.CombinatorialHopfAlgebra

Description

A module defining the following Combinatorial Hopf Algebras, together with coalgebra or Hopf algebra morphisms between them:

Sh, the Shuffle Hopf algebra
SSym, the Malvenuto-Reutnenauer Hopf algebra of permutations
YSym, the (dual of the) Loday-Ronco Hopf algebra of binary trees
QSym, the Hopf algebra of quasi-symmetric functions (having a basis indexed by compositions)
Sym, the Hopf algebra of symmetric functions (having a basis indexed by integer partitions)
NSym, the Hopf algebra of non-commutative symmetric functions

Synopsis

Documentation

newtype Shuffle a Source

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.

Constructors

Sh [a]

Instances

(Eq k, Num k, Ord a) => HopfAlgebra k (Shuffle a)
(Eq k, Num k, Ord a) => Bialgebra k (Shuffle a)
(Eq k, Num k, Ord a) => Coalgebra k (Shuffle a)
(Eq k, Num k, Ord a) => Algebra k (Shuffle a)
Eq a => Eq (Shuffle a)
Ord a => Ord (Shuffle a)
Show a => Show (Shuffle a)

sh :: [a] -> Vect Q (Shuffle a) Source

Construct a basis element of the shuffle algebra

shuffles :: [a] -> [a] -> [[a]] Source

deconcatenations :: [a] -> [([a], [a])] Source

newtype SSymF Source

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

Constructors

SSymF [Int]

Instances

Eq SSymF
Ord SSymF
Show SSymF
HasInverses SSymF
(Eq k, Num k) => HopfAlgebra k SSymF
(Eq k, Num k) => Bialgebra k SSymF
(Eq k, Num k) => Coalgebra k SSymF
(Eq k, Num k) => Algebra k SSymF
(Eq k, Num k) => HasPairing k SSymF SSymF	A pairing showing that SSym is self-adjoint
(Eq k, Num k) => HasPairing k SSymF (Dual SSymF)
(Eq k, Num k) => HopfAlgebra k (Dual SSymF)
(Eq k, Num k) => Bialgebra k (Dual SSymF)
(Eq k, Num k) => Coalgebra k (Dual SSymF)
(Eq k, Num k) => Algebra k (Dual SSymF)

ssymF :: [Int] -> Vect Q SSymF Source

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].

shiftedConcat :: SSymF -> SSymF -> SSymF Source

prop_Associative :: Eq t => (t -> t -> t) -> (t, t, t) -> Bool Source

flatten :: (Ord a, Num t, Enum t) => [a] -> [t] Source

newtype SSymM Source

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.

Constructors

SSymM [Int]

Instances

Eq SSymM
Ord SSymM
Show SSymM
(Eq k, Num k) => HopfAlgebra k SSymM
(Eq k, Num k) => Bialgebra k SSymM
(Eq k, Num k) => Coalgebra k SSymM
(Eq k, Num k) => Algebra k SSymM

ssymM :: [Int] -> Vect Q SSymM Source

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].

inversions :: (Ord a, Num t, Enum t) => [a] -> [(t, t)] Source

weakOrder :: (Ord a1, Ord a) => [a] -> [a1] -> Bool Source

mu :: (Num s, Eq a) => ([a], a -> a -> Bool) -> a -> a -> s Source

ssymMtoF :: (Eq k, Num k) => Vect k SSymM -> Vect k SSymF Source

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

ssymFtoM :: (Eq k, Num k) => Vect k SSymF -> Vect k SSymM Source

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

ssymFtoDual :: (Eq k, Num k) => Vect k SSymF -> Vect k (Dual SSymF) Source

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

data PBT a Source

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.

Constructors

T (PBT a) a (PBT a)
E

Instances

Functor PBT
Eq a => Eq (PBT a)
Ord a => Ord (PBT a)
Show a => Show (PBT a)

newtype YSymF a Source

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

Constructors

YSymF (PBT a)

Instances

Functor YSymF
(Eq k, Num k, Ord a) => HopfAlgebra k (YSymF a)
(Eq k, Num k, Ord a) => Bialgebra k (YSymF a)
(Eq k, Num k, Ord a) => Coalgebra k (YSymF a)
(Eq k, Num k, Ord a) => Algebra k (YSymF a)
Eq a => Eq (YSymF a)
Ord a => Ord (YSymF a)
Show a => Show (YSymF a)

ysymF :: PBT a -> Vect Q (YSymF a) Source

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

nodecount :: Num a => PBT t -> a Source

leafcount :: Num a => PBT t -> a Source

prefix :: PBT t -> [t] Source

shapeSignature :: Num t => PBT t1 -> [t] Source

nodeCountTree :: Num a => PBT t -> PBT a Source

leafCountTree :: Num a => PBT t -> PBT a Source

lrCountTree :: Num a => PBT t -> PBT (a, a) Source

shape :: PBT a -> PBT () Source

numbered :: Num a => PBT t -> PBT a Source

splits :: PBT a -> [(PBT a, PBT a)] Source

multisplits :: (Num a, Eq a) => a -> PBT a1 -> [[PBT a1]] Source

graft :: [PBT a] -> PBT a -> PBT a Source

newtype YSymM Source

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

Constructors

YSymM (PBT ())

Instances

Eq YSymM
Ord YSymM
Show YSymM
(Eq k, Num k) => HopfAlgebra k YSymM
(Eq k, Num k) => Bialgebra k YSymM
(Eq k, Num k) => Coalgebra k YSymM
(Eq k, Num k) => Algebra k YSymM

ysymM :: PBT () -> Vect Q YSymM Source

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

trees :: Int -> [PBT ()] Source

List all trees with the given number of nodes

tamariCovers :: PBT a -> [PBT a] Source

The covering relation for the Tamari partial order on binary trees

tamariUpSet :: Ord a => PBT a -> [PBT a] Source

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

tamariOrder :: PBT a -> PBT a -> Bool Source

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).

ysymMtoF :: (Eq k, Num k) => Vect k YSymM -> Vect k (YSymF ()) Source

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

ysymFtoM :: (Eq k, Num k) => Vect k (YSymF ()) -> Vect k YSymM Source

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

compositions :: Int -> [[Int]] Source

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]]

quasiShuffles :: [Int] -> [Int] -> [[Int]] Source

newtype QSymM Source

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

Constructors

QSymM [Int]

Instances

Eq QSymM
Ord QSymM
Show QSymM
(Eq k, Num k) => HopfAlgebra k QSymM
(Eq k, Num k) => Bialgebra k QSymM
(Eq k, Num k) => Coalgebra k QSymM
(Eq k, Num k) => Algebra k QSymM
(Eq k, Num k) => HasPairing k NSym QSymM	A duality pairing between NSym and QSymM (monomial basis), showing that NSym and QSym are dual.

qsymM :: [Int] -> Vect Q QSymM Source

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

coarsenings :: Num a => [a] -> [[a]] Source

refinements :: [Int] -> [[Int]] Source

newtype QSymF Source

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

Constructors

QSymF [Int]

Instances

Eq QSymF
Ord QSymF
Show QSymF
(Eq k, Num k) => HopfAlgebra k QSymF
(Eq k, Num k) => Bialgebra k QSymF
(Eq k, Num k) => Coalgebra k QSymF
(Eq k, Num k) => Algebra k QSymF

qsymF :: [Int] -> Vect Q QSymF Source

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

qsymMtoF :: (Eq k, Num k) => Vect k QSymM -> Vect k QSymF Source

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

qsymFtoM :: (Eq k, Num k) => Vect k QSymF -> Vect k QSymM Source

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

qsymPoly :: Int -> [Int] -> GlexPoly Q String Source

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.

newtype SymM Source

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

Constructors

SymM [Int]

Instances

Eq SymM
Ord SymM
Show SymM
(Eq k, Num k) => HopfAlgebra k SymM
(Eq k, Num k) => Bialgebra k SymM
(Eq k, Num k) => Coalgebra k SymM
(Eq k, Num k) => Algebra k SymM
(Eq k, Num k) => HasPairing k SymH SymM	A duality pairing between the complete and monomial bases of Sym, showing that Sym is self-dual.

symM :: [Int] -> Vect Q SymM Source

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

compositionsFromPartition :: Eq a => [a] -> [[a]] Source

symMult :: [Int] -> [Int] -> [[Int]] Source

newtype SymE Source

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]

Constructors

SymE [Int]

Instances

Eq SymE
Ord SymE
Show SymE
(Eq k, Num k) => Bialgebra k SymE
(Eq k, Num k) => Coalgebra k SymE
(Eq k, Num k) => Algebra k SymE

symE :: [Int] -> Vect Q SymE Source

symEtoM :: (Eq k, Num k) => Vect k SymE -> Vect k SymM Source

Convert from the elementary to the monomial basis of Sym

newtype SymH Source

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]

Constructors

SymH [Int]

Instances

Eq SymH
Ord SymH
Show SymH
(Eq k, Num k) => Bialgebra k SymH
(Eq k, Num k) => Coalgebra k SymH
(Eq k, Num k) => Algebra k SymH
(Eq k, Num k) => HasPairing k SymH SymM	A duality pairing between the complete and monomial bases of Sym, showing that Sym is self-dual.

symH :: [Int] -> Vect Q SymH Source

symHtoM :: (Eq k, Num k) => Vect k SymH -> Vect k SymM Source

Convert from the complete to the monomial basis of Sym

newtype NSym Source

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

Constructors

NSym [Int]

Instances

Eq NSym
Ord NSym
Show NSym
(Eq k, Num k) => HopfAlgebra k NSym
(Eq k, Num k) => Bialgebra k NSym
(Eq k, Num k) => Coalgebra k NSym
(Eq k, Num k) => Algebra k NSym
(Eq k, Num k) => HasPairing k NSym QSymM	A duality pairing between NSym and QSymM (monomial basis), showing that NSym and QSym are dual.

nsym :: [Int] -> Vect Q NSym Source

descendingTree :: Ord t => [t] -> PBT t Source

descendingTreeMap :: (Eq k, Num k) => Vect k SSymF -> Vect k (YSymF ()) Source

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.

minPerm :: Num t => PBT t1 -> [t] Source

maxPerm :: Num t => PBT t1 -> [t] Source

leftLeafComposition :: PBT t -> [Int] Source

leftLeafComposition' :: YSymF t -> QSymF Source

leftLeafCompositionMap :: (Eq k, Num k) => Vect k (YSymF a) -> Vect k QSymF Source

A Hopf algebra morphism from YSymF to QSymF

descents :: Ord b => [b] -> [Int] Source

descentComposition :: (Ord a, Num t) => [a] -> [t] Source

descentMap :: (Eq k, Num k) => Vect k SSymF -> Vect k QSymF Source

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.

underComposition :: QSymF -> SSymF Source

under :: PBT a -> PBT a -> PBT a Source

isUnderIrreducible :: PBT t -> Bool Source

underDecomposition :: PBT a -> [PBT a] Source

ysymmToSh :: Functor f => f YSymM -> f (Shuffle (PBT ())) Source

symToQSymM :: (Eq k, Num k) => Vect k SymM -> Vect k QSymM Source

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

nsymToSymH :: (Eq k, Num k) => Vect k NSym -> Vect k SymH Source

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

nsymToSSym :: (Num k, Eq k) => Vect k NSym -> Vect k SSymF Source