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

Question #13197

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

Expert's answer

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.

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.

## Comments

## Leave a comment