Answer to Question #13197 in Combinatorics | Number Theory for Saurabh Suman

Question

How many ordered pairs (A,B), where A,B are subsets of {1,2,…5} are there, such that |A∩B|=1 ?

Answer 1

The number of subsets of X = {1,2,…5} is equal to 2^5 = 32, and so the number
of all ordered pairs (A,B) of subsets
of X is 32*31/2 = 16*31 =
992.

We should count only pairs (A,B) with |A∩B|=1.
For each such pair
the sets
A \ {1} and B \ {1}
are disjoint, therefore we sould
compute the number of ordered pairs
(C,D) of subsets of the set {2,3,4,5}
such that C and D are disjoint.

Dentoe by |C| the number of elements in
C.

Say that the pair (C,D) is of type (a,b) if
|C|=a and
|D|=b

In thsi case we have that 0 <= a+b <= 4

Let P(a,b)
be the number of (a,b) pairs.
Evidently, P(a,b)=P(b,a).

Consider the
cases.

(0,0). There is only one (0,0)-pair: (empty_set, empty_set),
so
P(0,0)=1


(0,1). There are four (0,1)-pairs:

(empty_set, 2), (empty_set, 3), (empty_set, 4), (empty_set,
5)
so
P(0,1) = P(1,0) = 4


(0,2). The number of
(0,2)-pairs is the same as the number of all 2-elements subsets of {2,3,4,5},
i.e. binomial
coefficient C_4^2
so
P(0,2) = P(2,0) =
C_4^2 = 4*3/2 = 6


(0,3). Similarly, the number of (0,3)-pairs is the
same as the number of all 3-elements subsets of {2,3,4,5}, i.e.

binomial coefficient C_4^3
so
P(0,3) = P(3,0) = C_4^3 =
4


(0,4). There is only one (0,4)-pair: (empty_set, {2,3,4,5}),
so
P(0,4)=P(4,0)=1


(1,1). The number of (1,1)-pairs is the
same as the number of all ordered 2-elements subsets of
{2,3,4,5},
so
P(1,1) = 4 * 3 = 12


(1,2). Each (1,2)-pair
is determined by a choice of one element from four, and then choice of two
elements from
remaining three,
so
P(1,2) = P(2,1) = C^1_4 *
C^2_3 = 4 * 3 = 12

(1,3). Each (1,3)-pair is determined by a choice of
one element from four, then the remaining three are uniquely
defined,
so
P(1,3) = P(3,1) = 4


(2,2). Each (2,2)-pair is determined
by a choice of two elements from four, then the remaining two are uniquely
defined,
so
P(2,2) = C^2_4 = 6


Thus the number of all of
ordered pairs (C,D) of mutually disjoint subsets of {2,3,4,5} is

1 + 4 +
6 + 4 + 1 + 12 + 12 + 4 + 6 = 50.


Hence the number of ordered pairs
(A,B), where A,B are subsets of {1,2,…5} are there, such that |A∩B|=1
is
also 50.