Combinatorics of normal sequences of braids

Many natural counting problems arise in connection with the normal form of braids-and seem to have not been much considered so far. Here we solve some of them. One of the noteworthy points is that a number of different induction schemes appear. The key technical ingredient is an analysis of the normality condition in terms of permutations and their descents, in the vein of the Solomon algebra. As was perfectly summarized by a referee, the main result asserts that the size of the automaton involved in the automatic structure of B"n associated with the normal form can be lowered from n! to p(n), the number of partitions of n.

• Publication year

  2005

• Venue

  Journal of Combinatorial Theory

• Publication date

  2005-11-04

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.jcta.2006.06.004arXiv math/0511114
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Growth function for a class of monoids

  2009cited by this paper
• Still another approach to the braid ordering

  2005cited by this paper
• AN INTRODUCTION TO GARSIDE STRUCTURES

  2005cited by this paper
• A New Approach to the Conjugacy Problem in Garside Groups

  2003cited by this paper
• Why are braids orderable

  2002cited by this paper
• The dual braid monoid

  2001cited by this paper
• Groupes de Garside

  2001cited by this paper
• New Public-Key Cryptosystem Using Braid Groups

  2000cited by this paper
• Gaussian Groups and Garside Groups, Two Generalisations of Artin Groups

  1999cited by this paper
• A new approach to the word and conjugacy problems in the braid groups

  1997cited by this paper
• Growth Functions and Automatic Groups

  1996cited by this paper
• Geodesic automation and growth functions for Artin groups of finite type

  1995cited by this paper
• ALGORITHMS FOR POSITIVE BRAIDS

  1994cited by this paper
• Growth of the positive braid semigroups

  1992cited by this paper
• Word processing in groups

  1992influential reference
• Artin groups of finite type are biautomatic

  1992influential reference
• Enumeration of pairs of permutations

  1976influential reference
• A Mackey formula in the group ring of a Coxeter group

  1976influential reference
• Braids, Links, and Mapping Class Groups.

  1975cited by this paper
• Enumeration of pairs of permutations and sequences

  1974cited by this paper
• Les immeubles des groupes de tresses généralisés

  1972cited by this paper
• THE BRAID GROUP AND OTHER GROUPS

  1969influential reference
• Inverse Relations and Combinatorial Identities

  1964cited by this paper

• Experiments on growth series of braid groups

  2020cites this paper
• A divisibility result in combinatorics of generalized braids

  2017cites this paper
• Uniform measures on braid monoids and dual braid monoids

  2016cites this paper
• Combinatorial aspects of braids with applications to cryptography

  2015cites this paper
• Cataland: Why the Fuss?

  2015cites this paper
• Dual Garside structure of braids and free cumulants of products

  2014cites this paper
• On the penetration distance in Garside monoids

  2014cites this paper
• On the genericity of pseudo-Anosov braids I: rigid braids

  2013cites this paper
• THÈSE / UNIVERSITÉ DE RENNES 1 sous le sceau de l'Université Européenne de Bretagne pour le grade de DOCTEUR DE L'UNIVERSITÉ DE RENNES 1 Mention : mathématiques et applications Ecole doctorale Matisse présentée par

  2013cites this paper
• Algorithmes et généricité dans les groupes de tresses

  2013cites this paper
• Foundations of Garside Theory

  2013cites this paper
• Computing growth functions of braid monoids and counting vertex-labelled bipartite graphs

  2012cites this paper
• Tresses, animaux, cartes : à l'interaction entre combinatoire et probabilité

  2008cites this paper
• Sur une conjecture de Dehornoy

  2007cites this paper
• Bijective combinatorics of positive braids

  2007cites this paper
• Unprovability results involving braids

  2007cites this paper
• See Section 1 for Definitions

  2007cites this paper
• Sur une conjecture de Dehornoy

  2007cites this paper
• Long games on positive braids

  2007cites this paper
• Still another approach to the braid ordering

  2005cites this paper