Rows of Coins

Consider a game played with n identical coins. You are to arrange the coins in either one row or two rows under the following rules:

1. The bottom row cannot have any gaps, i.e., any coin on the bottom row must touch its neighbor(s) if it has a neighbor or neighbors.

2. Any coin placed on the top row must touch two coins from the bottom row.

Let A(n) (for n > 0) be the number of distinguishable arrangements of these n coins allowed under the rules of the game.

Find a general expression for A(n). What sequence do the numbers {A(j)} produce for j = 0,1,2,3,…(for this, take A(0) = 0)?

I don't think I understand.

There is only one way to create one row of n coins.

And if there are k coins in the bottom row, there must be k-1 coins in the top row, right?

Hence n = 2k-1

But this can't be what you mean.

Originally posted by THUDandBLUNDER
I don't think I understand.

There is only one way to create one row of n coins.

And if there are k coins in the bottom row, there must be k-1 coins in the top row, right?

Hence n = 2k-1

But this can't be what you mean.

Here's what I got.
if n = 0, then A(n) = 0 (or possibly one since there is only one way to set up nothing)
if n = 1, then A(n) = 1
if n = 2, then A(n) = 1
When n >= 3,
1 + (n-2) + (n-3)!/[2! * {(n-3)-2}!] + (n-4)!/[3! * {(n-4)-3}!] + ..... + {(n-1)-(m-1)}!/[(m-1)! * {((n-1)-(m-1))-(m-1)}!] + ((n-1)-m)!/[m! * {((n-1)-m)-m}!],
where m = (n/2)-1 if n is even and m = (n-1)/2 if n is odd.
* is a mutiplication sign

I've resisted condensing the formula since it would harder to figure out how I derived it. Plus this isn't the best formate to show math in. But a quick explination might be in order.

The first 1 is for the amount of ways to setup a single row.
The (n-2) is the number of possible ways to set up a upper row with only one coin in that row.
The rest of it is semi-basic probability that isn't easy to write but it's basic form is z!/[y! * (z-y)!] where z is the number of possible positions for coins in the upper row and y is the number of coins in the upper row.

Originally posted by theangrystudent
Here's what I got.
if n = 0, then A(n) = 0 (or possibly one since there is only one way to set up nothing)
if n = 1, then A(n) = 1
if n = 2, then A(n) = 1
When n >= 3,
1 + (n-2) + (n-3)!/[2! * {(n-3)-2}!] + (n-4)!/[3! * {(n-4)-3}!] + ..... + {(n-1)-(m-1)}!/[(m-1)! * {((n-1)-(m-1))-(m-1)}!] + ((n-1)-m)!/[m! * {((n-1)-m)-m}!],
where m = (n/ ...[text shortened]... of possible positions for coins in the upper row and y is the number of coins in the upper row.

Originally posted by davegage
Your answer looks good...don't see any mistakes...your reasoning is certainly right.

do you recognize what sequence {A(n)} is, assuming we take A(0) = 0?

Originally posted by iamatiger
Looks like fibonacci - I wonder how he comes into it?

Originally posted by davegage
yep -- Fibonacci...I guess there's just no escaping that sequence.

I was trying to figure out a meaningful way to rationalize why it comes into this problem, but it hasn't come to me yet.

Originally posted by elopawn
Here's a Fibonacci question:

Since its 2005, of the first 2005 Fibonacci numbers, how many have 2 as their last digit?

Originally posted by iamatiger
The last digit of each fibonacci number (assuming fib 1 = 0) forms a 60 digit repeating sequence, which contains 4 instances of the number 2.
There are 33 60s in 2005, remainder 25
and of the first 25 fibonacci numbers, only 1 ends in 2 ...[text shortened]...

Can anybody explain why that sequence goes 4,8,4,8,4,8,4,8,4,8?

ignore