HaskellForMaths-0.4.9: Combinatorics, group theory, commutative algebra, non-commutative algebra

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

- class Graded b where
  - grade :: b -> Int
- class (Eq k, Num k, Ord b, Graded b, HopfAlgebra k b) => CombinatorialHopfAlgebra k b where
  - zeta :: Vect k b -> Vect k ()
- gradedConnectedAntipode :: (Eq k, Num k, Ord b, Bialgebra k b, Graded b) => Vect k b -> Vect k b
- newtype Shuffle a = Sh [a]
- sh :: [a] -> Vect Q (Shuffle a)
- shuffles :: [a] -> [a] -> [[a]]
- deconcatenations :: [a] -> [([a], [a])]
- newtype SSymF = SSymF [Int]
- ssymF :: [Int] -> Vect Q SSymF
- shiftedConcat :: SSymF -> SSymF -> SSymF
- prop_Associative :: Eq a => (a -> a -> a) -> (a, a, a) -> Bool
- flatten :: (Num a1, Enum a1, Ord a2) => [a2] -> [a1]
- newtype SSymM = SSymM [Int]
- ssymM :: [Int] -> Vect Q SSymM
- inversions :: (Num b, Enum b, Ord a) => [a] -> [(b, b)]
- weakOrder :: (Ord a1, Ord a2) => [a1] -> [a2] -> Bool
- mu :: (Num p, Eq t) => ([t], t -> t -> Bool) -> t -> t -> p
- ssymMtoF :: (Eq k, Num k) => Vect k SSymM -> Vect k SSymF
- ssymFtoM :: (Eq k, Num k) => Vect k SSymF -> Vect k SSymM
- ssymFtoDual :: (Eq k, Num k) => Vect k SSymF -> Vect k (Dual SSymF)
- data PBT a
  - = T (PBT a) a (PBT a)
  - | E
- newtype YSymF a = YSymF (PBT a)
- ysymF :: PBT a -> Vect Q (YSymF a)
- nodecount :: Num p => PBT a -> p
- leafcount :: Num p => PBT a -> p
- prefix :: PBT a -> [a]
- shapeSignature :: Num a1 => PBT a2 -> [a1]
- nodeCountTree :: Num a1 => PBT a2 -> PBT a1
- leafCountTree :: Num a1 => PBT a2 -> PBT a1
- lrCountTree :: Num b => PBT a -> PBT (b, b)
- shape :: PBT a -> PBT ()
- numbered :: Num a1 => PBT a2 -> PBT a1
- splits :: PBT a -> [(PBT a, PBT a)]
- multisplits :: (Eq t, Num t) => t -> PBT a -> [[PBT a]]
- graft :: [PBT a] -> PBT a -> PBT a
- newtype YSymM = YSymM (PBT ())
- ysymM :: PBT () -> Vect Q YSymM
- trees :: Int -> [PBT ()]
- tamariCovers :: PBT a -> [PBT a]
- tamariUpSet :: Ord a => PBT a -> [PBT a]
- tamariOrder :: PBT a -> PBT a -> Bool
- ysymMtoF :: (Eq k, Num k) => Vect k YSymM -> Vect k (YSymF ())
- ysymFtoM :: (Eq k, Num k) => Vect k (YSymF ()) -> Vect k YSymM
- compositions :: Int -> [[Int]]
- quasiShuffles :: [Int] -> [Int] -> [[Int]]
- newtype QSymM = QSymM [Int]
- qsymM :: [Int] -> Vect Q QSymM
- coarsenings :: Num a => [a] -> [[a]]
- refinements :: [Int] -> [[Int]]
- newtype QSymF = QSymF [Int]
- qsymF :: [Int] -> Vect Q QSymF
- qsymMtoF :: (Eq k, Num k) => Vect k QSymM -> Vect k QSymF
- qsymFtoM :: (Eq k, Num k) => Vect k QSymF -> Vect k QSymM
- qsymPoly :: Int -> [Int] -> GlexPoly Q String
- newtype SymM = SymM [Int]
- symM :: [Int] -> Vect Q SymM
- compositionsFromPartition :: Eq a => [a] -> [[a]]
- symMult :: [Int] -> [Int] -> [[Int]]
- newtype SymE = SymE [Int]
- symE :: [Int] -> Vect Q SymE
- symEtoM :: (Eq k, Num k) => Vect k SymE -> Vect k SymM
- newtype SymH = SymH [Int]
- symH :: [Int] -> Vect Q SymH
- symHtoM :: (Eq k, Num k) => Vect k SymH -> Vect k SymM
- newtype NSym = NSym [Int]
- nsym :: [Int] -> Vect Q NSym
- descendingTree :: Ord a => [a] -> PBT a
- descendingTreeMap :: (Eq k, Num k) => Vect k SSymF -> Vect k (YSymF ())
- minPerm :: Num a1 => PBT a2 -> [a1]
- maxPerm :: Num a1 => PBT a2 -> [a1]
- leftLeafComposition :: PBT a -> [Int]
- leftLeafComposition' :: YSymF a -> QSymF
- leftLeafCompositionMap :: (Eq k, Num k) => Vect k (YSymF a) -> Vect k QSymF
- descents :: Ord a => [a] -> [Int]
- descentComposition :: (Ord a1, Num a2) => [a1] -> [a2]
- descentMap :: (Eq k, Num k) => Vect k SSymF -> Vect k QSymF
- underComposition :: QSymF -> SSymF
- under :: PBT a -> PBT a -> PBT a
- isUnderIrreducible :: PBT a -> Bool
- underDecomposition :: PBT a -> [PBT a]
- ysymmToSh :: Functor f => f YSymM -> f (Shuffle (PBT ()))
- symToQSymM :: (Eq k, Num k) => Vect k SymM -> Vect k QSymM
- nsymToSymH :: (Eq k, Num k) => Vect k NSym -> Vect k SymH
- nsymToSSym :: (Eq k, Num k) => Vect k NSym -> Vect k SSymF

