Help understanding algorithmic solution

[Script Coder]

Hey all, I was working on a problem and eventually I got so frustrated I looked at the answer sheet (yes, it was wrong) only to find that I am now even more frustrated because I do not understand the solution. Here is the question:
say you are given a string on length N and beads that are either 2 or 3 units wide in C different colours, how many possible designs are there given N and C?

The part of the solution I do not understand:
Let f(n) be the number of combinations of length n with c colours. We then use the recurrence relationship: F(n)=C*(F(n-2)+F(n-3))

How did they get that relation?
Any help is greatly appreciated.

[rmxhaha]

I think this is a brute force approach for a combination problem

Just think of this recursive as

Say I have this Long string
-------------------------------------------------------------------------

Now let say I pick beads with 2 unit wide
XX----------------------------------------------------------------------

New let's add another 2 unit wide beads
XXXX-------------------------------------------------------------------

Continue on until you cannot add anymore beads
and then you go back and try adding combination beads with 3 unit wide

The colour (C) timed the result is only because the same combination of beads with those 2 different width can also have C different colours

Another more simpler way I think of this is

F(N) is the number of combination of beads that is possible for N length of string left

Sorry, I kinda understand this. but couldn't explain it too well

[Disch]

Let f(n) be the number of combinations of length n with c colours. We then use the recurrence relationship: F(n)=C*(F(n-2)+F(n-3))

F(n) represents a string of length N. You can place any 1 color bead on that string... which will consume space on the string.

There are 2*C possible beads to place on the string. 2* because one set is of length 2 and one set is of length 3... resulting in 2 sets.

So you place 1 bead on the string... this reduces the length of N (available string space) by the size of the bead you placed. You then have another 2*C possibilities for the next bead.

Therefore:
F(n) = 2*C * F(n - size_of_last_bead)

But since the size of the last bead is variable... it's not that simple. Instead, we need to the two sizes differently.

So instead of saying we have 2*C possibilities... let's say we have C possibilities of length 2, and C possibilities of length 3:

F(n) = C*F(n-2) + C*F(n-3)


From there, you just factor out the C and you get the equation in your original post:

F(n) = C( F(n-2) + F(n-3) )



EDIT:

Although this solution is not complete because it does not account for the possibility of ending the string short (it assumes you will use as much of the string space as possible in your computations)

So the proper formula would probably be closer to this:

F(n) = 1 + C*F(n-2) + C*F(n-3)

But even that isn't quite right because doing F(n) with a negative number will not work, so you'd have to conditionally call F(n-2) and F(n-3)

[Script Coder]

Thank you Disch. I now understand where the recurrence relation comes in. As for negative numbers, read the question: how are you going to have a string of length -N?

Why would adding one prevent us from "ending short"? Also, what do you mean by "ending short"? Do you mean that there will be one left over?

EDIT: Oh, yes, I almost forgot: Thank you rmxhaha, while that solution could work it would not solve the problem in the my time constraints. :)

[Disch]

how are you going to have a string of length -N?

F(n) calls F again with a smaller value for N. Eventually, N is going to drop to or below 0 (example, F(2) calls F(0) and F(-1)). So you have to treat those cases separately.

Why would adding one prevent us from "ending short"?

No beads at all is a possible permutation.

A single bead of size 2 and no other beats is a possible permutation for N=100

Nothing in the problem seems to indicate you only count permutations which use all possible space on the string.


EDIT: My + 1 solution might not be right. I kind of pulled it out of my butt without really thinking about it. =P

[Script Coder]

F(n) calls F again with a smaller value for N. Eventually, N is going to drop to or below 0 (example, F(2) calls F(0) and F(-1)). So you have to treat those cases separately.

Well, yes, those would be your base cases. If there were no such thing, then recurrence relationships would never work...

F(1)=0
F(2)=C
F(3)=C
Would those not be your needed base cases?

Nothing in the problem seems to indicate you only count permutations which use all possible space on the string.

I did not think it would be a train smash if I left that out. Sorry :)