7. A coin pyramid is an arrangement of n coins in rows such that • Coins in each row form a contiguous block • For k > 1, coins in the kth row touch exactly 2 coins from the row beneath it. Here is an example of a coin pyramid with 10 coins in the first row: Let an be the number of coin pyramids with n coins in the first row. We have ai = 1 and a2 = 2. = j=1 = a. The sequence satisfies an 1+1=l(n – j)a; for n > 1. Give a combinatorial proof of this recurrence. Note that this formula also holds for n=1 (which makes life easier for us) b. List all the coin pyramids for n = 1, 2, 3, 4. (You can figure out how many there are using the recurrence.) c. Let A(x) = {mo anx”, the ordinary generating function for coin pyramids. Starting with the recursion above, find a simple closed formula for A(x). .
Leave a Reply