# Documentation

class Graded b where Source #

Methods

grade :: b -> Int Source #

#### Instances

Instances details

Graded NSym Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: NSym -> Int Source #
Graded SymE Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: SymE -> Int Source #
Graded SymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: SymM -> Int Source #
Graded QSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: QSymF -> Int Source #
Graded QSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: QSymM -> Int Source #
Graded YSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: YSymM -> Int Source #
Graded SSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: SSymM -> Int Source #
Graded SSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: SSymF -> Int Source #
Graded b => Graded (Dual b) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: Dual b -> Int Source #
Graded (YSymF a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: YSymF a -> Int Source #
Graded (Shuffle a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: Shuffle a -> Int Source #

class (Eq k, Num k, Ord b, Graded b, HopfAlgebra k b) => CombinatorialHopfAlgebra k b where Source #

Methods

zeta :: Vect k b -> Vect k () Source #

gradedConnectedAntipode :: (Eq k, Num k, Ord b, Bialgebra k b, Graded b) => Vect k b -> Vect k b Source #

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

Instances details

(Eq k, Num k, Ord a) => HopfAlgebra k (Shuffle a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods antipode :: Vect k (Shuffle a) -> Vect k (Shuffle a) Source #
(Eq k, Num k, Ord a) => Bialgebra k (Shuffle a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra
(Eq k, Num k, Ord a) => Coalgebra k (Shuffle a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods counit :: Vect k (Shuffle a) -> k Source # comult :: Vect k (Shuffle a) -> Vect k (Tensor (Shuffle a) (Shuffle a)) Source #
(Eq k, Num k, Ord a) => Algebra k (Shuffle a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods unit :: k -> Vect k (Shuffle a) Source # mult :: Vect k (Tensor (Shuffle a) (Shuffle a)) -> Vect k (Shuffle a) Source #
Eq a => Eq (Shuffle a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods (==) :: Shuffle a -> Shuffle a -> Bool (/=) :: Shuffle a -> Shuffle a -> Bool
Ord a => Ord (Shuffle a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods compare :: Shuffle a -> Shuffle a -> Ordering (<) :: Shuffle a -> Shuffle a -> Bool (<=) :: Shuffle a -> Shuffle a -> Bool (>) :: Shuffle a -> Shuffle a -> Bool (>=) :: Shuffle a -> Shuffle a -> Bool max :: Shuffle a -> Shuffle a -> Shuffle a min :: Shuffle a -> Shuffle a -> Shuffle a
Show a => Show (Shuffle a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods showsPrec :: Int -> Shuffle a -> ShowS show :: Shuffle a -> String showList :: [Shuffle a] -> ShowS
Graded (Shuffle a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: Shuffle a -> Int Source #

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

Instances details

Eq SSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods (==) :: SSymF -> SSymF -> Bool (/=) :: SSymF -> SSymF -> Bool
Ord SSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods compare :: SSymF -> SSymF -> Ordering (<) :: SSymF -> SSymF -> Bool (<=) :: SSymF -> SSymF -> Bool (>) :: SSymF -> SSymF -> Bool (>=) :: SSymF -> SSymF -> Bool max :: SSymF -> SSymF -> SSymF min :: SSymF -> SSymF -> SSymF
Show SSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods showsPrec :: Int -> SSymF -> ShowS show :: SSymF -> String showList :: [SSymF] -> ShowS
HasInverses SSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods inverse :: SSymF -> SSymF Source #
Graded SSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: SSymF -> Int Source #
(Eq k, Num k) => HopfAlgebra k SSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods antipode :: Vect k SSymF -> Vect k SSymF Source #
(Eq k, Num k) => Bialgebra k SSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra
(Eq k, Num k) => Coalgebra k SSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods counit :: Vect k SSymF -> k Source # comult :: Vect k SSymF -> Vect k (Tensor SSymF SSymF) Source #
(Eq k, Num k) => Algebra k SSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods unit :: k -> Vect k SSymF Source # mult :: Vect k (Tensor SSymF SSymF) -> Vect k SSymF Source #
(Eq k, Num k) => HasPairing k SSymF SSymF Source # | A pairing showing that SSym is self-adjoint
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods pairing :: Vect k (Tensor SSymF SSymF) -> Vect k () Source #
(Eq k, Num k) => HasPairing k SSymF (Dual SSymF) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods pairing :: Vect k (Tensor SSymF (Dual SSymF)) -> Vect k () Source #
(Eq k, Num k) => HopfAlgebra k (Dual SSymF) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods antipode :: Vect k (Dual SSymF) -> Vect k (Dual SSymF) Source #
(Eq k, Num k) => Bialgebra k (Dual SSymF) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra
(Eq k, Num k) => Coalgebra k (Dual SSymF) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods counit :: Vect k (Dual SSymF) -> k Source # comult :: Vect k (Dual SSymF) -> Vect k (Tensor (Dual SSymF) (Dual SSymF)) Source #
(Eq k, Num k) => Algebra k (Dual SSymF) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods unit :: k -> Vect k (Dual SSymF) Source # mult :: Vect k (Tensor (Dual SSymF) (Dual SSymF)) -> Vect k (Dual SSymF) Source #

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 a => (a -> a -> a) -> (a, a, a) -> Bool Source #

flatten :: (Num a1, Enum a1, Ord a2) => [a2] -> [a1] 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

Instances details

Eq SSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods (==) :: SSymM -> SSymM -> Bool (/=) :: SSymM -> SSymM -> Bool
Ord SSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods compare :: SSymM -> SSymM -> Ordering (<) :: SSymM -> SSymM -> Bool (<=) :: SSymM -> SSymM -> Bool (>) :: SSymM -> SSymM -> Bool (>=) :: SSymM -> SSymM -> Bool max :: SSymM -> SSymM -> SSymM min :: SSymM -> SSymM -> SSymM
Show SSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods showsPrec :: Int -> SSymM -> ShowS show :: SSymM -> String showList :: [SSymM] -> ShowS
Graded SSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: SSymM -> Int Source #
(Eq k, Num k) => HopfAlgebra k SSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods antipode :: Vect k SSymM -> Vect k SSymM Source #
(Eq k, Num k) => Bialgebra k SSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra
(Eq k, Num k) => Coalgebra k SSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods counit :: Vect k SSymM -> k Source # comult :: Vect k SSymM -> Vect k (Tensor SSymM SSymM) Source #
(Eq k, Num k) => Algebra k SSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods unit :: k -> Vect k SSymM Source # mult :: Vect k (Tensor SSymM SSymM) -> Vect k SSymM Source #

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 :: (Num b, Enum b, Ord a) => [a] -> [(b, b)] Source #

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

mu :: (Num p, Eq t) => ([t], t -> t -> Bool) -> t -> t -> p 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

Instances details

Functor PBT Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods fmap :: (a -> b) -> PBT a -> PBT b (<$) :: a -> PBT b -> PBT a
Eq a => Eq (PBT a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods (==) :: PBT a -> PBT a -> Bool (/=) :: PBT a -> PBT a -> Bool
Ord a => Ord (PBT a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods compare :: PBT a -> PBT a -> Ordering (<) :: PBT a -> PBT a -> Bool (<=) :: PBT a -> PBT a -> Bool (>) :: PBT a -> PBT a -> Bool (>=) :: PBT a -> PBT a -> Bool max :: PBT a -> PBT a -> PBT a min :: PBT a -> PBT a -> PBT a
Show a => Show (PBT a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods showsPrec :: Int -> PBT a -> ShowS show :: PBT a -> String showList :: [PBT a] -> ShowS

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

Instances details

Functor YSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods fmap :: (a -> b) -> YSymF a -> YSymF b (<$) :: a -> YSymF b -> YSymF a
(Eq k, Num k, Ord a) => HopfAlgebra k (YSymF a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods antipode :: Vect k (YSymF a) -> Vect k (YSymF a) Source #
(Eq k, Num k, Ord a) => Bialgebra k (YSymF a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra
(Eq k, Num k, Ord a) => Coalgebra k (YSymF a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods counit :: Vect k (YSymF a) -> k Source # comult :: Vect k (YSymF a) -> Vect k (Tensor (YSymF a) (YSymF a)) Source #
(Eq k, Num k, Ord a) => Algebra k (YSymF a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods unit :: k -> Vect k (YSymF a) Source # mult :: Vect k (Tensor (YSymF a) (YSymF a)) -> Vect k (YSymF a) Source #
Eq a => Eq (YSymF a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods (==) :: YSymF a -> YSymF a -> Bool (/=) :: YSymF a -> YSymF a -> Bool
Ord a => Ord (YSymF a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods compare :: YSymF a -> YSymF a -> Ordering (<) :: YSymF a -> YSymF a -> Bool (<=) :: YSymF a -> YSymF a -> Bool (>) :: YSymF a -> YSymF a -> Bool (>=) :: YSymF a -> YSymF a -> Bool max :: YSymF a -> YSymF a -> YSymF a min :: YSymF a -> YSymF a -> YSymF a
Show a => Show (YSymF a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods showsPrec :: Int -> YSymF a -> ShowS show :: YSymF a -> String showList :: [YSymF a] -> ShowS
Graded (YSymF a) Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: YSymF a -> Int Source #

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

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

nodecount :: Num p => PBT a -> p Source #

leafcount :: Num p => PBT a -> p Source #

prefix :: PBT a -> [a] Source #

shapeSignature :: Num a1 => PBT a2 -> [a1] Source #

nodeCountTree :: Num a1 => PBT a2 -> PBT a1 Source #

leafCountTree :: Num a1 => PBT a2 -> PBT a1 Source #

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

shape :: PBT a -> PBT () Source #

numbered :: Num a1 => PBT a2 -> PBT a1 Source #

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

multisplits :: (Eq t, Num t) => t -> PBT a -> [[PBT a]] 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

Instances details

Eq YSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods (==) :: YSymM -> YSymM -> Bool (/=) :: YSymM -> YSymM -> Bool
Ord YSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods compare :: YSymM -> YSymM -> Ordering (<) :: YSymM -> YSymM -> Bool (<=) :: YSymM -> YSymM -> Bool (>) :: YSymM -> YSymM -> Bool (>=) :: YSymM -> YSymM -> Bool max :: YSymM -> YSymM -> YSymM min :: YSymM -> YSymM -> YSymM
Show YSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods showsPrec :: Int -> YSymM -> ShowS show :: YSymM -> String showList :: [YSymM] -> ShowS
Graded YSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: YSymM -> Int Source #
(Eq k, Num k) => HopfAlgebra k YSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods antipode :: Vect k YSymM -> Vect k YSymM Source #
(Eq k, Num k) => Bialgebra k YSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra
(Eq k, Num k) => Coalgebra k YSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods counit :: Vect k YSymM -> k Source # comult :: Vect k YSymM -> Vect k (Tensor YSymM YSymM) Source #
(Eq k, Num k) => Algebra k YSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods unit :: k -> Vect k YSymM Source # mult :: Vect k (Tensor YSymM YSymM) -> Vect k YSymM Source #

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

Instances details

Eq QSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods (==) :: QSymM -> QSymM -> Bool (/=) :: QSymM -> QSymM -> Bool
Ord QSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods compare :: QSymM -> QSymM -> Ordering (<) :: QSymM -> QSymM -> Bool (<=) :: QSymM -> QSymM -> Bool (>) :: QSymM -> QSymM -> Bool (>=) :: QSymM -> QSymM -> Bool max :: QSymM -> QSymM -> QSymM min :: QSymM -> QSymM -> QSymM
Show QSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods showsPrec :: Int -> QSymM -> ShowS show :: QSymM -> String showList :: [QSymM] -> ShowS
Graded QSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: QSymM -> Int Source #
(Eq k, Num k) => HopfAlgebra k QSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods antipode :: Vect k QSymM -> Vect k QSymM Source #
(Eq k, Num k) => Bialgebra k QSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra
(Eq k, Num k) => Coalgebra k QSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods counit :: Vect k QSymM -> k Source # comult :: Vect k QSymM -> Vect k (Tensor QSymM QSymM) Source #
(Eq k, Num k) => Algebra k QSymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods unit :: k -> Vect k QSymM Source # mult :: Vect k (Tensor QSymM QSymM) -> Vect k QSymM Source #
(Eq k, Num k) => HasPairing k NSym QSymM Source # | A duality pairing between NSym and QSymM (monomial basis), showing that NSym and QSym are dual.
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods pairing :: Vect k (Tensor NSym QSymM) -> Vect k () Source #

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

Instances details

Eq QSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods (==) :: QSymF -> QSymF -> Bool (/=) :: QSymF -> QSymF -> Bool
Ord QSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods compare :: QSymF -> QSymF -> Ordering (<) :: QSymF -> QSymF -> Bool (<=) :: QSymF -> QSymF -> Bool (>) :: QSymF -> QSymF -> Bool (>=) :: QSymF -> QSymF -> Bool max :: QSymF -> QSymF -> QSymF min :: QSymF -> QSymF -> QSymF
Show QSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods showsPrec :: Int -> QSymF -> ShowS show :: QSymF -> String showList :: [QSymF] -> ShowS
Graded QSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: QSymF -> Int Source #
(Eq k, Num k) => HopfAlgebra k QSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods antipode :: Vect k QSymF -> Vect k QSymF Source #
(Eq k, Num k) => Bialgebra k QSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra
(Eq k, Num k) => Coalgebra k QSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods counit :: Vect k QSymF -> k Source # comult :: Vect k QSymF -> Vect k (Tensor QSymF QSymF) Source #
(Eq k, Num k) => Algebra k QSymF Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods unit :: k -> Vect k QSymF Source # mult :: Vect k (Tensor QSymF QSymF) -> Vect k QSymF Source #

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

Instances details

Eq SymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods (==) :: SymM -> SymM -> Bool (/=) :: SymM -> SymM -> Bool
Ord SymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods compare :: SymM -> SymM -> Ordering (<) :: SymM -> SymM -> Bool (<=) :: SymM -> SymM -> Bool (>) :: SymM -> SymM -> Bool (>=) :: SymM -> SymM -> Bool max :: SymM -> SymM -> SymM min :: SymM -> SymM -> SymM
Show SymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods showsPrec :: Int -> SymM -> ShowS show :: SymM -> String showList :: [SymM] -> ShowS
Graded SymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: SymM -> Int Source #
(Eq k, Num k) => HopfAlgebra k SymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods antipode :: Vect k SymM -> Vect k SymM Source #
(Eq k, Num k) => Bialgebra k SymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra
(Eq k, Num k) => Coalgebra k SymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods counit :: Vect k SymM -> k Source # comult :: Vect k SymM -> Vect k (Tensor SymM SymM) Source #
(Eq k, Num k) => Algebra k SymM Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods unit :: k -> Vect k SymM Source # mult :: Vect k (Tensor SymM SymM) -> Vect k SymM Source #
(Eq k, Num k) => HasPairing k SymH SymM Source # | A duality pairing between the complete and monomial bases of Sym, showing that Sym is self-dual.
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods pairing :: Vect k (Tensor SymH SymM) -> Vect k () Source #

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

Instances details

Eq SymE Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods (==) :: SymE -> SymE -> Bool (/=) :: SymE -> SymE -> Bool
Ord SymE Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods compare :: SymE -> SymE -> Ordering (<) :: SymE -> SymE -> Bool (<=) :: SymE -> SymE -> Bool (>) :: SymE -> SymE -> Bool (>=) :: SymE -> SymE -> Bool max :: SymE -> SymE -> SymE min :: SymE -> SymE -> SymE
Show SymE Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods showsPrec :: Int -> SymE -> ShowS show :: SymE -> String showList :: [SymE] -> ShowS
Graded SymE Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: SymE -> Int Source #
(Eq k, Num k) => Bialgebra k SymE Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra
(Eq k, Num k) => Coalgebra k SymE Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods counit :: Vect k SymE -> k Source # comult :: Vect k SymE -> Vect k (Tensor SymE SymE) Source #
(Eq k, Num k) => Algebra k SymE Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods unit :: k -> Vect k SymE Source # mult :: Vect k (Tensor SymE SymE) -> Vect k SymE Source #

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

Instances details

Eq SymH Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods (==) :: SymH -> SymH -> Bool (/=) :: SymH -> SymH -> Bool
Ord SymH Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods compare :: SymH -> SymH -> Ordering (<) :: SymH -> SymH -> Bool (<=) :: SymH -> SymH -> Bool (>) :: SymH -> SymH -> Bool (>=) :: SymH -> SymH -> Bool max :: SymH -> SymH -> SymH min :: SymH -> SymH -> SymH
Show SymH Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods showsPrec :: Int -> SymH -> ShowS show :: SymH -> String showList :: [SymH] -> ShowS
(Eq k, Num k) => Bialgebra k SymH Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra
(Eq k, Num k) => Coalgebra k SymH Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods counit :: Vect k SymH -> k Source # comult :: Vect k SymH -> Vect k (Tensor SymH SymH) Source #
(Eq k, Num k) => Algebra k SymH Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods unit :: k -> Vect k SymH Source # mult :: Vect k (Tensor SymH SymH) -> Vect k SymH Source #
(Eq k, Num k) => HasPairing k SymH SymM Source # | A duality pairing between the complete and monomial bases of Sym, showing that Sym is self-dual.
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods pairing :: Vect k (Tensor SymH SymM) -> Vect k () Source #

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

Instances details

Eq NSym Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods (==) :: NSym -> NSym -> Bool (/=) :: NSym -> NSym -> Bool
Ord NSym Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods compare :: NSym -> NSym -> Ordering (<) :: NSym -> NSym -> Bool (<=) :: NSym -> NSym -> Bool (>) :: NSym -> NSym -> Bool (>=) :: NSym -> NSym -> Bool max :: NSym -> NSym -> NSym min :: NSym -> NSym -> NSym
Show NSym Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods showsPrec :: Int -> NSym -> ShowS show :: NSym -> String showList :: [NSym] -> ShowS
Graded NSym Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods grade :: NSym -> Int Source #
(Eq k, Num k) => HopfAlgebra k NSym Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods antipode :: Vect k NSym -> Vect k NSym Source #
(Eq k, Num k) => Bialgebra k NSym Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra
(Eq k, Num k) => Coalgebra k NSym Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods counit :: Vect k NSym -> k Source # comult :: Vect k NSym -> Vect k (Tensor NSym NSym) Source #
(Eq k, Num k) => Algebra k NSym Source # |
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods unit :: k -> Vect k NSym Source # mult :: Vect k (Tensor NSym NSym) -> Vect k NSym Source #
(Eq k, Num k) => HasPairing k NSym QSymM Source # | A duality pairing between NSym and QSymM (monomial basis), showing that NSym and QSym are dual.
Instance details Defined in Math.Combinatorics.CombinatorialHopfAlgebra Methods pairing :: Vect k (Tensor NSym QSymM) -> Vect k () Source #

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

descendingTree :: Ord a => [a] -> PBT a 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 a1 => PBT a2 -> [a1] Source #

maxPerm :: Num a1 => PBT a2 -> [a1] Source #

leftLeafComposition :: PBT a -> [Int] Source #

leftLeafComposition' :: YSymF a -> 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 a => [a] -> [Int] Source #

descentComposition :: (Ord a1, Num a2) => [a1] -> [a2] 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 a -> 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 :: (Eq k, Num k) => Vect k NSym -> Vect k SSymF Source #