The number of unrelated partitions (Q1112025): Difference between revisions

Let X be a set with n elements and write \(\Pi_ k\) for the set of all ordered partitions of X into k sets. The weight of a partition \(A=(A_ i)^ k_ 1\) is \[ w(A)=w(A_ 1,...,A_ k)=\left[ \begin{matrix} n\\ a_ 1,...,a_ k\end{matrix} \right]^{-1}=\frac{a_ 1!...a_ k!}{n!}, \] where \(a_ i=| A_ i|\). Two partitions \(A=(A_ i)^ k_ 1\) and \(B=(B_ i)^ k_ 1\) are called unrelated if there is no i such that \(A_ i\neq B_ i\) and either \(A_ i\subset B_ i\) or \(B_ i\subset A_ i.\) The author proves in this note that if \({\mathcal A}\subseteq \Pi_ k\) is a family of unrelated partitions then \(\sum_{A\in {\mathcal A}}w(A)\leq 1\). Moreover equality holds here iff \(n=a_ 1+...+a_ k\) and \({\mathcal A}\) consists of all partitions \(A=(A_ i)^ k_ 1\) with \(| A_ i| =a_ i\), \(1\leq i\leq k\).