Partitions of a finite set into structured subsets

From MaRDI portal





A set \(P\) of non-empty subsets (called classes) of a finite set \(F\) (which has \(n>1\) objects) is a partition of \(F\) if every pair of classes have empty intersection while their Union is \(F\). On each of the classes a ``structure can be imposed; the author avoids a ``heavy general description, relying up on several examples to explain the ideas. A structure on a class \(S\), of \(s\) objects, is described by a graph (sometimes directed) on \(s\) points (which represent the \(s\) objects); the characteristic group \(G\) (of order \(g\)) of the structure consists of all the permutations of the \(s\) points which preserve the incidence relations of the graph. Given a sequence of structures (say the \(i^{th}\) has char. group of order \(g_i\)), the problem is to compute \(P\), the number of different partitions of a set of \(n\) objects with \(k\) admissibly structured classes (i.e., each class of the partition is endowed with a structure chosen from the given sequence). The solution uses the series \(\frac{x^{s_1}}{g_1} + \frac{x^{s_2}}{g_2}+ \dots + \frac{x^{s_m}}{g_m} = \dots = \psi(x)\), whose terms are associated with the full sequence of admissible structures. The author proves that \(1 = \sum_{n=1}^\infty\sum_{k=1}^nP_k^n\frac{x^nv^k}{n!}=e^{v\psi(x)}\) . For example, if the \(m^{th}\) admissible structure consists of \(m\) isolated points, with group \(G_m\) of order \(m!\), then \(\psi(x)=\frac x{1!}+\frac{x^2}{2!}+\dots+\frac{x^m}{m!}+\dots=e^x-1\) and \(1 = \sum_{n=1}^\infty\sum_{k=1}^nP_k^n\frac{x^nv^k}{n!}=e^{v(e^x-1)}\) and hence \(P_k^n=S_k^n\), a Stirling number of the second kind. Another example leads to the Stirling numbers of the first kind. Still further examples yield other interesting numbers such as \(\frac{n!}{k!}{{n-1}\choose{k-1}}\) and \({n\choose k}k^{n-k}\). Several of the examples lead to the polynomial \(P_1^nz+P_2^nz^2+\dots+P_n^nz^n\) having only real zeros for \(n=1,2,3,\dots\), while others do not have this property, so the author leaves the reader the open question: is there a simple general rule to decide which sequences of structures lead to polynomials with this property?











This page was built for publication: Partitions of a finite set into structured subsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4133644)