3
$\begingroup$

This is how far I could go..

example:
S = {1,2,3}
Unique possible subset pairs such that the intersection is {}
P = {}    Q = {}
P = {}    Q = {1}
P = {}    Q = {2}
P = {}    Q = {3}
P = {}    Q = {1,2}
P = {}    Q = {1,3}
P = {}    Q = {2,3}
P = {}    Q = {1,2,3}
P = {1}   Q = {2}
P = {1}   Q = {3}
P = {1}   Q = {2,3}
P = {2}   Q = {1}
P = {2}   Q = {3}
P = {2}   Q = {1,3}
P = {3}   Q = {1}
P = {3}   Q = {2}
P = {3}   Q = {1,2}
Total = 17

Subset X of $S$ with $0$ elements doesn't intersect with any subsets of $S$.

So, total pairs = ${n \choose 0} \times 2^n$

Subset $X$ of $S$ with $1$ element doesn't intersect with any subsets of $S-X$.

So, total pairs = ${n \choose 1} \times \left (2^{n-1} - 1 \right) $

$-1$ because the subset $\{\}$ of $S-X$ has already been counted.

Subset $X$ of $S$ with $2$ element doesn't intersect with any subsets of $S-X$.

So, total pairs = ${n \choose 2} \times \left (2^{n-2} - 1 \right) $

$\vdots$

while $|X| <= \frac{n}{2} $

So, total pairs are: $$\left \{ \sum_{r=0}^{\frac{n}{2}} {{n \choose r} \times 2^{n-r}} \right \} - \left \{ \sum_{r=1}^{\frac{n}{2}} {n \choose r} \right \}$$

which works. But how do I simplify it?

Also, what would be a better approach for this problem?

$\endgroup$
  • 1
    $\begingroup$ Why didn't you count $P=\{1\},Q=\{\}$? $\endgroup$ – bof May 16 '15 at 23:42
  • $\begingroup$ @bof: Since I am trying to count unique subset pairs. The pair $\left \{ \{1\}, \{\} \right \}$ is same as the pair $\left \{ \{\}, \{1\} \right \}$ $\endgroup$ – Pragy Agarwal May 16 '15 at 23:45
  • $\begingroup$ It doesn't matter since if I count them as seperate, the final answer will just be double of what I get with this. $\endgroup$ – Pragy Agarwal May 16 '15 at 23:47
  • 1
    $\begingroup$ @PragyAgarwal: If one carries out your analysis, preferably for ordered pairs first, one will notice the binomial expansion of $(1+2)^n$. That's another way of getting to the $3^n$. $\endgroup$ – André Nicolas May 17 '15 at 0:01
  • 1
    $\begingroup$ Yes, I noticed that inconsistency. Moreover, giving the two sets names, calling one $P$ and the other $Q$, really makes it seem like you are counting ordered pairs. $\endgroup$ – bof May 17 '15 at 1:13
9
$\begingroup$

First we look at the number of ordered pairs $(P,Q)$ such that $P\cap Q=\emptyset$. Equivalently, we count the number of functions $f:S\to\{1,2,3\}$, where $f(s)=1$ if $s\in P$, $f(s)=2$ if $s\in Q$, and $f(s)=3$ if $s$ is in neither $P$ nor $Q$. There are $3^n$ such functions.

If we want to count the unordered pairs (and the question seems to ask for that), note that in the count $3^n$, all unordered pairs appear twice, except $(\emptyset,\emptyset)$. So the number of unordered pairs is $\frac{3^n-1}{2}+1$.

$\endgroup$
  • $\begingroup$ What a nice answer! But when $S$ has $3$ elements, as Pragy has shown answer must be 17; while taking $n=3$ in this way gives $14$, so where is the problem? $\endgroup$ – Sry May 18 '15 at 4:47
  • $\begingroup$ In that list, $3$ items occur twice each. For example, one line (item 9) has $\{1\}$ then $\{2\}$. Three lines later the post lists $\{2\}$ then $\{1\}$. The count of $17$ is off by $3$. $\endgroup$ – André Nicolas May 18 '15 at 5:14
  • $\begingroup$ oh! I see. Thanks for pointing. $\endgroup$ – Sry May 18 '15 at 5:25
  • $\begingroup$ You are welcome. Explicit listing can be kind of tricky. It is all too easy to repeat, or to leave out something. $\endgroup$ – André Nicolas May 18 '15 at 5:31
  • $\begingroup$ Yes, you are right. The way you answered seems so good to me. $\endgroup$ – Sry May 18 '15 at 5:43
2
$\begingroup$

Note that the set $\mathcal{S}$ of ordered pairs $(P,Q)$ with the property described can be described by the following sequence of choices. For $0\leq k\leq n$ first choose a $k$-subset $P\subseteq S$ (for which there are ${n\choose k}$ options), and then choose a subset $Q\subseteq S\setminus P$ (for which there are $2^{n-k}$ options). Thus we obtain all such pairs and we have the following count:

$$|\mathcal{S}|=\sum_{k=0}^n{n\choose k}2^{n-k}$$ By the argument given in @Andre Nicolas' solution, we have $\sum_{k=0}^n{n\choose k}2^{n-k}=3^n$ (which is cool).

Note that my solution above assumes that we count ordered pairs of such sets. If we seek to count unordered pairs, then there is a bit more we must do. Let $S(k,m)$ be the Stirling number of the $2^{nd}$ kind (i.e. $S(k,m)$ counts the number of partitions of $\{1,2,\cdots,k\}$ into exactly $m$ blocks). Then the set $\mathcal{S}^{\prime}$ you seek to count is described by the following sequence of choices. First there is unordered intersection $\phi\cap Q$ where $Q\subseteq S$ which contributes $2^n$ to the sum; note that this counts all unordered pairs with one set a singleton or at least one the empty set. For $2\leq k\leq n$ we first choose a $k$-subset $A\subseteq S$ (for which there are ${n\choose k}$ options), and then choose a partition into exactly $2$ parts (for which there are $S(k,2)$ options). Thus we obtain all such unordered pairs and

$$|\mathcal{S}^\prime|=2^n+\sum_{k=2}^n{n\choose k}S(k,2)$$

It is possible to obtain a simple formula for $S(k,2)$. In particular it is easy to obtain the recursion $S(k,m)=S(k-1,m-1)+mS(k-1,m)$ for all $2\leq k\leq m$ (consider partitions which contain $\{k\}$ as a block and those that don't) and $S(k,1)=1$ for all $k\geq1$. By induction and the recursion we can show $S(k,2)=2^{k-1}-1$ for all $k\geq2$ (noting trivially that $S(m,m)=1$ for all $m\geq1$). Hence our formula reduces to the following:

$$|\mathcal{S}^\prime|=2^n+\sum_{k=2}^n{n\choose k}S(k,2)=2^n+\sum_{k=2}^n{n\choose k}(2^{k-1}-1)$$

If you check this against your example, you'll notice that I count $14$ possible unordered pairs for a set of size $3$. Checking your example, you've counted the pairs $\{\{1\},\{2\}\}$, $\{\{2\},\{3\}\}$, and $\{\{1\},\{3\}\}$ two times each. Other than this discrepancy, our answers agree.

$\endgroup$
0
$\begingroup$

Each of the n elements of set S will have 3 choices. 1.Either join subset P & don't join subset Q 2.Either join subset Q don't join subset P 3.Neither join P nor join Q.

Therefore n elements with 3 choices gives us 3^n( 3 power n).

$\endgroup$

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.