×

zbMATH — the first resource for mathematics

The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group. (English) Zbl 0804.05023
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\).

MSC:
05C05 Trees
05A17 Combinatorial aspects of partitions of integers
20B30 Symmetric groups
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bertram, E.A.; Wei, V.K., Decomposing a permutation into two large cycles: an enumeration, SIAM J. alg. discr. methods, 1, 450-461, (1980) · Zbl 0499.05003
[2] Boccara, G., Nombre de représentations d’une permutation comme produit de deux cycles de longueurs données, Discr. math., 29, 105-134, (1980) · Zbl 0444.20003
[3] Goulden, I.P.; Jackson, D.M., Combinatorial enumeration, (1983), Wiley-Interscience Princeton · Zbl 0519.05001
[4] A. Goupil and F. Bédard, The lattice of conjugacy classes of the group (preprint). · Zbl 0695.20006
[5] Harary, F.; Palmer, E., Graphical enumeration, (1973), Academic Press New York · Zbl 0266.05108
[6] Jackson, D.M., Counting cycles in permutations by group characters, with an application to a combinatorial problem, Trans. AMS, 299, 785-801, (1987) · Zbl 0655.05005
[7] Jackson, D.M., Counting semi-regular permutations which are products of a full cycle and an involution, Trans. AMS, 305, 317-331, (1988) · Zbl 0634.05008
[8] Jackson, D.M., Some problems associated with products of conjugacy classes of the symmetric group, J. combin. theory, ser. A, 49, 363-369, (1988) · Zbl 0682.20002
[9] Jackson, D.M.; Visentin, T.I., A character theoretic approach to embeddings of rooted maps in an orientable surface of given genus, Trans. AMS, 322, 343-363, (1990) · Zbl 0747.05008
[10] Jackson, D.M.; Visentin, T.I., Character theory and rooted maps on an orientable surface of given genus: face-coloured maps, Trans. AMS, 322, 365-376, (1990) · Zbl 0738.05005
[11] Sherman, J.; Morrison, W.J., Adjustments of an inverse matrix corresponding to changes in the elements of a given row or a given column of the original matrix, Ann. math. statist., 20, 621, (1949)
[12] Stanley, R.P., Factorization of a permutation into n-cycles, Discr. math., 37, 255-262, (1981) · Zbl 0467.20005
[13] Tutte, W.T., The number of plane planted trees with a given partition, Am. math. monthly, 71, 272-277, (1964) · Zbl 0117.17403
[14] Walkup, D.W., How many ways can a permutation be factored into two n-cycles?, Discr. math., 28, 315-319, (1979) · Zbl 0429.05006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.