Jtdylktuy

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.

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
= sumlimits_{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 - kleft( {r + 1} right) \
s - kleft( {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 = sumlimits_{left( {0, le } right),s,left( { le ,n} right)} {sumlimits_{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) + sumlimits_{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.