Discrete Math Combinatorics Sets and Subsets. Can someone please explain why the following question's answer is (a)? Let S be a set of size 37, and let x and y be two distinct elements of S. How many subsets of S are there that contain x but do not contain y?

ezelsbankuk

ezelsbankuk

Answered question

2022-09-04

Discrete Math Combinatorics Sets and Subsets
Can someone please explain why the following question's answer is (a)?
Let S be a set of size 37, and let x and y be two distinct elements of S. How many subsets of S are there that contain x but do not contain y?
(a) 2 35
(b) 2 36
(c) 2 37 2 35
(d) 2 35 + 2 36

Answer & Explanation

Gerardo Kent

Gerardo Kent

Beginner2022-09-05Added 12 answers

Step 1
There are 2 | S { x , y } | = 2 35 subsets of S∖{x,y}.
Step 2
We add x to each of them to obtain the 2 35 subsets of S that contain x but don't contain y.
Illuddybopylu

Illuddybopylu

Beginner2022-09-06Added 17 answers

Step 1
Think of it this way: Let S = { s 1 , s 2 , , s 37 } . Every subset A S can be identified by a sequence
( a 1 , a 2 , , a 37 )   ,   a i { 0 , 1 } .
Step 2
in the way that a i = 1 if s i A and a i = 0 if s i A. Now you know that x is some s m and y is some s n . If x is in A and y isn't, this means that a m = 1 and a n = 0. However, every other a i can be either 0 or 1. Since there are 35 other a i 's left, you are looking for the number of sequences of length 35 using only the symbols 0 and 1. This is
2 2 2 2 35  times = 2 35
because at every position you have 2 symbols to choose from.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?