1. Ordered Pairings

How many ordered pairs (A,B), where A,B are subsets of {1, 2, . . . , n}, are there such that |A $\cap$ B| = 1?

2. Solution

We can prove this via straightforward counting techniques and some elementary algebra. You want to first count all the A sets and then for each of those A sets you want to count all possible B sets such that their intersection comes out to be exactly equal to 1. So first we choose A set from n elements. Then we choose the element we want to be common in the both sets. Then from the remaining elements we just choose the B set. So from this we get the following summation.

$\sum_{k=1}^{n}\binom{n}{k}\cdot\binom{k}{1} \cdot 2^{n-k-1}$

$= \sum_{k=1}^{n}\frac{n!}{k!\cdot(n-k)!} \cdot k \cdot2^{n-k-1}$

$= 2^{n-1}\cdot \sum_{k=1}^{n}\frac{n!}{(k-1)!\cdot(n-k)!} \cdot2^{-k}$

$= 2^{n-1}\cdot n\cdot \sum_{k=1}^{n}\frac{(n-1)!}{(k-1)!\cdot(n-k)!} \cdot2^{-k}$

$= 2^{n-1}\cdot n\cdot \sum_{k=1}^{n}\binom{n-1}{k-1} \cdot2^{-k}$

$= 2^{n-1}\cdot n\cdot \sum_{k=0}^{n-1}\binom{n-1}{k} \cdot2^{-k}$

We can now observe that the formula for the binomial theorem can be used to simplify the summation with $a = 1 and b = \frac{1}{2}$

$= 2^{n-1}\cdot n\cdot \left( 1+\frac{1}{2} \right)^{n-1}$

$= 2^{n-1}\cdot n\cdot \left(\frac{3}{2} \right)^{n-1}$

$= n\cdot 3^{n-1}$

Hence Proved.

3. Originally Posted by hans.kruger11
We can prove this via straightforward counting techniques and some elementary algebra. You want to first count all the A sets and then for each of those A sets you want to count all possible B sets such that their intersection comes out to be exactly equal to 1. So first we choose A set from n elements. Then we choose the element we want to be common in the both sets. Then from the remaining elements we just choose the B set. So from this we get the following summation.
$\sum_{k=1}^{n}\binom{n}{k}\cdot\binom{k}{1} \cdot \color{red}2^{n-k-1}$
Surely it should be $\sum_{k=1}^{n}\binom{n}{k}\cdot\binom{k}{1} \cdot \color{blue}2^{n-k}$
In the sum what happens if $k=n$?
The A set is the whole set while the B set is a singleton. Hence there n of those.

4. Indeed. I guess that was a typo-error.

5. Originally Posted by hans.kruger11
We can prove this via straightforward counting techniques and some elementary algebra. You want to first count all the A sets and then for each of those A sets you want to count all possible B sets such that their intersection comes out to be exactly equal to 1. So first we choose A set from n elements. Then we choose the element we want to be common in the both sets. Then from the remaining elements we just choose the B set. So from this we get the following summation.

...

$= n\cdot 3^{n-1}$
Once you have seen the answer, it's easy to derive it more quickly. There are n possibilities for the one element that is in $A\cap B$. For each of the other n–1 elements, there are three possibilities: (i) the element belongs to A, (ii) the element belongs to B, (iii) the element belongs to neither A nor B. Total number of choices is therefore $n\cdot 3^{n-1}$. (I would not have noticed that without seeing hans.kruger11's solution!)

6. That is a much clearer way to put it and makes much more intuitive sense. Good work opalg