[Math] How to find the number of subsets of a specific cardinality

combinatorics

Given a set S with cardinality N, does a formula exist to calculate the number of subsets with cardinality M?

For instance, if N=5, and M=3; how many subsets are there within S with cardinality M?

Here is some extra info for each cardinality…maybe it helps.

Cardinality 0 = 1 subset
Cardinality 1 = 5 subsets
Cardinality 2 = 10 subsets
Cardinality 3 = 10 subsets
Cardinality 4 = 5 subsets
Cardinality 5 = 1 subset

So, set S contains 32 subsets total, but I just want to find the number of subsets for M.

Thanks for your insight…I thought this would be easy, but can't crack it.

Best Answer

These are the binomial coefficients: the number of $k$-element subsets of a set of size $n$ is $$n!\over k!(n-k)!,$$ or "$n\choose k$" (pronounced "$n$ choose $k$"). Here "$!$" is the factorial function.$^1$ You can derive this as follows:

  • First, we count the sequences of $k$ distinct elements of our $n$-element set. The number of these is $n\cdot (n-1)\cdot ...\cdot (n-(k-1))$ - this is an ugly expression, but it's more snappily written as $$n!\over (n-k)!$$ (do you see why?).

  • Now we need to "unorder" everything: the above is a terrible upper bound. Every set of $k$ elements can be listed in $k!$ many ways. So the actual number of sets is the number of sequences divided by the "overcounting" - that is, $${({n!\over (n-k)!})\over k!}={n!\over k!(n-k)!}.$$

As to the name, it's a good exercise to convince yourself that $n\choose k$ is the coefficient of the $x^k$ term in the expansion of $(x+1)^n$.

Incidentally, looking at the values of the binomial coefficients leads to a neat combinatorial picture - Pascal's triangle.


$^1$A convention which may seem odd at first, but is definitely the right definition: we set $0!=1$. So when $k=0$ we get $${n!\over k!(n-k)!}={n!\over 1\cdot (n-0)!}={n!\over n!}=1,$$ and similarly when $k=n$. If you think of the factorial function as being defined as "$a!$ is the number of distinct ways to order $a$ objects" (rather than "multiply all the whole numbers up to $a$") this makes sense - there's only one way to order no things.

Related Question