The enumeration of irreducible combinatorial objects (Q1072554): Difference between revisions

This paper (we are told in its acknowledgement) was developed as part of the author's doctoral dissertation written under the direction of Herbert Wilf who gave the initial push. The paper deals with an important topic in the classical theory of combinatorial enumeration, and surprisingly (because one might suppose the subject to be exhausted by now) a fresh point of view is offered which produces new results. A unique factorization theory is given for combinatorial objects which are modeled as hypergraphs having vertex set \(Z_n=\{1,\dots,n\}\). The edge set is a collection of subsets of \(Z_n\). Such a theory has a notion of ''product'' and ``irreducible''. The notion of irreducibility depends on a family of partitions of \(Z_n\), and when the family satisfies certain conditions there is a unique factorization theory. The author credits \textit{D. Foata} and \textit{M. P. Schützenberger} [Théorie géométrique des polynômes eulériens. Berlin etc.: Springer Verlag (1970; Zbl 0214.26202)] as the inventors of the idea which is generalized in this work. The unique factorization theory leads to a simple relationship between the generating function for all objects and the generating function for irreducible objects.