Pre-interview_Test_Question_49

define S=\{1,2,3,\ldots,n\}
if a subset of size r contains 1, then you have to choose r-1 numbers that aren’t 1, one for each of the remaining r-1 places. you have also used up the element 1 from S, so you only have n-1 left to choose from.
so if the subset of size r contains 1 then there are \dbinom{n-1}{r-1} possibilities for it.
if a subset of size r definitely does not contain a 1 then you have all elements of S barring 1, ie. n-1 elements to choose from, for all r places.
so if the subset of size r doesn’t contain 1 then there are \dbinom{n-1}{r} possibilities for it.
because any arbitrary subset either has 1 in it or doesn’t, the sum of these separate possibilities will give the total number of subsets of size r, which by the stem is \dbinom{n}{r}
(note: the above result is known as pascal’s rule)
for the second part, i can think of 2 methods.

  1. the “similar” one would involve considering the 4 possibilities separately that arise from a subset containing, or not, 1 and/or 2 WLOG (you can do this with any 2 such numbers in S)
    if a subset of size r contains both 1 and 2 then you have to choose r-2 numbers that are neither 1 nor 2, one for each of the remaining r-2 places. you have also used up both the elements 1 and 2 from S, so you only have n-2 left to choose from.
    so if both are contained then there are \dbinom{n-2}{r-2} such possibilities.
    if a subset of size r contains exactly one out of 1 and 2 then in either case you have to choose r-1 numbers from S that are not the already contained number for each of the r-1 remaining places. in either case you also have used up one of the numbers, and the other is not contained in the subset so you have n-2 elements from S to choose from. crucially, notice how fixing either of 1 or 2 follows the exact same process as detailed above. this means that you can calculate the possibilities for either one of the cases and then simply double the result.
    so if exactly one out of 1 or 2 is in the subset, there are 2\dbinom{n-2}{r-1} possibilities.
    if a subset of size r contains neither of 1 or 2 then you have to choose r numbers that are neither 1 nor 2, one for each of the r places. you also cannot have the elements 1 and 2 from S in the subset, so you only have n-2 left to choose from.
    so if the subset contains neither of 1 or 2, then there are \dbinom{n-2}{r} possibilities.
    because any subset has to satisfy exactly any one of these rules, the sum of the possibilities will give the total number of subsets there are, which is \dbinom{n}{r}
  2. for the easier but not similar one just use pascal’s rule multiple times
    we have that
\begin{align} \binom{(n-1)-1}{(r-1)-1}+\binom{(n-1)-1}{r-1}&=\binom{n-1}{r-1} \\ \implies \binom{n-2}{r-2}+\binom{n-2}{r-1}&=\binom{n-1}{r-1} \end{align}

and that

\begin{align} \binom{(n-1)-1}{r-1}+\binom{(n-1)-1}{r}&=\binom{n-1}{r} \\ \implies \binom{n-2}{r-1}+\binom{n-2}{r}&=\binom{n-1}{r} \end{align}

combining these facts:

\begin{align} \binom{n-2}{r-1}+\binom{n-2}{r}+\binom{n-2}{r-2}+\binom{n-2}{r-1}&=\binom{n-1}{r}+\binom{n-1}{r-1} \\ &=\binom{n}{r} \end{align}

by pascal’s rule/initial result again.

2 Likes