On the symmetry and asymmetry of combinatorial structures (Q688675): Difference between revisions

This is mainly a review article which presents a number of recently- published results about five series associated with a given species \(F\) of structures on a set of points (species of structures were first introduced in \textit{A. Joyal} [Une théorie combinatoire des séries formelles, Adv. Math. 42, 1-82 (1981; Zbl 0491.05007)]). If \(f_ n\), \(\widetilde f_ n\) and \(\bar f_ n\) are, respectively, the number of \(F\)-structures, types (isomorphism classes) of \(F\)-structures and types of asymmetric \(F\)-structures on \(n\) points, then the following three power series are defined: \[ F(x)= \sum_{n\geq 0} f_ n {x^ n\over n!},\quad \widetilde F(x)= \sum_{n\geq 0} \widetilde f_ n x^ n, \quad \overline F(x)=\sum_{n\geq 0} \bar f_ n x^ n. \] In addition, two series in an indefinite number of variables are defined: the cycle index series \[ Z_ F(x_ 1,x_ 2,x_ 3,\dots)= \sum_{n\geq 0}{1\over n!} \sum_{\sigma\in S_ n} f_ \sigma x^{\sigma_ 1}_ 1 x^{\sigma_ 2}_ 2\cdots x^{\sigma_ n}_ n \] and the asymmetric index series \[ \Gamma_ F(x_ 1,x_ 2,x_ 3,\dots)= \sum_{n\geq 0} {1\over n!} \sum_{\sigma\in S_ n} f^*_ \sigma x^{\sigma_ 1}_ 1 x^{\sigma_ 2}_ 2\cdots x^{\sigma_ n}_ n, \] where \(S_ n\) is the symmetric group on \(n\) objects, \(\sigma_ i\) is the number of cycles of length \(i\) of the permutation \(\sigma\), \(f_ \sigma\) is the number of \(F\)-structures of which \(\sigma\) is an automorphism, but \(f^*_ \sigma\) has no simple interpretation and may even be negative. Section 1 states some theorems about the commutativity between the transformation from \(F\) to each of these five series and such operators as addition, multiplication, substitution and differentiation. Section 2 presents the series associated with some simple species including all the atomic species on \(n\leq 4\) points and discusses ways of calculating the series associated with the plethystic substitution of a given species into the species of sets, cycles and permutations. Section 3 discusses applications to \(R\)-enriched trees and rooted trees (a tree or a rooted tree is \(R\)-enriched if an \(R\)-structure is imposed on the neighbors or children of each vertex). Formulae are given for the associated series; and ordinary trees, rooted trees, endofunctions, plane trees, trees enriched by permutations, and trees with no vertices of degree 2 are treated as special cases. Section 4 contains some new results which are proved by presenting counterexamples: \(\bullet\) the transformations \(F\to\widetilde F(x)\) and \(F\to \overline F(x)\) do not commute with substitution or differentiation, \(\bullet\) \(\Gamma_ F\) is not a function of \(Z_ F\) and vice versa, \(\bullet\) the isomorphism class of a species is not a function of its five associated series, \(\bullet\) \(\Gamma_{F\times G}\) is not a function of \(\Gamma_ F\) and \(\Gamma_ G\). The bibliography contains 60 references which, together with the results quoted in the first three sections and the new ones derived in the last section, make this article a good starting point for anyone wishing to get a feel for the state of the art of species of structures and their associated series.