1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics fun

  1. Mar 18, 2010 #1

    silvermane

    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
    chessboard.

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?



Similar Discussions: Combinatorics fun
Loading...