So, it looks like your method may be wrong.

[Gtotheiles]

OK, here's the quesiton:

You own an iPod on which you currently have 19 songs loaded. You wish to create a playlist in which no two consecutive songs are played, no more than two songs in a row are omitted, and the songs are played in the order they are currently loaded. How many playlists are possible?

Our method was to figure out how many were possible on less number of songs, such as 3, 5, 7 etc., and find a pattern. The number of possible playlists for 3 songs is 4, for 5 it's 7, for 7 it's 12, for 9 it's 21, and for 11 it's 36. These numbers were found by counting out every individual possibility. We then looked for a pattern within these numbers. We found that by adding 3 to the possibilities of 3, we received the number for 5 songs. Then adding 5 (2 more than the previous addition), we received the number for 7 songs. Than adding 9 (4 more than the previous), receiving the number for 9 songs. then 15 (6 more than the previous), we received the number for 11 songs. The number added goes up by 2 each consecutive time, and we applied this formula to get the rest of the numbers, for 13, 15, 17 and 19. However, I do not think that our number (196) is large enough. Anyone have thoughts? Are we correct? Or why is our method wrong (if it is). Huge appreciation for help received before tomorrow afternoon. Thanks in advance.

 

[honestrosewater]

I'm not positive, it seems quite complicated, just some thoughts. Number your songs as loaded 1 - 19. Your playlists will be sequences of the form:
s₁, s₂, ..., s_i, ..., s_n.

"the songs are played in the order they are currently loaded". So for any two songs s_i and s_j in the list, s_i < s_j iff i < j. (i.e. the songs are in increasing order.)

"no two consecutive songs are played". So for any two songs s_i and s_i+1 in the list, s_i+1 - s_i > 1. (i.e. ruling out 1, 2 and 2, 3 and ... from being in the list, but allowing 1, 3 or 2, 5 etc.)

"no more than two songs in a row are omitted". So for any two songs s_i and s_i+1 in the list, s_i+1 - s_i < 4. And from above, 1 < s_i+1 - s_i < 4. So each term can increase by 2 or 3.
Let m be the first song in the list. m can equal 1, 2, or 3. Let p be the last song in the list. p can equal 19, 18, or 17. Make sense? You can omit at most 1 & 2 and 19 & 18. For example:
1, 4, 7, 10, 13, 16, 19
2, 5, 8, 11, 14, 17
3, 6, 9, 12, 15, 18

So your lists can start with 1, 2, or 3, can end with 17, 18, or 19, and each term can increase by 2 or 3. So, for instance, you can start with 1, add 3 six times, giving:
1, 4, 7, 10, 13, 16, 19
and 1 + 3*6 = 19. Or you can start with 1, add 3 five times and add 2 once, giving, as two possibilities:
1, 4, 7, 10, 13, 16, 18
1, 3, 6, 9, 12, 15, 18
and 1 + 3*5 + 2*1 = 18. So I think you want to find all solutions to m + 2x + 3y = p, where m = 1, 2, or 3, p = 17, 18, or 19, and x and y are integers > 0. Actually, I think 5 < x + y < 9. Heh, maybe this doesn't help you after all, but I guess it can't hurt.

 

[AKG]

I've found a pattern, but it might be a little hard to explain. Start by making a tree diagram with 1, 2, and 3 at the top. Then let 1 branch down into 2 branches, one labelled 3, the other labelled x. So the bottom of your tree will have a 3 and an x, plus a 2 and a 3 one level up. These four leafs will be called your "3 row." Next, write a 4 under your x's, and branch your 3's off into two leaves each, one 5 and one x, branch your 2 off into 4 and 5. Under the 3, you have a 5 and an x. This symbolizes that you can either choose to play song 3, then song 5, or play song three then stop, if we only have 5 songs. The new "bottom" of your tree will be your "5 row." Your "n row" will represent the possible play lists if you have n songs. Every such row will always have a part of it lower than the rest, and a part that is higher than the rest (like 3 levels), but just treat everything that is at the bottom of a branch as part of the same row. The number of leaves in a row is the number of play lists, but how do we find this?

t_n = x_{n-2} + 2P(n-3)_{n-2} + 2P(n-2)_{n-2}

