How many subsets can be made out of the days of the week?

Answer 1

This depends a little on what's allowed for the subsets:

(1) assuming you don't allow the EMPTY subset, the SHORT answer to your question is 2^7-1 (reads: take two to the seventh power, then subtract one) = 128-1 = 127

(2) if you DO allow the empty subset, then you simply add one to the above answer to get 128 subsets

The LONG answer is found by considering what the different subsets would look like:

> the subset(s) with ZERO days in them: {} (the empty set)

> the subset(s) with ONE day in them: {Sunday}, {Monday}, ..., {Saturday}

> the subset(s) with TWO days in them: {Sunday,Monday}, {Sunday,Tuesday},...,{Sunday,Saturday},{Monday,Tuesday},...,{Monday,Saturday}, and so on...

> ...and all the way up to the subset(s) with ALL SEVEN days in them: {Sunday,...,Saturday} (there is of course only one of these!)

Now you can take each of the above cases (zero days, one day, etc...) and treat it as a combinatorics problem:

How many ways are there to choose Y objects (days) out of a set of seven without replacement?

Answer: "7 choose Y" (you'd see this as a 7 on top of a Y and both surrounded by big parantheses...see, eg http://en.wikipedia.org/wiki/Combinatorics)

Next, add up the results for each case:

(7 choose 0) + (7 choose 1) + (7 choose 2) + ... + (7 choose 7) (this would be the instance where the ZERO day subset IS included---it's the "(7 choose 0)" term above)

NOW, the clever bit about this sum is it simplifies by the Binomial Theorem (http://en.wikipedia.org/wiki/Binomial_theorem) to just 2^7.

(If you want an intuitive way to think about it, think of a set of seven empty spots:

O O O O O O O. Each spot can have it's day of the week in it or not--for example

Sunday O O Wednesday O Friday O. In other words, EACH subset corresponds to one of these sequences where the day of the week is "ON" or "OFF" (in the above example, Sunday, Wednesday and Friday are "ON" and the other days are "OFF). The number of sequences like this is found simply by multiplying 2 to itself seven times)

Answer 2

7