# How many subsets of size three or less are in a n-object set

• Eclair_de_XII
Eclair_de_XII

## Homework Statement

(a) How many ways can at most three people out of a selection of ##n## applicants be selected for a job?
(b) How many subsets of size at most three are there in a set of size ##n##?
(c) How many ways can a given subset of size three or fewer be chosen for the job?

## The Attempt at a Solution

(a) There are ##\sum_{i=0}^3 \binom n i## ways.
(b) Define the set of n objects as ##A##. Then define a subset ##\sigma_i=\{x\in P(A): |x|\leq 3\}##. Now define a set of integers ##J=\{i\in \mathbb{N}:\sigma_i\cap \sigma_j=∅,\sum_i |\sigma_i|=n\}##. Now define ##S_k=\cup_{j \in J} \sigma_j##, and so for a given selection of subsets, the number of subsets of at most size three is: ##\frac{n!}{\Pi_{\sigma_i\in S_k} |\sigma_i|!}##. And so the total number of possible subsets of at most size three is: ##\sum_{k=1}^{|\{\text{possible arrangements of subsets of at most three}\}|}\frac{n!}{\Pi_{\sigma_i\in S_k} |\sigma_i|!}##

Last edited:

Homework Helper
Gold Member

Do you think (b) or (c) differs from (a) other than in how they are expressed? If so, how? (Note that in none of the three cases are the subsets specified to be ordered).

Eclair_de_XII
Do you think (b) or (c) differs from (a) other than in how they are expressed? If so, how?

Well, in part (a), you're choosing one subset of at most size three to be selected for a job, while part (b) asks for how many of these possible subsets there are in the n-size set. If I had to hazard a guess, I'd say that they're both the same, in the respect that ##\binom n k## for ##k\leq 3## counts how many subsets of ##k## elements can be formed from a set of ##n## objects. So I'll take a shot in the dark and say that the answer to part (a) is the same as in part (b), or part (b)'s answer looks something like: ##\binom n k## for ##k\leq 3##.