0
$\begingroup$

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?

  • 0
    I want to make sure we are talking about *combinations* and not *permutations*. Is `135135` valid?2012-09-06

3 Answers 3

1

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

  • 0
    @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$2012-09-06
1

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.

0

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/