1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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