The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group. (English) Zbl 0804.05023

Goulden, I. P.; Jackson, D. M.

Eur. J. Comb. 13, No. 5, 357-365 (1992).

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

Reviewer: V.Ufnarovskij (Lund)

MSC:

05C05	Trees
05A17	Combinatorial aspects of partitions of integers
20B30	Symmetric groups

Keywords:

symmetric group; cactus; cycle; tree; partition; group algebra; coefficient

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