2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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:

  1. 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$.)
  2. 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$.
  3. 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 < 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 & 1 \\ 1 & 1 \end{pmatrix}. $$ Therefore $$ \alpha_n = \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 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 & 1 \\ \frac{1-\sqrt{5}}{2} & \frac{1+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1-\sqrt{5}}{2} & 0 \\ 0 & \frac{1+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1}{2} + \frac{\sqrt{5}}{10} & -\frac{\sqrt{5}}{5} \\ \frac{1}{2} - \frac{\sqrt{5}}{10} & \frac{\sqrt{5}}{5} \end{pmatrix}. $$ Thus $$ \begin{align*} \alpha_n &= \begin{pmatrix} \frac{3-\sqrt{5}}{2} & \frac{3+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1-\sqrt{5}}{2} & 0 \\ 0 & \frac{1+\sqrt{5}}{2} \end{pmatrix}^n \begin{pmatrix} -\frac{\sqrt{5}}{5} \\ \frac{\sqrt{5}}{5} \end{pmatrix} \\ &= \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).

$\endgroup$
7
  • $\begingroup$ This is a completely different approach of which I have never thought of. Well, this seems quite tough, I will need to brush up my Automata Theory. But I have a small doubt that u have mentioned "we recognize the Fibonacci sequence" , what does this exactly mean ? I couldn't quite comprehend on this as at any given time we will have 3 inputs n,m,k ; so how does it relate to fibonacci ?. $\endgroup$
    – Ajit
    Jun 25 '13 at 6:47
  • $\begingroup$ Here are some links where I had posted this question but it was unanswered, the comments would be useful to u. stackoverflow.com/questions/16730961/… and stackoverflow.com/questions/16730961/… $\endgroup$
    – Ajit
    Jun 25 '13 at 7:12
  • $\begingroup$ math.stackexchange.com/questions/401090/… $\endgroup$
    – Ajit
    Jun 25 '13 at 7:46
  • $\begingroup$ Ajit, I see no reason for there to be a nice formula. It might be possible to explicitly calculate a constant $c_{m,k}$ so that $\alpha_n = \Theta(c_{m,k}^n)$ (when $(m,k)=(2,1)$, $c_{m,k} = (1+\sqrt{5})/2$), but the "formula" isn't necessarily going to be nice. (There is also an off-chance that the asymptotics are different.) $\endgroup$ Jun 25 '13 at 16:52
  • $\begingroup$ Regarding the Fibonacci sequence, you can use the explicit formula for the sequence to prove that when $(m,k)=(2,1)$, $\alpha_n = F_{n+2}$. Better yet, you can come up with a combinatorial proof. All you have to do is show that $\alpha_n = \alpha_{n-1} + \alpha_{n-2}$. When $(m,k) \neq (2,1)$, you probably won't get the Fibonacci sequence, but you would get some sequence defined by a recurrence relation. $\endgroup$ Jun 25 '13 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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