4
$\begingroup$

I have N number of days where three different events X,Y,Z can occur in each day. A is a set of possible occurrences of length N. I want to calculate the number of ways where:

  1. Y does NOT happen twice or more in these number of days N
  2. X does NOT happen three times consecutively in these number of days N

So, one acceptable way where N=5 is A=[Z,Z,Z,Y,Z]. One unacceptable way is where A=[X,X,X,Z,Z].

I was just going to find the number of days where Y can occur two time, plus the number of days where x happens three times consecutively, add then and subtract that from the total number of days possible, but that wouldn't give me the right answer because it is possible for there to be overlap in those days. I don't remember the right formula I need.

$\endgroup$
7
  • $\begingroup$ To clarify, Y happens at most one time TOTAL, while X can happen many times, bot not three times in a row, correct? $\endgroup$ Nov 20, 2018 at 12:44
  • 1
    $\begingroup$ This is a repeat of math.stackexchange.com/questions/2250558/… which is also equivalent to projecteuler.net/problem=191 $\endgroup$
    – antkam
    Nov 20, 2018 at 14:27
  • $\begingroup$ @TodorMarkov Yes, that is correct $\endgroup$ Nov 20, 2018 at 16:37
  • $\begingroup$ Do you mean Y happens exactly twice or at least twice? $\endgroup$ Nov 21, 2018 at 18:23
  • 1
    $\begingroup$ would like to know your feedback to my answer $\endgroup$
    – G Cab
    Nov 28, 2018 at 15:46

1 Answer 1

2
$\begingroup$

a) Y cannot appear two or more times

Then
- if Y does not appear, we are left with a binary (X,Z) string of length $n=N$;
- if Y appears once, by removing it, we are left with two binary (X,Z) string of length $n$ and $N-n-1$, with $0 \le n \le N-1$.

b) The string does not contain one (or more) runs of three (or more) consecutive X

Consider a binary string with $s$ $X\; \leftrightarrow \,1$'s and $m$ $Z\; \leftrightarrow \,0$'s in total.
The number of these strings in which the runs of consecutive ones have a length not greater than $r$, is given by $$N_{\,b} (s,r,m+1) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m+1} = s \hfill \\ \end{gathered} \right.$$ which is equal to $$ N_b (s,r,m + 1)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{r}\, \leqslant \,m + 1} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} m + 1 \\ k \\ \end{gathered} \right)\left( \begin{gathered} s + m - k\left( {r + 1} \right) \\ s - k\left( {r + 1} \right) \\ \end{gathered} \right)} $$ as thoroughly explained in this and this other posts.

In our case $r=2$, and for a string of length $n$ we shall put $m=n-s$ and sum for $0 \le s \le n$ $$ S(n)\quad = \sum\limits_{\left( {0\, \le } \right)\,s\,\left( { \le \,n} \right)} {\sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{s \over 2}\,} \right)} {\left( { - 1} \right)^k \binom{n-s+1}{k} \binom{n-3k}{s-3k} } } $$

For $n=0,1,2,\cdots ,6$ we obtain that $S(n)$ equals $$1, 2, 4, 7, 13, 24, 44, \cdots$$

c) Conclusion

Standing what said in point a) we can conclude that the sought number $T(N)$ is given by $$ T(n) = S(N) + \sum\limits_{0\, \le \,n\, \le \,N - 1} {S(n)\,S(N - 1 - n)} $$

For $n=0,1,2,\cdots ,8$ $T(n)$ results to be $$1, 3, 8, 19, 43, 94, 200, 418, 861, \cdots$$ which checks correctly with a direct count.

$\endgroup$
2
  • $\begingroup$ Thank you, I get it now! I appreciate it $\endgroup$ Nov 28, 2018 at 20:41
  • $\begingroup$ glad it is useful, if you need any explanation just ask $\endgroup$
    – G Cab
    Nov 28, 2018 at 21:58

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.