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.

I had come across this problem. Consider the list of numbers from 1 to 100. How to find the number of combinations, such that no combination has k consecutive elements? (k is any constant, it can be 3 or 4 or any other number) Could anyone please help me with this?

share|improve this question

migrated from stackoverflow.com Sep 6 '12 at 19:33

This question came from our site for professional and enthusiast programmers.

    
Combination of what length (without this restriction, there are infinite number of those if number of elements >= 3)? Or is it Permutation? –  amit Sep 6 '12 at 19:32
    
length is 100 as the numbers are from 1 to 100. I was looking at an approach. If that is too large then consider the numbers to be between 1 to 30 –  John Smith Sep 6 '12 at 19:47
    
I want to make sure we are talking about combinations and not permutations. Is 135135 valid? –  amit Sep 6 '12 at 19:48

3 Answers 3

up vote 1 down vote accepted

The answer must be written up somewhere, but here is how to start. We'll do $k=4$ to be specific, then show how to extend it to any $k$. Let $F(n,4)$ be the number of combinations out of $[1,n]$ without $4$ consecutive elements. Divide those with $n$ from those without $n$. There are $F(n-1,k)$ combinations without $n$. If $n$ is present, think of those without $n-1$. There are $F(n-2,4)$ of those. If both $n$ and $n-1$ are present, think of those without $n-2$. There are $F(n-3,4)$ of those. Finally, if $n-2, n-1, n$ are all present, $n-3$ cannot be, so there are $F(n-4,4)$ with $n-2, n-1, n$. The recurrence is then $F(n,4)=F(n-1,4)+F(n-2,4)+F(n-3,4)+F(n-3,4)+F(n-4,4)$. The starting values are $F(0,4)=1,F(1,4)=2,F(2,4)=4,F(3,4)=8$ because all the subsets do not have four in a row. Similarly for general $k$ we have $$F(n,k)=\begin {cases} 2^n & n\lt k \\ \sum_{i=1}^k F(n-i,k) & n \ge k\end {cases} $$

share|improve this answer
    
The recurrence $F(n) = F(n-1) + \ldots + F(n-k)$ has basic solutions $r^n$ where $r$ is any root of the polynomial $p_k(x) = x^k - x^{k-1} - \ldots - 1$. I think all of these are irreducible. For large $k$ it appears that there are $k-1$ roots near the unit circle and one very close to $2$. –  Robert Israel Sep 6 '12 at 20:17
    
Yes, "one very close to 2" of course is just a translation of the fact that long streaks of "heads" are rare when tossing coins. –  Hagen von Eitzen Sep 6 '12 at 20:26
    
The number $F(n,k)$ of subsets of $\{1,\ldots,n\}$ with no $k$ consecutive members is also the number of $n$-letter binary words with no $k$ consecutive $1$'s. Note that if you extend the recursion backwards, $F(n,k) = 0$ for $n=-k, \ldots, -1$. Thus $F(n,k) = G(n+k,k)$ where $G(j,k)$ are the "$k$-step Fibonacci numbers". –  Robert Israel Sep 6 '12 at 20:37
1  
See e.g. mathworld.wolfram.com/Fibonaccin-StepNumber.html and references there. –  Robert Israel Sep 6 '12 at 20:38
    
@HagenvonEitzen: Or that almost all subsets of $[1,n]$ have close to $\frac n2$ members. Among these, few will have a run of $k$. Almost all subsets will count, so we should get close to $2^n$ –  Ross Millikan Sep 6 '12 at 20:38

You have this under algorithms. So, I suspect that you might be looking for an easy way to handle problems when working with the binomial coefficient. If true, then please see this stackoverflow link to my answer on a problem working with the binomial coefficient that involves a paper I wrote and a class that handles problems using the binomial coefficient. My class would not work for a list size of 100 because the numbers are too large and even if the class could be modified to handle numbers that large, it would take forever to finish. You would need a mathematical approach as suggested by Ross Millikan in that case. For a list size of 30, it should work and could also perform other types of processing, which is what I suspect you are trying to do.

share|improve this answer

Think recursively.

If you have the number of such combinations for $n-1$. Then for $k = 3$

if you include $a_n$ then you count the number of such combinations for $a_n-2$.

if you include $a_n$ and $a_n-1$ then you count the number of such combinations for $a_n-3$

if you do not include $a_n$ then you count the combinations for $a_n-1$.

therefor $A_n = A_{n-1} + A_{n-2} + A_{n-3}$ and so on. I think this can be easily generalised.

Computationally this can be done in $O(\log n)$ time for $n$. you need to solve this linear recursion. http://fusharblog.com/solving-linear-recurrence-for-programming-contest-part-2/

share|improve this answer

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.