# Number of combinations avoiding k consecutive elements

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?

-

## migrated from stackoverflow.comSep 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

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}$$

-
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
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.

-

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/

-