# Combinatorics concept

• Apr 24th 2010, 09:41 AM
oldguynewstudent
Combinatorics concept
Hello, I'm back and this summer it's combinatorics.
So, I understand how to get the answer, but I don't understand why this works.

How many subsets of [20] have the smallest element 4 and the largest element 15?

Answer is $2^k$ where k=10.

Let's look at a smaller problem of smallest number 4 and largest 8. Here are the possible subsets {4,8} {4,5,8} {4,6,8} {4,7,8} {4,5,6,8} {4,5,7,8} {4,6,7,8} {4,5,6,7,8} which total 8 subsets or $2^3$.

This is the formula for counting k-element lists taken from an n-element set or $n^k$.

The k comes from the 3 elements between 4 and 8 but where does the 2 come from?

Also with lists repetition is normally allowed.

I see how this works but according to the definitions in my book (which seems to be great by the way, Combinatorics A Guided Tour by David R. Mazur) this doesn't seem to fit a k-element list taken from an n-element set. Understanding which formula to use in which situation seems to be more important than memorizing the formula.

Can someone help me with this concept?
• Apr 24th 2010, 09:54 AM
Quote:

Originally Posted by oldguynewstudent
Hello, I'm back and this summer it's combinatorics.
So, I understand how to get the answer, but I don't understand why this works.

How many subsets of [20] have the smallest element 4 and the largest element 15?

Answer is $2^k$ where k=10.

Let's look at a smaller problem of smallest number 4 and largest 8. Here are the possible subsets {4,8} {4,5,8} {4,6,8} {4,7,8} {4,5,6,8} {4,5,7,8} {4,6,7,8} {4,5,6,7,8} which total 8 subsets or $2^3$.

This is the formula for counting k-element lists taken from an n-element set or $n^k$.

The k comes from the 3 elements between 4 and 8 but where does the 2 come from?

Also with lists repetition is normally allowed.

I see how this works but according to the definitions in my book (which seems to be great by the way, Combinatorics A Guided Tour by David R. Mazur) this doesn't seem to fit a k-element list taken from an n-element set. Understanding which formula to use in which situation seems to be more important than memorizing the formula.

Can someone help me with this concept?

In this case, as you bring in one new element, you end up doubling the number of solutions

{4,20} 1 solution

bring in 5

{4,20}, {4,5,20} 2 solutions

bring in 6

{4,20}, {4,5,20}, {4,6,20}, {4,5,6,20} 4 solutions

bring in 7

{4,20}, {4,5,20}, {4,6,20}, {4,5,6,20}, {4,7,20}, {4,5,7,20}, {4,6,7,20}, {4,5,6,7,20} 8 solutions

and continue

Hence are there are 10 elements between 4 and 15, there are $2^{10}$ solutions
• Apr 24th 2010, 10:22 AM
Plato
Quote:

Originally Posted by oldguynewstudent
So, I understand how to get the answer, but I don't understand why this works.
How many subsets of [20] have the smallest element 4 and the largest element 15? Answer is $2^k$ where k=10.

Here is another way to see this.
Let $\mathcal{L}=\left\{ {5,6,7, \cdots ,14} \right\}$, so $| \mathcal{L} |=10$.
Now the power set $\mathbb{P}(\mathcal{L} )$ contains $2^{10}$ sets.
If $A\in\mathbb{P}(\mathcal{L} )$ then $A\cup \{4,15\}$ is a set with a smallest element 4 and the largest element 15.
There are $2^{10}$ of those sets.
• Apr 24th 2010, 02:02 PM
oldguynewstudent
Thanks
Thanks Plato, those two views make things much clearer. I'm trying to get a jump on my summer courses. I've got two condensed math courses this summer. But I've met my professor and he seems very good and the book seems good also. As always you guys rock!