Suppose that $X = \{x_1, \ldots, x_n\}$, and $k\geq 1$ is given. Count the number of ways that we could cover $X$ with $k$-subsets $Y_1, \ldots, Y_n$ (note that here, $n = |X|$), such that every $x_i$, $1\leq i \leq n$, appears in exactly $k$ of $Y_j$'s.

I appreciate if you could give some hint, or let me know if this is a known problem.

  • $\begingroup$ Maybe it's just me, but it seems to me that there's been an increase in questions here recently that want to "count the number" of something. You count the coverings of the set, not their number. $\endgroup$
    – joriki
    Commented Mar 22, 2020 at 13:13
  • $\begingroup$ I assume that the identity of the elements $x_j$ matters, i.e. if one covering had $Y_1=\{x_1,x_2\}$, $Y_2=\{x_1,x_3\}$ and another had $Y_1=\{x_4,x_2\}$, $Y_2=\{x_4,x_3\}$, they would be considered different? What about the identity of the subsets – would coverings with $Y_1=\{x_1,x_2\}$, $Y_2=\{x_1,x_3\}$ and with $Y_1=\{x_1,x_3\}$, $Y_2=\{x_1,x_2\}$ be considered different? And may two of the $Y_j$ be equal? $\endgroup$
    – joriki
    Commented Mar 22, 2020 at 16:10
  • $\begingroup$ Hi, Please note that in my question, I emphasized that $n = |X|$; so in your example, you should have $Y_1, Y_2, Y_3$ and $Y_4$ - not just two $Y_j$'s. Yes, the labels of the subsets matters, I guess.... Anyway, if you could suggest a solution for any of these cases, I would be thankful. $\endgroup$
    – user24175
    Commented Mar 23, 2020 at 5:22
  • $\begingroup$ Yes, I didn't want to write out a full example, these were just some of the sets. It's good that the labels of the subsets matter; that makes the situation more symmetric. You didn't answer the question whether two of the $Y_j$ may be equal? $\endgroup$
    – joriki
    Commented Mar 23, 2020 at 5:50
  • $\begingroup$ They are allowed to be equal $\endgroup$
    – user24175
    Commented Mar 24, 2020 at 6:35


You must log in to answer this question.

Browse other questions tagged .