Results 1 to 4 of 4

Math Help - Combinatorics concept

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by oldguynewstudent View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by oldguynewstudent View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The concept behind sin(π/2-Φ)=cos(Φ)
    Posted in the Trigonometry Forum
    Replies: 11
    Last Post: July 30th 2013, 03:59 AM
  2. Concept of average
    Posted in the Statistics Forum
    Replies: 5
    Last Post: September 2nd 2011, 06:56 PM
  3. help on a concept
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 7th 2010, 05:56 PM
  4. calc3 concept
    Posted in the Calculus Forum
    Replies: 1
    Last Post: June 10th 2008, 11:25 PM
  5. need to get the concept down...
    Posted in the Calculus Forum
    Replies: 8
    Last Post: November 17th 2007, 09:23 PM

Search Tags


/mathhelpforum @mathhelpforum