Hopf Algebras of Heap Ordered Trees and Permutations

Abstract

A standard heap ordered tree with n + 1 nodes is a finite rooted tree in which all the nodes except the root are labeled with the natural numbers between 1 and n, and that satisfies the property that the labels of the children of a node are all larger than the label of the node. Denote the set of standard heap ordered trees with n + 1 nodes by 𝒯 _n . Let

It is known that there are Hopf algebra structures on k 𝒯. Let 𝔖 _n denote the symmetric group on n symbols. Let

We give a bialgebra structure on k𝔖, and show that there is a natural bialgebra isomorphism from k𝒯 to k𝔖.

Key Words:

• Bialgebras
• Hopf algebras
• Permutations
• Trees

2000 Mathematics Subject Classification:

• 16W30
• 20B30
• 05C05

Notes

Communicated by M. Cohen.