3
$\begingroup$

So I know that the combinatorial explanation is has following:
let there be 2 group A= x is chosen (${n-1\choose {k-1}}$) and B=x is not chosen (${n-1\choose k}$)
so $A\cup B= |A|+|B|$ therefore:
${n \choose k}={n-1\choose {k-1}}+{n-1\choose k}$

so I took n=4, k=2, x=4 so:
${n-1\choose {k-1}}$=${3\choose {1}}$= {1},{2},{3},{4}
${n-1\choose k}$=${3\choose 2}$= {1,2},{2,3},{3,1}
adding those groups is {1,2},{1,2,3},{2,3,1},{1,2,4},{2,3,4},{3,1,4}

the number adds up to ${4\choose 2}$ but the sum is not disjoint, and the groups are of 2 and 3 elements

$\endgroup$
1
  • 1
    $\begingroup$ The first bunch should be $\{1,4\}$, $\{2,4\}$, $\{3,4\}$. $\endgroup$
    – André Nicolas
    Commented Jun 19, 2014 at 15:40

2 Answers 2

Reset to default
2
$\begingroup$

In your line for $3 \choose 1$ you shouldn't have $\{4\}$. Then when you add the groups, the ones coming from the second line should not get the $4$ added. You should then get $\{1,4\},\{2,4\},\{3,4\},\{1,2\},\{2,3\},\{1,3\}$ which are disjoint and all of size $2$

$\endgroup$
7
  • $\begingroup$ but $3\choose 1$ is where we choose 4 no? $\endgroup$
    – gbox
    Commented Jun 19, 2014 at 15:48
  • 1
    $\begingroup$ But you are starting with selections of one item from $\{1,2,3\}$ and adding a $4$ to them. Alternately you could write ${3 \choose 1}=\{1,4\},\{2,4\},\{3,4\}$ In any case there should be just three of them. $\endgroup$
    – Ross Millikan
    Commented Jun 19, 2014 at 15:51
  • $\begingroup$ got it and as for the disjoint {1,4}$\cap${1,2}={1}? $\endgroup$
    – gbox
    Commented Jun 19, 2014 at 15:53
  • 1
    $\begingroup$ There is no need that the individual sets be disjoint. The need is that the elements of $\{\{1,4\},\{2,4\},\{3,4\}\}$ and $\{\{1,2\},\{2,3\},\{1,3\}\}$ be disjoint-that none of the two element sets is counted twice. We have that. Certainly with four elements, you can't have six disjoint sets made out of them. $\endgroup$
    – Ross Millikan
    Commented Jun 19, 2014 at 16:25
  • $\begingroup$ thanks! so what you are basically saying is that Inclusion–exclusion principle is just when they intersection as the same cardinality as A or B? $\endgroup$
    – gbox
    Commented Jun 19, 2014 at 16:29
2
$\begingroup$

Given $n$ people we can form a committee of size $k$ in ${n\choose k}$ ways. We can count the same thing by counting the number of ways in which person $x$ is in the committee and person $x$ is not in the committee. The number of ways person $x$ is not in the committee is ${n-1\choose k}$. We have $n-1$ people to work with because we are excluding the possibility of person $x$ being in the committee. The number of ways person $x$ is in the committee is ${n-1\choose k-1}$. We have $n-1$ people to work with since person $x$ is in the committee by default and we choose $k-1$ people because person $x$ is in the committee. Thus ${n\choose k}={n-1\choose k}+{n-1\choose k-1}$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .