# Homework Help: Combinatorics intense question!

1. Jan 26, 2012

### newchie

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. Jan 26, 2012

### genericusrnme

you said n-k+1 choose k
what is n?

3. Jan 26, 2012

### newchie

If we have ways are there to choose k elements from an ordered n element set without choosing two consecutive members

4. Jan 26, 2012

### genericusrnme

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?

5. Jan 26, 2012

### newchie

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
6. Jan 26, 2012

### genericusrnme

What about it do you not understand?

7. Jan 26, 2012

### newchie

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

8. Jan 27, 2012

### obafgkmrns

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