×

The functorial composition of species, a forgotten operation. (English) Zbl 0759.05099

A. Joyal introduced the notion of species of structures. (It is a functor \(f:B\to B\) where \(B\) denotes the category of finite sets and bijections.) The authors have concentrated on the composition of functors. Although it is one of the most natural operations on species it has been mostly overlooked up to now. The authors introduce concepts of cyclic type and fixed points enumerator of a species. They establish basic formulas and compute cycle index series of classes of graphs, pure \(m\)-complexes, coverings and \(m\)-ary relations structured in various ways. Since the paper brings interesting results for “every-day-life” structures and it has a rich list of references, it can be interesting also for a reader not familiar with the notion of species.
Reviewer: J.Vinárek (Praha)

MSC:

05E99 Algebraic combinatorics
05A15 Exact enumeration problems, generating functions
05A05 Permutations, words, matrices
05C30 Enumeration in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bergeron, F., Une combinatoire du pléthysme, J. Combin. Theory Ser. A, 46, 2, 291-305 (1987) · Zbl 0644.05003
[2] Bergeron, F., A combinatorial outlook on symmetric functions, J. Combin. Theory Ser. A, 50, 2, 226-234 (1989) · Zbl 0672.05004
[3] Bergeron, F.; Cartier, G., Darwin: Computer algebra and enumerative combinatorics, (Cori, R.; Wirsing, M., Proc. STACS 88 5th Ann. Symp. on Theoretical Aspects of Computer Science, Bordeaux, France 1988. Proc. STACS 88 5th Ann. Symp. on Theoretical Aspects of Computer Science, Bordeaux, France 1988, Lecture Notes in Computer Science, 294 (1988), Springer: Springer Berlin), 393-394
[4] Bogart, K.; Gordon, J., Hypergraphs, Characteristic polynomials and permutation characters, Linear and Multilinear Algebra, 7, 213-236 (1979) · Zbl 0428.05041
[5] Bergeron, F.; Labelle, G.; Leroux, P., Functional equations for data structures, (Cori, R.; Wirsing, M., Proc. STACS 88 5th Ann. Symp. on theoretical Aspects of Computer Science, Bordeaux, France 1988. Proc. STACS 88 5th Ann. Symp. on theoretical Aspects of Computer Science, Bordeaux, France 1988, Lecture Notes in Computer Science, 294 (1988), Springer: Springer Berlin), 73-80
[6] Comtet, L., Analyse Combinatoire, Vol. 1 (1970), Presses Universitaires de France: Presses Universitaires de France Paris · Zbl 0221.05001
[7] Comtet, L., Recouvrements, bases de filtre et topologies d’un ensemble fini, C. R. Acad. Sci. Paris, 1091-1094 (1966) · Zbl 0152.39701
[8] Constantineau, I.; Labelle, J., Le nombre d’endofonctions et arborescences laissées fixes par l’action d’une permutation, Ann. Sci. Math. Québec, 13, 2, 33-38 (1989) · Zbl 0721.05003
[9] Davis, R. L., The number of structures of finite relations, Proc. Amer. Math. Soc., 4, 486-495 (1953) · Zbl 0051.24702
[10] De Bruijn, N. G., Pólya’s Theory of Counting, (Beckenbach, E. F., Applied Combinatorial Mathematics (1964), Wiley: Wiley New York) · Zbl 0144.00601
[11] Harary, F., Applications of Pólya’s theorem to permutation groups, (Harary, F., A Seminar on Graph Theory (1967), Academic Press: Academic Press New York), 1-41
[12] Harary, F.; Palmer, E., Graphical Enumeration (1973), Academic Press: Academic Press New York · Zbl 0266.05108
[13] Joyal, A., Une théorie combinatoire des séries formelles, Adv. in Math., 42, 1-82 (1981) · Zbl 0491.05007
[14] Joyal, A., Foncteurs analytiques et espèces de structures, (Labelle, G.; Leroux, P., Proc. Combinatoire Énumérative, Montréal Québec 1985. Proc. Combinatoire Énumérative, Montréal Québec 1985, Lecture Notes in Mathematics, 1234 (1986), Springer: Springer Berlin), 126-159
[15] Kerber, A., Der Zykelindex der Exponentialgruppe, Mitt. Math. Sem. Giessen, 98, 5-20 (1973) · Zbl 0258.20045
[16] Labelle, G., Some New Computational Methods in the Theory of Species, (Labelle, G.; Leroux, P., Proc. Combinatoire Énumérative, Montréal Québec 1985. Proc. Combinatoire Énumérative, Montréal Québec 1985, Lecture Notes in Mathematics, 1234 (1986), Springer: Springer Berlin), 192-209
[17] Labelle, G., On the generalized iterates of Yeh’s combinatorial \(K\)-species, J. Combin. Theory Ser. A, 50, 235-258 (1989) · Zbl 0667.05005
[18] Labelle, G., Dérivées directionnelles et développements de Taylor combinatoires, Discrete Math., 79, 279-297 (1989/90) · Zbl 0717.05003
[19] Leroux, P., Methoden der Anzahlbestimmung für einige Klassen von Graphen, Bayreuth. Math. Schr., 26, 1-36 (1988)
[20] (Labelle, G.; Leroux, P., Combinatoire Énumérative, Montréal Québec 1985, Proceedings. Combinatoire Énumérative, Montréal Québec 1985, Proceedings, Lecture Notes in Mathematics, 1234 (1986), Springer: Springer Berlin)
[21] Leroux, P.; Viennot, G. X., Combinatorial resolution of systems of differential equations, IV: Separation of variables, Discrete Math., 72, 237-250 (1988) · Zbl 0696.34008
[22] Labelle, J.; Yeh, Y. N., The relation between Burnside rings and combinatorial species, J. Combin. Theory Ser. A, 50, 2, 269-284 (1989) · Zbl 0671.20004
[23] Oberschelp, W., Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174, 53-58 (1967) · Zbl 0155.35002
[24] Pólya, G.; Read, R. C., Combinatorial Enumeration of Groups, (Graphs and Chemical Compounds (1987), Springer: Springer Berlin)
[25] Rota, G. C.; Smith, D. A., Enumeration under group action, Ann. Scuola Norm. Sup. Pisa Cl. Sci, 4, 4, 637-646 (1977) · Zbl 0367.05008
[26] Strehl, V., Combinatorics of Jacobi-configurations III: The Srivastava-Singhal generating function revisited, Discrete Math., 73, 221-232 (1988/89) · Zbl 0672.05010
[27] Thürlings, K.-J., Direkte Berechnung specieller Anzahlen in Pólyas Abzähltheorie, Informal Comm. Math. Chemistry (Match), 4, 161-171 (1978) · Zbl 0397.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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.