The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group
type: Item
instance of: scholarly article
title: The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group
zbMATH Open document ID: 0804.05023
DOI: 10.1016/S0195-6698(05)80015-0
published in: European Journal of Combinatorics
publication date: 1993-01-16T00:00:00Z
review text: An \(m\)-cactus is a connected graph in which every edge lies on exactly one cycle, which has length \(m\) (case \(m=2\) corresponds to trees). If \(\sigma \in S_ n\) is a permutation, let \(\alpha (\sigma)\) be a partition of \(n\), corresponding its cyclic structure, \(l(\sigma)\) its length (number of cycles). A combinatorial bijection between \(m\)-cacti and \(m\)-tuples \((\sigma_ 1, \sigma_ 2, \dots, \sigma_ m)\) such that \(\sigma_ 1 \sigma_ 2 \dots \sigma_ m = (1,2, \dots,n)\) and \(\sum I (\sigma_ i) = n + 1\) is established. If \(K_ \alpha = \sum_{\alpha (\sigma) = \alpha} \sigma\) is an element of a group algebra, this bijection permits to find the exact value of the coefficient \(c^{(n)}\) in the decomposition \(K_{\alpha_ 1} K_{\alpha_ 2} \cdots K_{\alpha_ m} = \sum_ \gamma c^ \gamma K_ \gamma\).
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05A17
Mathematics Subject Classification ID: 20B30
zbMATH DE Number: 94938
zbMATH Keywords: symmetric group
zbMATH Keywords: cactus
zbMATH Keywords: cycle
zbMATH Keywords: tree
zbMATH Keywords: partition
zbMATH Keywords: group algebra
zbMATH Keywords: coefficient
author: I. P. Goulden
author: David M. Jackson
reviewed by: Victor Ufnarovski
MaRDI profile type: Publication
cites work: Decomposing a Permutation into Two Large Cycles: An Enumeration
cites work: Nombre de représentations d'une permutation comme produit de deux cycles de longueurs données
cites work: Q3669422
cites work: On products of conjugacy classes of the symmetric group
cites work: Q5682013
cites work: Counting Cycles in Permutations by Group Characters, With an Application to a Topological Problem
cites work: Counting Semiregular Permutations which are Products of a Full Cycle and and an Involution
cites work: Some combinatorial problems associated with products of conjugacy classes of the symmetric group
cites work: A Character Theoretic Approach to Embeddings of Rooted Maps in an Orientable Surface of Given Genus
cites work: Character Theory and Rooted Maps in an Orientable Surface of Given Genus: Face-Colored Maps
cites work: Factorization of permutations into n-cycles
cites work: The Number of Planted Plane Trees with a Given Partition
cites work: How many ways can a permutation be factored into two n-cycles?
description: scientific article; zbMATH DE number 94938