Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Combinatorics intense question!

  1. Jan 26, 2012 #1
    1. The problem statement, all variables and given/known data
    How many non- empty subsets of {1,2,3...,15} have the following two properties?
    1) No two consecutive integers belong to S.
    2)If S contains K elements, then S contains no number less than K .

    2. Relevant equations

    choosing identities, not sure which one

    3. The attempt at a solution
    Tried casework, but I dont understand how the solution gets
    n-k+1 choose k
  2. jcsd
  3. Jan 26, 2012 #2
    you said n-k+1 choose k
    what is n?
  4. Jan 26, 2012 #3
    If we have ways are there to choose k elements from an ordered n element set without choosing two consecutive members
  5. Jan 26, 2012 #4
    Okay, so what does it mean when you take a choose b?
    You're taking the number of ways to choose b items out of a, right?

    So why would you suppose the answer to your question is n-k+1 choose k?
    What is the significance of n-k+1?
  6. Jan 26, 2012 #5
    http://www.artofproblemsolving.com/Wiki/index.php/2006_AMC_12A_Problems/Problem_25 [Broken]
    I dont understand the solution
    Last edited by a moderator: May 5, 2017
  7. Jan 26, 2012 #6
    What about it do you not understand?
  8. Jan 26, 2012 #7
    Defining the boxes into n-2k+1 elements, then the general choosing statement, i get the first part, but the second part is a bit opaque
  9. Jan 27, 2012 #8
    Interesting problem! Fiddling with pencil & paper and looking for patterns suggests that for n integers, the answer involves sums of triangle numbers, T(n) = n(n+1)/2, but I don't see a good way to get there from simple combinetrics.
    Last edited: Jan 27, 2012
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook