Given that a set $M$ has $35$ elements. How many ways to divide $M$ into $4$ subsets, namely $A_1, A_2, A_3, A_4$ satisfying all following conditions:

i) Each element in $M$ belongs at least one of four subsets ($A_1, A_2, A_3, A_4$).

ii) For any $ k \in \{2,3,4\}$ we have $| A_k \cap A_{k-1}| \geq 1$.

  • $\begingroup$ What are your thoughts? $\endgroup$ – user159517 Sep 24 '17 at 9:59
  • $\begingroup$ I didn't have any ideas for that problem, maybe using 2-counting ways? $\endgroup$ – Huong Dang Sep 24 '17 at 10:08
  • $\begingroup$ or Inclusion - Exclusion? $\endgroup$ – Huong Dang Sep 24 '17 at 10:16
  • $\begingroup$ Your problem statement is a bit confusing. Usually when we "divide" a set, we mean we write it as a union of disjoint subsets, but that is evidently not the case in this problem, because condition ii requires that the subsets are not disjoint. $\endgroup$ – awkward Sep 24 '17 at 14:04

Here is a solution by way of the Principle of Inclusion / Exclusion (PIE). Let $M = \{m_1, m_2, m_3, \dots ,m_{35}\}$.

We start by asking how many ways we can write $M$ as a union of four subsets $A_1, A_2, A_3, A_4$ if every element of $M$ must be in at least one subset, dropping condition (ii) for now. Consider one element, $m_i$, and let $$x_{ij} = \begin{cases} 1 \qquad \text{if } m_i \in A_j\\ 0 \qquad \text{otherwise} \end{cases}$$ Then there are $15$ possible choices for $(x_{i1}, x_{i2}, x_{i3}, x_{i4})$: all of the $2^4$ possibilities except for $(0,0,0,0)$, since $x_i$ must be in at least one subset. So all together there are $N = 15^{35}$ ways to write $M$ as a union of four subsets.

Let $P_k$ be the set of arrangements in which every element of $M$ is in at least one $A_k$ and $A_k \cap A_{k-1} = \emptyset$, for $k=2,3,4$. We write $|P_k|$ for the size of $P_k$, and we define $S_1$ = $|P_2|+|P_3|+|P_4|$. To find $|P_2|$, fix $i$ and consider the possible choices for $(x_{i1},x_{i2},x_{i3},x_{i4})$ for an element $m_i$. All choices are possible except for those of the form $(1,1,x_{i3},{x_{i4}})$ or $(0,0,0,0)$. It turns out there are $11$ possibilities. We could count the possibilities through another application of PIE, but it's probably easier to simply make a list of all $16$ possibilities for $(x_{i1},x_{i2},x_{i3},x_{i4})$ and cross out those which are excluded. So $|P_2| = 11^{35}$. The same is true of $|P_3|$ and $|P_4|$, so $S_1 = 3 \cdot 11^{35}$.

Now define $S_2 = |P_2 \cap P_3| + |P_2 \cap P_4| + |P_3 \cap P_4|$. To find $|P_2 \cap P_3|$, we again count the number of possibilities for $(x_{i1},x_{i2},x_{i3},x_{i4})$. This time the excluded cases are those of the form $(1,1,x_{i3},x_{i4})$, $(x_{i1}, 1, 1, x_{i4})$, or $(0,0,0,0)$. There are $9$ possibilities, so $|P_2 \cap P_3| = 9^{35}$. The case $|P_3 \cap P_4|$ is similar, so $|P_3 \cap P_4| = 9^{35}$, but the case $|P_2 \cap P_4|$ is a bit different. Here the excluded cases for $(x_{i1},x_{i2},x_{i3},x_{i4})$ are those of the form $(1,1,x_{i3}, x_{i4})$, $(x_{i1},x_{i2},1,1)$, or $(0,0,0,0)$. There are $8$ possibilities, so $|P_2 \cap P_4| = 8^{35}$. Hence $S_2 = 2 \cdot 9^{35} + 8^{35}$.

Next, define $S_3 = |P_2 \cap P_3 \cap P_4|$. The excluded cases for $(x_{i1},x_{i2},x_{i3},x_{i4})$ are those of the form $(1,1,x_{i3},x_{i4})$, $(x_{i1},1,1,x_{i4})$, $(x_{i1},x_{i2},1,1)$, or $(0,0,0,0)$. There are $7$ possibilities, so $S_3 = 7^{35}$.

Finally, by PIE the number of arrangements which fall in none of the sets $P_2$, $P_3$, or $P_4$, i.e. those which satisfy all the requirements (i) and (ii), is $$\begin{align} N_0 &= N - S_1 + S_2 - S_3\\ &= 15^{35} -3 \cdot 11^{35} + 2 \cdot 9^{35} + 8^{35} - 7^{35} \end{align}$$


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.