MandysNotes

Saturday, 08 March 2014 01:31

Binomial Coefficients and Subsets

By  Gideon
Rate this item
(0 votes)


For a finite set  \(S\) with \(n\) elements, the total number of subsets of \(S\) with \(k\) elements

\[ ( 0 \leq k \leq n) \]

is

\[ \binom{n}{k}.\]


For example, if you have a set of three balls, there is \(\binom{3}{3} = 1\) set with all three balls; there are \(\binom{3}{2} = 3\) sets of two balls; there are \(\binom{3}{1} = 3\) sets of one ball each; and there is \(\binom{3}{0} = 1\) set with zero balls (the empty set).

As another example, if there are six people in a room, and if each person must shake hands with each other person, then there must be \(\binom{6}{2} = 15\) total handshakes. (In other words, in a set with six members, there are 15 possible combinations of two of the members).


Note that in these cases, unlike the situation when we looked at total permutations, we do not care about the order in which the elements of the sets appear.

So, for instance, if we are drawing balls at random out of a bag filled with three balls, then there are three possible sets of two balls that we could obtain by pulling out first one ball and then a second. But in this case we don't care which is first and which is second. So if we pull out a red ball and a blue ball we consider this to be \emph{one set} \(\{\text{blue}, \text{red} \}\), irrespective of whether we pulled the red ball or the blue ball out first.

Proof:

First, we know that for a set of \(n\) elements there are \(n!\) possible permutations. We also saw in the proof of Claim \ref{C:factcom} that in a set of \(n\) elements there are \(n(n-1)(n-2)...(n-k + 1)\) sequences of length \(k\).(E.g. there were (10)(9)(8) slideshows of length three pictures drawn from a set of ten pictures).

Therefore the total number of sequences of length \(k\), made from a set of \(n\) elements is \( \frac{n!}{(n-k)!}\). But this number counts each sequence separately, whereas we only want the total number of sets, independent of order. Each set of \(k\) objects has \(k!\) possible permutations, therefore the number of sets with \(k\) members chosen from a set of \(n\) elements equals:

\[ \frac{\text{number of sequences of length \(k\) chosen from \(n\) elements}}{\text{number of permutations of \(k\) elements}} \]
\[ = \frac{ \frac{n!}{(n-k)!}}{k!} = \frac{n!}{(n-k)!k!} = \binom{n}{k} \]

 

Read 1489 times Last modified on Saturday, 08 March 2014 03:10
More in this category: « The Factorial
Login to post comments

NOTRad