Combinations
Counting Subsets
Our next problem is counting subsets of a given size chosen from a set of a given size.
Question: How many different \(k\) element subsets does a set with \(n\) elements have?
Theorem on counting subsets
Proposition: The number of \(k\) element subsets of a set with \(n\) elements is called \(\binom{n}{k}\). This number is read “\(n\) choose \(k\)” and it is called a “binomial coefficient”. The formula for \(\binom{n}{k}\) is: \[ \binom{n}{k}=\frac{n!}{(n-k)!k!} \]
Proof: First we give the book’s proof.
Proof: now we give a proof by strong induction.
Examples
Problem 2, page 89: If a set has \(100\) elements, how many subsets of \(A\) have \(5\) elements? How many have \(10\) elements? How many have \(99\) elements?
Problem 5, page 89: How many \(16\) digit binary strings contain exactly seven \(1\)’s?
Problem 11, page 89: How many positive 10 digit integers contain no zeros and exactly three 6’s?
Problem 19, page 89: A 5-card poker hand is called a flush if all cards are the same suit. How many different flushes are there?