Let $C_1,\dots, C_m$ be a family of ordered set partitions of $[n]$ with exactly $k$ blocks.

Write $C_i = \{B_{i1}, \dots, B_{ik}\}$ for $i=1,\dots, m$ where $B_{ij}$ are the blocks of the ordered set partition $C_i$.

Suppose this family also has the property that for each $j=1,\dots, k$

$$B_{1j} \cup \cdots \cup B_{mj}$$

is also a partition of $[n]$

Can one determine the maximal number of members in such a family $m$, or at least a decent upper bound on $m$?


It might also be worth noting that if we take $k=n$, then $m=n$ since this would be equivalent to the existence of a latin square. I am in particular interested in the case $k=2$.


2 Answers 2


We have $$mn=\sum_i\sum_j |B_{ij}|=\sum_j\sum_i |B_{ij}|=kn,$$ thus $m=k$.


Answer: $m=k$.

Put indeed your blocks $B_{ij}$ in a $m\times k$ array and then "read" this array:

-- row-wise: any element of $[n]$ appears then $m$ times.

-- column-wise: any element of $[n]$ appears then $k$ times.

  • $\begingroup$ 26 seconds slower than Fedor, but my answer is better, does not use multiplication :) $\endgroup$
    – Richard
    Apr 9, 2019 at 17:09
  • $\begingroup$ you actually multiply 1 by $m$ and by $k$ :) $\endgroup$ Apr 9, 2019 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.