1
$\begingroup$

I came across this question on the internet and I am trying to wrap my head around how to solve it.

Mark likes to listen to music while travelling. His iPod contains $n$ songs and he wants to listen to $l$ (not necessarily different) songs during a trip. So he creates a playlist such that:

  • Every song is played at least once.
  • A song can be played again only if at least $k$ other songs have been played.

Mark wants to know how many different playlists are possible. Can you help Mark determine this number? $1\le k\le n\le l\le100$.

My Approach:

We can only choose $\dfrac{n!}{(n - k)!}$ for the first $k$ songs and after that we are free to choose from the entire sample of $n$. This leaves us with $$ \frac{n!}{(n-k)!} × n^{l-k}$$ combinations.

Is my solution right? If not what detail am I missing?

$\endgroup$
  • 1
    $\begingroup$ My interpretation of the question is that the condition should read as "a song can be played again only if at least $k$ other songs have been played [since the last time it has been played]." In your solution, you did not guarantee that every song is played at least once, and you allowed for the same song to be played back to back to back ad nauseum after the first $k$ songs had been played, making the $k+1$'st, $k+2$'nd, on up until the final song in the playlist able to be the same song repeatedly. I certainly wouldn't want that in my playlist for a trip. $\endgroup$ – JMoravitz Mar 7 '18 at 5:42
  • 1
    $\begingroup$ As for an approach on how to solve the question with my interpretation above, I would try to use recurrence relations (for condition2) coupled with inclusion-exclusion (for condition1). Let $F_k(n,l)$ be the number of playlists of length $l$ with a library of $n$ songs satisfying condition $2$ (ignoring 1). For $l>k$ note that $F_k(n,l)=(n-k)F_k(n,l-1)$, and that for $l\leq k$ we have $F_k(n,l)=n\frac{l}{~}$ (using falling factorial notation). Similarly work out for if $n$ decreases. Then apply inclusion-exclusion on if a track is missing from the playlist to correct the count. $\endgroup$ – JMoravitz Mar 7 '18 at 5:55
  • $\begingroup$ @Jmoravitz Your comment is very helpful. Please can you give a hint on how we can find out if a track is missing using inclusion-exclusion? I'm fairly new to inclusion-exclusion principle and I can't figure it out. Thanks $\endgroup$ – Shankar May 10 '18 at 1:51

Your Answer

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

Browse other questions tagged or ask your own question.