${n\choose 2} - {k\choose 2} = {n-k\choose 2} +k(n-k)$ Marked box or unmarked box

202 Views Asked by At

${n\choose 2}$ counts the 2-combination $(a,b)$ where

  1. $a\,\in\,\{\text{Set with n-k elements}\}\,b\,\in\,\{\text{Set with n-k elements}\}$
  2. $a\,\in\,\{\text{Set with n-k elements}\}\,b\,\in\,\{\text{Set with k elements}\}$ Order trivial here?
  3. $a\,\in\,\{\text{Set with k elements}\}\,b\,\in\,\{\text{Set with k elements}\}$

${k\choose 2}$ counts the 2-combination $(a,b)$ where

  1. $a\,\in\,\{\text{Set with k elements}\}\,b\,\in\,\{\text{Set with k elements}\}$

${n-k\choose 2}$ counts the 2-combination $(a,b)$ where

  1. $a\,\in\,\{\text{Set with n-k elements}\}\,b\,\in\,\{\text{Set with n-k elements}\}$

$k(n-k)$ counts the 2-combination $(a,b)$ where

  1. $a\,\in\,\{\text{Set with n-k elements}\}\,b\,\in\,\{\text{Set with k elements}\}$
  2. First question, is that because the order is trivial, either $k(n-k)$ or $(n-k)k$ would suffice?
  3. Second question, under what circumstances will both $k(n-k)$ and $(n-k)k$ have to be counted?
1

There are 1 best solutions below

0
On BEST ANSWER

Maybe it is clearer as $$\binom{n}{2}=\binom{k}{2}+\binom{n-k}{2}+k(n-k),$$ which you can prove combinatorially as follows. The LHS counts the number of 2-subsets $\{a,b\}$ (with $a<b$) of $\{1,\dots,n\}$. The RHS counts the same objects according to three mutually exclusive cases:

  1. $\{a,b\} \subset \{1,\dots,k\}$
  2. $\{a,b\} \subset \{k+1,\dots,n\}$
  3. $a\in \{1,\dots,k\}$ and $b \in\{k+1,\dots,n\}$

Because $a < b$, these are the only possibilities.