GateAI
Discrete Mathematics

GATE CSE 2021 Set 2 · Q50

NAT2 marksEasy

Time

Let SS be a set consisting of 10 elements. The number of tuples of the form (A,B)(A, B) such that AA and BB are subsets of SS, and A⊆BA \subseteq B is __________.

Your answerNumerical answer

Enter a value to check

Solution

Step-by-step verified solution

Official answer: 59049

Discrete Mathematics

To form an ordered pair of subsets (A,B)(A, B) of SS such that A⊆BA \subseteq B, we consider the placement of each element x∈Sx \in S.

For each element x∈Sx \in S, there are 3 mutually exclusive and exhaustive choices:

  1. x∈Ax \in A and x∈Bx \in B

  2. x∉Ax \notin A and x∈Bx \in B

  3. x∉Ax \notin A and x∉Bx \notin B

(The case where x∈Ax \in A and x∉Bx \notin B is not allowed because A⊆BA \subseteq B.)

Since ∣S∣=10|S| = 10, each of the 10 elements has 3 independent choices.

Total number of tuples (A,B)=310=59049\text{Total number of tuples } (A, B) = 3^{10} = 59049

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Discrete Mathematics previous year question is Q50 of the GATE CSE 2021 Set 2 paper. Find more GATE CSE PYQs on Discrete Mathematics in Engineering Mathematics, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Discrete Mathematics PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Discrete Mathematics in GATE CSE

Discrete Mathematics has 50 GATE CSE PYQs across 23 papers from 2011 to 2026. 6 of them are 2-mark NAT questions like this one, and it is the only one in GATE CSE 2021 Set 2.

How GATE tests Discrete Mathematics

More from GATE CSE 2021 Set 2

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2021 Set 2 · Q50 · NAT

Let S be a set consisting of 10 elements. The number of tuples of the form (A, B) such that A and B are subsets of S, and A ⊆ B is …

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.