Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In essence, how many unique ways can I choose a subset of N people such that there exist 3 people in the subset who are adjacent in the original set.

e.g. N = 4 Lets label the people {1,2,3,4} I can choose {1,2,3} , {2,3,4} , { 1,2,3,4} making a total of 3 ways.

Here I assume that {1,2,3} = {3,2,1} etc. are the same

Is there any general formula I can derive for calculating this?

share|improve this question
    
It seems this question has been picked up from currently running contest, which is against rules! codechef.com/SEP12/problems/CROWD Admin Please verify the same. I don't have enough reputation to comment otherwise I would have done that. :( –  rajneesh2k10 Sep 10 '12 at 16:35
    
Yes, it is based on the above mentioned problem. I was not aware that this was against math.stackexchange rules. I was just trying to find a simple way to solve this. –  varrunr Sep 10 '12 at 20:45

1 Answer 1

Let us call the number of ways of choosing a subset of N people such that there exist 3 people in the subset who are adjacent in the original set as $a_n$. Call such subsets good.

Let's try to find a recurrence for $a_n$.

Now, let us take any such subset of $N-1$ people, and consider that set with $N$ in it and not in it. Clearly both are distinct good subsets. So, this amounts to $2 a_{n-1}$ ways.

So, the elements not yet considered have $N$ in the triplet, and in fact the triplet $N-2, N-1,N$ should be the only one inside the subset, otherwise it has been calculated before. So, this amounts to $2^{n-4} - a_{n-4}$ ways, as we need the number of subsets of $N-4$ people not having any such triplet (Note that the element $N-3$ cannot be in the set).

So, we get the recurrence as $$a_{n} = 2a_{n-1} + 2^{n-4} - a_{n-4}$$ with initial conditions as $a_1=a_2=0, a_3=1, a_4=3$.

As regards to a general formula, the use of OEIS leads to this which tells us that the generating function is $$G(x) = \frac{x^3}{(1-2x)(1-x-x^2-x^3)}$$ and also gives a nicer looking recurrence: $$a_n = 3a_{n-1} - a_{n-2} - a_{n-3} - 2a_{n-4}$$

share|improve this answer
    
I am actually looking for an expression involving N and constants. –  varrunr Sep 4 '12 at 22:48
    
var, there is a standard way to go from that last recurrence to the kind of formula you want - do you know how to do this? Bear in mind that Rijul seems to be using $n$ and $N$ interchangeably. If you don't know how to solve constant-coefficient linear recurrences, follow Rijul's link to OEIS where there's a formula in terms of tribonacci, and then follow the link to a formula for tribonacci. But it really pays to learn how to solve these recurrences. –  Gerry Myerson Sep 5 '12 at 2:09
    
@GerryMyerson Yes, I can solve recurrences. I was just looking to see if there is a more straightforward solution to get a relationship with N , rather than creating a recurrence and then solving it to get N. –  varrunr Sep 5 '12 at 4:12
    
varrunr, when you get such a 4 term linear recurrence, the general formula in terms of n is often nasty and pretty difficult to work with, for example, I would rather work with the Fibonacci Recurrence than the Binet's Formula if I can avoid it. Anyway, I don't know how to get a straightforward solution to reach the Binet's Formula, which doesn't involve all this machinery. –  Rijul Saini Sep 5 '12 at 6:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.