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

[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?

Homework Equations

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|!}$

 

[andrewkirk]

Your answer to (a) is correct.

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$.

 

[andrewkirk]

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$.

Yes, the set of applicants is a set of size $n$ and the set of people selected for the job is a subset of that, of size at most three.

The three questions are the same, just expressed differently.

 

[Eclair_de_XII]

Huh, thanks.