Ordered Pairings

**DeRSeD** · October 6th 2009, 10:43 AM

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

**hans.kruger11** · October 12th 2009, 05:43 AM

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.

**Plato** · October 12th 2009, 07:26 AM

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.

**hans.kruger11** · October 12th 2009, 08:47 AM

Indeed. I guess that was a typo-error.

**Opalg** · October 12th 2009, 11:46 AM

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!)

**hans.kruger11** · October 14th 2009, 09:31 AM

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

Thread: Ordered Pairings

LinkBack

Thread Tools

Display

Ordered Pairings

Solution

Similar Math Help Forum Discussions

Number of different pairings of 2n objects.

Probability pairings

Set ordered

Marriage Pairings

Pairings problem

Search Tags