Thread: 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 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 .

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

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?

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 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 .

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

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 solutions

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 where k=10.

Here is another way to see this.
Let , so .
Now the power set contains sets.
If then is a set with a smallest element 4 and the largest element 15.
There are of those sets.

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!