Counting the amount of desirable colourings Inspired by This topic:
Let there be $N$ balls in a straight line. We colour them with $m$ $(c_1, c_2,\ldots , c_m)$ different colours. 

Determine the probability there exists at least one streak of monochromatic balls of at least length $1\leq k\leq N$.

The real question here is, how do we count how many of the colourings are desirable to us and how many there are in total.
For instance, pick $N=5, m=2$ (equal probability), $k=3$.
With two colours, there should be $2^5 = 32$ different colourings.
EDIT: Thanks Arthur
$5$ ways for three consecutive to occur, $2$ ways for four consecutives and $1$ way of five consecutives. By symmetry, there should be $16$ desirable choices. 
With some modifications we can also work out the solution if the colourings had different probabilities.
Question:
How do we count desirable choices when $N=100, m=2$ (equal probability) and $k = 5$? 
It's not very sensible to count each case. Is there a way to work this problem out with pen and paper?
 A: There are $m^N= 2^{100}$ cases in total.
There are $1231762993555129375668495000350$ desirable cases.
To count each the desirable cases exactly once you can do this for all $i\in[k,N]$:


*

*Choose a common color for the balls with position $i-k+1$ to $i$. Count a factor $m$

*Choose any color for the balls with position $i+1$ to $N$. Count a factor $m^{N-i}$

*Partition (with ordering) the balls with position $1$ to $i-k$ into groups of size $1$ to $k-1$. E.g. for $i=9,k=5$ the valide group sizes are
$\quad\{\{4\},\{3,1\},\{1,3\},\{2,2\},\{2,1,1\},\{1,2,1\},\{1,1,2\},\{1,1,1,1\}\}$
For each partition the last group must have a color different from that of step 1. The second last group must have a color different from the last group etc. Hence a given partition yields $(m-1)^q$ cases, where $q$ is a group count. In total we get a factor $S=\sum_q(m-1)^q$. For the example ($i=9,k=5$) we have $q=1,2,2,2,3,3,3,4$


The sum depends on variables $k$, $i$ and constant $m$. We have
$S(1, i) = \max(2-i, 0)
\\S(k, i)=\begin{cases} 
      S(k-1,i-1)& k\leq i\leq 2 k-2 \\
      (m-1)\sum_{j=1}^{k-1}S(k,i-j)& \text{else} 
   \end{cases}$
To get the result multiply the factors and sum over $i$:
$$\sum_{i=k}^N S(k,i)m^{N-i+1}$$
