The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group (Q1199773): Difference between revisions

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