3
$\begingroup$

A set $M$ consists of $n$ elements. Determine the number of pairs of subsets of $M$ which have no elements in common (don't forget to account for the empty set).

If we choose a subset of one element, then there are $(n-1)+1$ corresponding different subsets of the same size, hence the total is ${n\choose1}+\frac12{{n-1}\choose 1}{n\choose1}$ when we shuffle through each subset and repeat the same operation.

Then, if we choose one with two elements, then there are $1+{{n-2}\choose1}+{{n-2}\choose2}$ corresponding different subsets of the same size and of size = 2-1, which gives us a total of ${n\choose2}+{{n-2}\choose1}{{n}\choose2}+\frac12{{n-2}\choose2}{n\choose2}$.

With three, we get for the one selection ${n\choose3}+{{n-3}\choose1}{n\choose3}+{{n-3}\choose2}{n\choose3}+\frac12{{n-3}\choose3}{n\choose3}$ for the same size, size-1 and size-2.

If I am to do this for a subset with $k$ elements, then the total is $s_k={n\choose k}+\frac12{{n-k}\choose k}{n\choose k}+\sum_{i=1}^{k-1}{{n-k}\choose i}{n\choose k}$.

The big total is when I shuffle through all possible values of $k$, so $\sum_{k=1}^{n-1}s_k$.

Is there any flaw in my reasoning? Thank you for your time!

$\endgroup$
1
  • $\begingroup$ Ordered pairs or unordered pairs? $\endgroup$ – Thomas Andrews Jan 20 at 20:45
6
$\begingroup$

Note: Like you, I take pairs to mean unordered pairs. If ordered pairs are intended, the calculation is a bit simpler, both via your approach and via mine.


The explanation could be a good bit clearer, but it appears to be right. However, it results in a very complicated expression that can be greatly simplified. It’s easier, however, to adopt a different approach from the start.

We can choose disjoint subsets of $M$ by first choosing a set $C\subseteq M$ and then partitioning $C$ into two sets. There are $\binom{n}k$ ways to choose a $C\subseteq M$ of cardinality $k$. $C$ has $2^k$ subsets, and if $k>0$, these subsets come in $2^{k-1}$ complementary pairs. Thus, $C$ can be split into two disjoint subsets in $2^{k-1}$ ways if $k>0$. If $k=0$, $C=\varnothing$, which is the union of two disjoint subsets in only one way: $\varnothing=\varnothing\cup\varnothing$. Altogether, then there are

$$\begin{align*} 1+\sum_{k=1}^n\binom{n}k2^{k-1}&=1+\frac12\sum_{k=1}^n\binom{n}k2^k\\ &=1+\frac12\left(\sum_{k=0}^n\binom{n}k2^k-\binom{n}02^0\right)\\ &\overset{*}=1+\frac12\left(3^n-1\right)\\ &=\frac12\left(3^n+1\right)\,, \end{align*}$$

where the starred step uses the binomial theorem applied to $(2+1)^n$.

$\endgroup$
5
  • $\begingroup$ Hi professor, could I ask your assistance here, please? $\endgroup$ – Antonio Maria Di Mauro Jan 20 at 21:50
  • $\begingroup$ @AntonioMariaDiMauro: I just now got there, and I think that between them Hagen and Danny have pretty well covered the ground. $\endgroup$ – Brian M. Scott Jan 20 at 21:58
  • 1
    $\begingroup$ Yes, I saw. I agree with you. Thanks anyway. $\endgroup$ – Antonio Maria Di Mauro Jan 20 at 22:12
  • $\begingroup$ Hello @BrianM.Scott, and thank you for your answer! I didn't find the same number of complementary subsets as you.. If I take a subset of size $i$, then I can pair it with subsets that are made of $k-i$ elements, with the special case of $\{\phi\}\cup(C-\{\phi\})$. So the total is $1+\frac12\sum_{i=1}^{k-1}{k\choose i}{{k-i}\choose{k-i}}$. Where have I mistaken? $\endgroup$ – Luyw Jan 21 at 5:20
  • $\begingroup$ Never mind, it is correct. Sorry! $\endgroup$ – Luyw Jan 21 at 5:32
4
$\begingroup$

Number of ordered pairs: since each element is either in subset $A$, or subset $B$, or neither, it's $3^n$.

Number of unordered pairs: if $A \neq B$, the pair is counted twice in the ordered case. Only when they are both empty are they the same, which was counted once. Therefore the total number of unordered pairs is $1+(3^n-1)/2=(3^n+1)/2$.

$\endgroup$
2
$\begingroup$

The question asks for pairs of subsets that share no elements. When I read "pairs", I typically assume that means an ordered pair of sets. This would mean that the question is asking for the number of pairs of subsets $(A, B)$ where $A\cap B=\varnothing$. Your answer works if the question wants you to count the number of sets $\{A, B\}$ where $A\cap B=\varnothing$ (though you could consider the case that $A=B=\varnothing$, in which case you're off by $1$). I'll give an answer for the ordered case, which is what I assume is intended.

One approach is to revise your argument to treat the subsets as being distinct. We let $t_k$ count the number of pairs of subsets $(A, B)$ such that $A$ and $B$ have no elements in common, and $|A|=k$. Then $$t_k={n\choose k}\sum_{i=0}^k {n-k\choose i}.$$ That is, you first choose a subset $A$ of $k$ elements, then you choose a subset $B$ from the remaining $n-k$ elements of arbitrary size. Hence, the number of such pairs can be counted by $$\sum_{k=0}^n t_k.$$

However, the nice thing about the ordered case is that there's a much easier way of counting such pairs. Each element $x$ of $M$ has three choices. Either

  1. $x\in A$ and $x\notin B$,
  2. $x\notin A$ and $x\in B$, or
  3. $x\notin A$ and $x\notin B$.

For each of these $n$ elements, you choose one of these three options, so there are $3^n$ possible pairs.

$\endgroup$
2
  • $\begingroup$ This reflects nicely with the fact that there are $2^n$ subsets of $\{1,\cdots,n\}$ and $(2^n)^2 = (2^{2n}) = (2^2)^n=4^n$ pairs of subsets of $\{1,\cdots,n\}$! $\endgroup$ – Patrick Da Silva Jan 20 at 20:53
  • 1
    $\begingroup$ In my experience the default interpretation of pairs is unordered pairs. $\endgroup$ – Brian M. Scott Jan 20 at 20:54

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.