Combination with a minimum number of elements in a fixed length subset I have been searching for long but unable to find a solution for this. My question is "Suppose you have n street lights(cannot be moved) and if you get any m from them then it should have atleast k working.Now in how many ways can this be done"

This seems to be a combination problem, but the problem here is "m" must be sequential.

Eg: 1 2 3 4 5 6 7 (Street lamps) 
Let m=3 
Then the valid sets are,
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7

Whereas, 1 2 4 and so are invalid selections.

So every set must have atleast 2 working lights. I have figured how to find the minimum lamps required to satisfy the condition but how can I find the number of ways in it can be done ?

There should certainly some formula to do this but I am unable to find it.. :(

Eg: Let n=7,m=4,k=3. The minimum number of lights that must be working to satisfy the condition that "atleast 3 of any 4 lights must be working" is 5. It is if 23467 are working. But there are more ways in which it can be satisfied like if 23467,13457... We have 4 such combinations in all for the taken values of n,m,k. I want to know how can we generalize this?

Can be represented like this :
n => 1111111
1 Indicates light working and 0 indicated not working.
0111110
0111011
1011101
1011110

Hope the question is clear.
For each particular $m,k$ you can get a recurrence formula and solve it. Perhaps this way you can obtain a general formula. Here is how to find the recurrence formula:


The language of all valid sequence is regular. Construct a DFA (deterministic finite automaton) that accepts the language. (An optimization: construct a "partial" DFA in which sometimes there is no outgoing edge labeled $0$.)
Suppose the transition matrix is $A$, the initial state is $s$, and the accepting states are $F$. Then the number of sequences of length $n$ is $\alpha_n = 1_F A^n 1_s$.
Compute the Jordan normal form of $A$, decompose $1_F,1_s$ according to the Jordan basis, and so obtain a formula for $\alpha_n$.


Instead of using DFAs, you can use generating functions, which really amounts to the same.

Here is a very simple example: $m = 2$ and $k = 1$. The regular language here is all words not containing $00$, that is $1^*(10)^*1^*$. The minimal partial DFA has two states $s_0,s_1$ which correspond to the two possible "histories" (we can assume that the part of the sequence before it actually starts consists entirely of 1s) - in general there will be $2^{m-1}$ states (if $k &lt; m-1$ then actually less, since some of them would be invalid). The transitions are: On $0$, transition from $s_1$ to $s_0$; On $1$, transition from $s_0,s_1$ to $s_1$. The starting state is $s_1$. All states are accepting (this will always be the case with a minimal partial DFA). The transition matrix is
$$ A = \begin{pmatrix} 0 &amp; 1 \\ 1 &amp; 1 \end{pmatrix}. $$
Therefore
$$ \alpha_n = \begin{pmatrix} 1 &amp; 1 \end{pmatrix} \begin{pmatrix} 0 &amp; 1 \\ 1 &amp; 1 \end{pmatrix}^n \begin{pmatrix} 0 \\ 1 \end{pmatrix}. $$
The matrix $A$ has two eigenvalues $(1 \pm \sqrt{5})/2$, and furthermore
$$ A = \begin{pmatrix} 1 &amp; 1 \\ \frac{1-\sqrt{5}}{2} &amp; \frac{1+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1-\sqrt{5}}{2} &amp; 0 \\ 0 &amp; \frac{1+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1}{2} + \frac{\sqrt{5}}{10} &amp; -\frac{\sqrt{5}}{5} \\ \frac{1}{2} - \frac{\sqrt{5}}{10} &amp; \frac{\sqrt{5}}{5} \end{pmatrix}. $$
Thus
$$
\begin{align*}
\alpha_n &amp;= \begin{pmatrix} \frac{3-\sqrt{5}}{2} &amp; \frac{3+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1-\sqrt{5}}{2} &amp; 0 \\ 0 &amp; \frac{1+\sqrt{5}}{2} \end{pmatrix}^n \begin{pmatrix} -\frac{\sqrt{5}}{5} \\ \frac{\sqrt{5}}{5} \end{pmatrix} \\ &amp;=
\frac{5-3\sqrt{5}}{10} \left( \frac{1-\sqrt{5}}{2} \right)^n +
\frac{5+3\sqrt{5}}{10} \left( \frac{1+\sqrt{5}}{2} \right)^n.
\end{align*}
$$
The first few numbers (starting with $\alpha_0$) are $1,2,3,5,8,13,\ldots$, and we recognize the Fibonacci sequence: $\alpha_n = F_{n+2}$.



An alternative to following these steps is noticing that $\alpha_n$ is always defined by a recurrence relation of length at most $2^{m-1}$. So for general $m,k$, all you have to do is calculate enough of the sequence $\alpha_n$ to determine the coefficients: you need to calculate $\alpha_0,\ldots,\alpha_{2^m-1}$, which will give you $2^{m-1}$ equations.

Here is how to do it for $(m,k) = (2,1)$: $\alpha = 1,2,3,5$. If $\alpha_n = c_1 \alpha_{n-1} + c_2 \alpha_{n-2}$ then $3 = 2c_1 + c_2$ and $5 = 3c_1 + 2c_2$. We deduce that $c_1 = c_2 = 1$ and so the recurrence is $\alpha_n = \alpha_{n-1} + \alpha_{n-2}$.

Having recovered the recurrence relation, we solve it as usual. It will usually be the case that all roots of the characteristic polynomial are distinct, and that the asymptotics of the sequence are given by the largest root (though in principle it depends on the actual sequence).