Katie wants to make a list of songs from her phone , in how many ways can she make one? Katie has $m$ songs in her phone, she wants to make a playlist consisting of $s$ songs such that every song is played at least once, and  a song can be played again if and only if at least $k$ other songs have been played in between.  

In how many ways can she create such a playlist?

attempt: Let Katie have $m$ songs in her phone such that there are $s$ songs to be played . Suppose $k \leq t$  so that we select $t$ songs from $m$ songs, so that we have $m \choose t$ , then at least $k$ songs implies we have $k$ or more, so we have $m \choose k $ + $m \choose k+1$ + ...+ $m \choose m$ = $\Sigma_{t = k}^m $ $m \choose t$ total ways.
Can someone please verify this is correct? and if it's not, please provide some feedback. Thank you.
Let $m,s$ be positive integers, and let $k$ be a nonnegative integer.

Let $f(m,k,s)$ be the number of playlists of length $s$ from a collection of $m$ songs, with the restriction that if a given song is replayed, there must be at least $k$ other songs between the play of the given song and the replay.

Then $f$ is given by the following piecewise formula:

$$
{\small{\bullet}}\;\;\text{If $s \ge k+1$ then}
\qquad\qquad\qquad\qquad\qquad\qquad\qquad
\qquad\qquad\qquad\qquad\qquad\qquad\qquad
$$

$$
f(m,k,s) =
\begin{cases}
\left({\large{\frac{m!}{(m-k-1)!}}}\right)(m-k)^{\large{{s-k-1}}} &amp; \text{if $m &gt;k$}\qquad\qquad\qquad\;\;\;\,\\[6pt]
\;\;0 &amp; \text{otherwise}\\[6pt]
\end{cases}
$$

$$
{\small{\bullet}}\;\;\text{else if $s &lt; k+1$ then}
\qquad\qquad\qquad\qquad\qquad\qquad\qquad
\qquad\qquad\qquad\qquad\qquad\qquad\;\;\,
$$

$$
f(m,k,s) =
\begin{cases}
m!/(m-s)! &amp; \text{if $m \ge s$}
\qquad\qquad\qquad\qquad\qquad\qquad\qquad\\[6pt]
\;\;0 &amp; \text{otherwise}\\[6pt]
\end{cases}
$$
For m = 3, s = 5 and k = 1. The above answer gives 48. But the correct answer is 42. If the three songs are A, B and C. Then the playlists like ABABA and ACACA should be subtracted from the count since not every song is played at least once.

P.S I do not have credit to add a comment for the above answer. That's why added as a separate answer.