A set has 8 elements. How many subsets of S have at most 3 elements?

Question

What's the easiest way to figure this out?

Answer 1

"Easiest" is quite subjective, but here are two ways I find pretty direct:

For a subset of k elements chosen from a set containing a total of n elements, the order of listing in a subset doesn't matter, so you can think of this as a "combination" problem where picking is done without replacement (not repeating a particular element).

The formula for counting this is C(n,k) = n! / [(n-k)! k!], where n! is the factorial notation for 1,2, ..., n all multiplied together.

For instance, a subset of 3 elements from 8 total can be done in

C(8,3) = 8! / [5! 3!] = 8x7x6x5x4x3x2x1 / [5x4x3x2x1 x 3x2x1] = 8x7x6 / [3x2x1] = 8x7 = 56 ways.

If doing it by hand, I write 3X2X1 (the smaller factorial) on the bottom and "cover" it with 8 down to 6 multiplied, then cancel 6's.

Quick way on a calculator is use the factorial key and type 8! / 5! / 3! (make sure to DIVIDE by the last factorial. Even quicker way on a calculator like a TI-84 or 83 is to use the nCr key. So 8 nCr 3 results in 56.

Similarly, C(8,0) = 1 (don't forget the EMPTY subset!), C(8,1) = 8, C(8,2) = 28.

Then the total # of subsets of 3 or fewer elements from a set of 8 total elements is 1+8+28+56 = 93. //

An alternate way is to generate 9 lines of Pascal's triangle (that'll be n=0 down to n=8) and then add the first four numbers on that line (representing k=0 to k=3), which will be 1+8+28+56 = 93. //

See https://www.calculatorsoup.com/calculators/discretemathematics/pascals-triangle.php?given_data=rows&n=0&r=8&action=print&given_data_last=rows

Note that if you add all nine numbers on that line (for k=0 to k=8), the sum will be 2^8 = 256 which is the total number of subsets of all possible sizes from 8 elements, sometimes called the Power Set of the given set.

----------

If you are in a situation where n is very large and k has a big range, there is a much fancier way of speeding this up using the "sum" and "seq" commands under the List menu of a TI 83/4 calculator!

E.g., sum(seq(8 nCr x, x,0,3 gives 93. How great is that? (Some explanation in bigger example below)

How many subsets from a set of 30 elements consisting of subsets whose size is a multiple of 3 but between 14 and 25 elements each?

sum(seq(30 nCr x, x,15,25,3 gives 256511670 for the total count -- I'd rather not do that one by hand.

Filling in some steps:

seq(x,x,15,25,3 gives {15, 18, 21, 24} for the possible sizes (start with 15 since 14 is not multiple of 3)

seq(30 nCr x, x, 15,25,3) gives 155117520, 86493225, 14307150, 593775 for the counts of those sizes