Question

f(n,r) is the number of ways of selecting r integers from the prdered set {1,2,...,n} so that consecutive integers are not selected.determine the recurrence relations. :)

Answer 1

ordered*

Answer 2

I;m going to look something up....give me a sec...

Answer 3

Do you know what f(n,r) is exactly?

Answer 4

no. :(

Answer 5

for each n we need to find f(n,r) as a function of r
correct?

Answer 6

Would you count the case of f(n,0)?

Answer 7

i guess not. because the set does not contain 0?

Answer 8

No what I mean is f(n,0) would be the number of ways of selecting 0 integers (so that the conditions are met) from a set of n.
example: 1 choose 0 = 1 so f(1,0) = 1

Answer 9

yes. :)) it is included.

Answer 10

I tried a couple small cases and found:
n=1: f(1,0) = 1
f(1,1) = 1

n=2: f(2,0) = 1
f(2,1) = 2
f(2,2) = 0

n=3: f(3,0) = 1
f(3,1) = 3
f(3,2) = 2
f(3,3) = 0

Answer 11

our professor told us that we may use iteration. either backward or forward.

Answer 12

n=4: f(4,0) = 1
f(4,1) = 4
f(4,2) = 6
f(4,3) = 4
f(4,4) = 3

see the pdf for what I counting: I used SAGE to list the possible ordered sets, then went through and counted how many would fit the condition.

Kinda looks like the binomial coefficients, except that last number f(n,n)

Answer 13

Wait, sorry, f(4,4) = 2 not 3

Answer 14

i think f(n,n)= 1
f(n,n)= n!/n! which is equals to one? ryt?

Answer 15

Ok I went through and circled in red the ones that worked, and marked out in blue the ones that didn't.
n=4: f(4,0) = 1
f(4,1) = 4
f(4,2) = 6
f(4,3) = 5
f(4,4) = 2

And I got to start getting ready for work :(

If you want to use SAGE to compute some of the cases for higher values of n check out http://www.sagemath.org/
select "try sage online" and set up a free account. Then start a new worksheet.

Answer 16

thanks. :)

Answer 17

If you are still working on this, I misinterpreted the problem :(

The statement "so that consecutive integers are not selected" means that I over counted! For example the when n = 4 and r = 2 the set [3,1,4] would not be a "good" set since 3 and 4 appear in the set.

Also, the word "ordered" through me off. Did you mean that the set {1,2,3,...,n} was ordered, or that order should be considered when counting subsets. For example "without regard to order" means that [1,3,5] = [1,5,3]. But with regards to order would mean [1,3,5] and [1,5,3] are two different sets. That really changes things!

I did find a similar problem in one of my favorite books, "Mathematics of Choice" by Ivan Niven. Here is how he phrases the problem:

Consider the integers 1,2,3,...,n Let K(n,j) denote the number of subsets of these n integers satisfying the conditions (i) each subset contains j integers, (ii) no subset contains a consecutive pair of integers. For example K(5,3)=1 because the only subset of 1,2,3,4,5 satisfying the conditions is 1,3,5 (notice that order is not considered). By separating the subsets counted by K(n,j) into two types, those that contain n and those that do not, obtain a recursion relation for K(n,j).

It goes on to give a hint about making a table of values of K(n,j) and comparing it to Pascal's triangle. The prove your conjecture using induction.

Answer 18

Yep, the hint is a good one! The recursion relation is that f(n,r) = f(n-2,r-1)+f(n-1,r)

Answer 19

so how can i show the recursion relation? :))