where x represents the number of x's on the n-2 row. Note that you will have to look at the n-2 row before you added the n row, since in adding the n row, you changed the x's to n-1, so there would appear to be no x's on the n-2 row. P(n-3)_{n-2} is the number of n-3's on the n-2 row, and P(n-2)_{n-2} is the number of n-2's on the n-2 row. This formula above is true because each x will not branch off. For example, in the three row, we have 3, x, 2, 3. In the 5 row, x will turn into a 4, and 4 can't branch off into anything since if you need to skip at least one song, you'll have to play at least song 6 after song 4, but row 5 is only if we have 5 songs on the list. So that's why x_{n-2} has a coefficient of 1 in the above formula. The other two terms have coefficients of 2, since n-3 will branch off into n-1 and n, and n-2 will branch off into n and x, meaning that if you played song n-2, then you can either play the last song, or just stop at n-2. And on row n-2, the only possibilities are x, n-2, or n-3. n-4 is not a possible way to end a branch, since it would branch off into n-2 and x. So t_n can be completely described by what's on the above row, and that's a simple formula based on the number of x's, n-2's, and n-3's on the previous row, the previous row being the n-2 row.

Now how do we compute each of these things? P(n-3)_{n-2} = t_{n-2} - P(n-2)_{n-2} - x_{n-2}. That is, the number of n-3's on the n-2 row is just the total number on that row, minus the number of things that aren't n-3's. If we plug this into the formula, we get:

t_n = 2t_{n-2} - x_{n-2}

How do we find x_{n-2}? Well if you make the tree, then you'll see that the number of x's on the 11 row is just the number of 9's on the 9 row. This make sense if you think about it. An 8 will branch off into a 10 or 11. An x will turn into a 10, and not branch off at all, and a 9 will branch off into an 11 or x. So for each 9 on the 9 row, there's an x on the 11 row. It's not hard tos ee in general that x_k = P(k-2)_{k-2}. Plug this into the formula, we get:

t_n = 2t_{n-2} - P(n-4)_{n-4}

The number of n-4's on the n-4 row of course depends on what's on the n-6 row. n-6 or n-7 will branch off into n-4 and x, or n-5 and n-4, respectively, whereas x will just turn into n-3 and not branch off at all. So everything that's not an x on the n-6 row will produce one n-4 on the n-4 row. So we can substitute P(n-4)_{n-4} = t_{n-6} - x_{n-6}.

t_n = 2t_{n-2} - t_{n-6} + x_{n-6}

Well you can see where this will lead. We will express x_{n-6} = P(n-8)_{n-8} and then P(n-8)_{n-8} = t_{n-10} - x_{n-10}. Eventually, we'll get:

t_n = 2t_{n-2} - t_{n-6} + t_{n-10} - t_{n-14} + \dots \pm (t_{\alpha} - x_{\alpha})

where \alpha \in \{1,\, 3\}.

t_1 - x_1 = 2 - 0 = 2

t_3 - x_3 = 4 - 1 = 3

Note that unlike what you said, this gives that t_{11} = 37[/tex]. If you make the tree, you&#039;ll see this to be the case. Now this formula should be further reducible, and I encourage you to do it.

 

[NateTG]

Hmm.
let's call p(x) the number of playlists from x songs that play the first song.
Then
p(1)=1
p(2)=1
p(3)=2
And for larger x it's pretty easy to see that p(x)=p(x-2)+p(x-3).

Now, let's call P(x) the number of playlists. Clearly, for x>=3:
P(x)=p(x)+p(x-1)+p(x-2)

Now
P(19)
=p(19)+p(18)+p(17)
=p(18)+2p(17)+p(16)
=2p(17)+2p(16)+p(15)
=2p(16)+3p(15)+2p(14)
=3p(15)+4p(14)+2p(13)
=4p(14)+5p(13)+3p(12)
=5p(13)+7p(12)+4p(11)
=7p(12)+9p(11)+5p(10)
=9p(11)+12p(10)+7p(9)
=12p(10)+16p(9)+9p(8)
=16p(9)+21p(8)+12p(7)
=21p(8)+28p(7)+16p(6)
=28p(7)+37p(6)+21p(5)
=37p(6)+49p(5)+28p(4)
=49p(5)+65p(4)+37p(3)
=65p(4)+86p(3)+49p(2)
=130+172+49=351

If you want to get more sophisticated - like finding, say P(50,000) - you can probably work out a closed form for this, but that's a bit more advanced.