Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Combinatorics fun

  1. Mar 18, 2010 #1


    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data
    1. Recall that Fn denotes the number of perfect coverings of a 2–by–n chessboard with dominoes.
    Use combinatorial reasoning to show that

    F2n = Sum [of k=0 to k=n] of (nCk) Fk

    for all integers n ≥ 0. Make sure to describeFk in the context of perfect coverings of a 2–by–2n

    2. Relevant equations
    (it's given above, we just have to prove it combinatorially)

    3. The attempt at a solution
    The idea here is to count perfect coverings of a 2–by–2n chessboard based on the number of vertical dominoes that appear in the first n dominoes in the top row of the board from left to right, but I'm having trouble applying it, because there are certain restraints in how the vertical dominoes may be placed.
    Last edited: Mar 18, 2010
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted