If we have a set $\{a,b,c\}$ there are going to be $8$ subsets, namely

one empty subset: $\{\emptyset\}$

$3$ subsets of size one: $\{a\},\{b\},\{c\}$

$3$ subsets of size two: $\{a, b\}, \{a, c\}, \{b, c\}$

$1$ subset of size three: $\{a,b,c\}$

now if one goes to a higher set such as $\{a,b,c,d\}$ and etc, the number of subsets increase and would follow $2^n$ subsets rule. Now I wonder if there is a mathematical pattern to group these subsets by the size of elements exist in each subset as I did in the above example.

  • $\begingroup$ Did you want the number of subsets of a given length? $\endgroup$ – mvw May 21 '18 at 10:19

Yeah sure. A number of subsets with cardinality $k$ in a set with cardinality $n$ is given by the binomial coefficient $${n\choose k} = {n!\over k!(n-k)!}$$

  • $\begingroup$ @Henning Thanks $\endgroup$ – Aqua May 21 '18 at 10:18
  • 1
    $\begingroup$ All I would add for my own answer would be some fluff about how the binomial coefficients are important in many areas of mathematics. $\endgroup$ – Henning Makholm May 21 '18 at 10:20

Pascal's triangle provides an exact answer to this. \begin{array}{rccccccc} n=0: \quad & &&& 1 = \binom{0}{0} &&& \\ n=1: \quad & && 1 = \binom{1}{0} && 1 = \binom{1}{1} && \\ n=2: \quad & & 1 = \binom{2}{0} && 2 = \binom{2}{1} && 1 = \binom{2}{2} & \\ n=3: \quad & 1 = \binom{3}{0} && 3 = \binom{3}{1} && 3 = \binom{3}{2} && 1 = \binom{3}{3} \end{array}

The $n$-th row of the triangle shows how the subsets are split up and the $n$–th row sums to $2^n$ which holds with the number of subsets.

The binomial coefficient $\binom{n}{k}$ gives the number of ways of how to draw $k$ numbers from a set of $n$ elements.

  • $\begingroup$ You can easily show this is true by considering how you are generating the subsets, e.g for a subset of size 3 you are choosing 3 elements from n etc. $\endgroup$ – Myles Mckay May 21 '18 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.