I have a question:

let a(n) be the number of ways to construct a wall of height 2 & length n, built with single bricks "." or double bricks ":" or ".." find a recurrence for a(n) & find a(10)

I think I may have found a solution to this problem, but it doesn't involve any of the previous terms the sequence, so it's not a recurrence relation...

I've been trying to come up with a recurrence relation for this problem, but I just don't see how a(n) relates to a(n-1) or anythin' like that...

please help =)

So, there are 8 ways to build a column?




...but six of the possibilities imply a second column and there are two choices for the second column and one of the choices implies a third column (no choice).

Hmmm. but if you build from left to right, your beginning is restricted to column types 1,2,5 and 7...? Hard! Is this cancelled out by the completion of the series?

Sorry, but this isn't much help, but there are 3 symbols and the symbols have to add up to two horizontally or two vertically.

How about: there are 4 ways to start the wall:



but 2 of the choices imply 2 other choices:
Choice 1:


Choice 2:



And then there's a recursion, because one of the two choices starts the 2-choice loop again- the other choice starts the wall (main loop) again? Does that work?

my prof told me that the horizontal double bricks --> ..

take up two spaces in the wall...so if you have length n=1, you can't use horizontal double bricks, b/c you need at least n=2.

I'm thinkin' that there's five ways to start the wall: (s=single, v=vertical, h=horizontal)

s
s________________.....n

v
v________________.....n

hh
hh_______________...n

ss
hh_______________...n

ss
hh__________________...n

assuming that for the last three ways there's only one pair of horizontal double bricks.

if that's the case I can see the recurrence relation...but I don't know if that makes sense =///

it's kind of like looking for the relation for bit strings that contain a pair of consecutive 0's --> 00

you can have a bit string that starts with 1, & the 00 is in it so length = n-1

or you can have a bit string that starts with 01, & the 00 is in it so length = n-2

or you can have a bit string that starts with the 00, so the length is 2^n-2

then the recurrence relation would be: a(n) = a(n-1) + a(n-2) + 2^n-2

does any of this make sense??? >.<

I'm trying to compare the question to bit strings b/c it makes it easier.

You're right, my series misses two possibilities:



Which means there are 5 ways to start the wall:



one of the choices implies 2 columns. Like you say.

but 2 of the choices imply 2 other choices:
Choice 1:


Choice 2:



So there's a main loop (5 choices) with 3 branches, the 1 branch, say, implies 2 horizontal blocks.

The 2 and 3 branches loop, because: the 2 branch either exits (if...), or (else...):


looks like the 3. branch.

Yes, that's a good point about n=1 and n=2 as well... I don't think I'm helping.
I think you're right about the bit series- but...

What about if you look at a row... then there are 3 symbols that are possible:

so you have this kind of pattern, 1 2 33 2 33 1 33 33 2 1 33 2 1 2 1 ...., you could change the second 3 to a 4 and then you would have a 2bit char string- but anyway, you have choices for a string of .
In the two row series, the interesting thing is the vertical character, because that restarts the count- so that whenever you get, say, a 2 the sub-program adds the number of proceeding 1s and 33s (or 3-4s) to a total. The two is analog to the beginning of the wall.
1 3-3 1 1 2 3-3 2 1 3-3 2...
3-3 1 3-3 2 3-3 2 3-3 1 2...
so you have a bit series, 1 or 3-3 wich is n bits long until there is a 2. So, the two can be at or ... Err

1 1 1 1 1 3-3 3-3 1 1 1 1 1 1 1 3-3 3-3 1 ...d...
1 1 1 3-3 1 1 3-3 1 3-3 3-3 1 1 1 1 1 1 1 ...d...
(w. d= 2, or vertical)

These seem to be the requirements of the series..?
So, for n=1 there is 1 possibility
and for n=2 there are 4 possibilities
and for n=3 there are 4? need to check this...
and then you have a d at n=1 or 2 (or (2+1) or (1+1+2), etc)

What about if you look at a row... then there are 3 symbols that are possible:

so you have this kind of pattern, 1 2 33 2 33 1 33 33 2 1 33 2 1 2 1 ...., you could change the second 2 to a 4 and then you would have a 2bit char string- but anyway, you have choices for a string of .
In the two row series, the interesting thing is the vertical character, because that restarts the count- so that whenever you get, say, a 2 the sub-program adds the number of proceeding 1s and 33s (or 3-4s) to a total. The two is analog to the beginning of the wall.
1 3-3 1 1 2 3-3 2 1 3-3 2...
3-3 1 3-3 2 3-3 2 3-3 1 2...
so you have a bit series, 1 or 3-3 wich is n bits long until there is a 2. So, the two can be at or ... Err

1~~~1 1~~~1 1~~~3-3~~~3-3~~~1 1 1~~~1 1 1~~~1 3-3~~~3-3~~~ ...d...
1~~~1 1~~~3-3~~~1 1~~~3-3~~~1 3-3~~~3-3 1~~~1 1 1~~~111~~~ ...d...
(w. d= 2, or vertical)

These seem to be the requirements of the series..?
So, for n=1 there is 1 possibility
and for n=2 there are 4 possibilities
and for n=3 there are 4? need to check this...
and for n=4 there are 4*4?
and then you have a d at n=1 or 2 (or (2+1) or (2+2), etc)