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 $\displaystyle 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 $\displaystyle 2^3$.

This is the formula for counting k-element lists taken from an n-element set or $\displaystyle 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*?