• Support PF! Buy your school textbooks, materials and every day products via PF Here!

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

1. The problem statement, all variables and given/known data
(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?

2. Relevant equations


3. 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:

andrewkirk

Science Advisor
Homework Helper
Insights Author
Gold Member
3,715
1,344
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).
 
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

Science Advisor
Homework Helper
Insights Author
Gold Member
3,715
1,344
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.
 
Huh, thanks.
 

Want to reply to this thread?

"How many subsets of size three or less are in a n-object set" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top