Dividing a set into 4 subsets with conditions?

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$.

• What are your thoughts? – user159517 Sep 24 '17 at 9:59
• I didn't have any ideas for that problem, maybe using 2-counting ways? – Huong Dang Sep 24 '17 at 10:08
• or Inclusion - Exclusion? – Huong Dang Sep 24 '17 at 10:16
• 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. – 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}