Perfect Coverings of 2-by-2n Chessboard | Combinatorics Fun

In summary, the problem asks for a combinatorial proof of the equation F2n = Sum [of k=0 to k=n] of (nCk) Fk, where Fn represents the number of perfect coverings of a 2-by-n chessboard with dominoes. The solution involves counting perfect coverings of a 2-by-2n chessboard based on the number of vertical dominoes in the first n dominoes of the top row. However, there are constraints on the placement of vertical dominoes, as the kth domino from the left cannot have a vertical domino to its immediate right. This information must be incorporated into the combinatorial proof.
  • #1
silvermane
Gold Member
117
0

Homework Statement


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.

Homework Equations


(it's given above, we just have to prove it combinatorially)

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:
Physics news on Phys.org
  • #2
That is, if the kth domino from the left is a vertical one, then neither of the two dominoes to its immediate right may be vertical. I'm not sure how to use this information to prove the equation combinatorially. Any help would be much appreciated.
 

1. What is a perfect covering in the context of a 2-by-2n chessboard?

A perfect covering of a 2-by-2n chessboard is a tiling of the board with non-overlapping dominoes, where each domino covers exactly 2 squares of the board. The goal is to cover the entire board without any gaps or overlaps.

2. How many perfect coverings are possible for a 2-by-2n chessboard?

The number of possible perfect coverings for a 2-by-2n chessboard is equal to the number of ways to arrange n dominoes on a 2-by-2 grid, which is given by the formula (2n)!/2^n. For example, for a 2-by-4 chessboard, there are (2*4)!/2^4 = 90 possible perfect coverings.

3. Is there a mathematical formula for calculating the number of perfect coverings for any 2-by-2n chessboard?

Yes, the number of perfect coverings for a 2-by-2n chessboard can be calculated using the formula (2n)!/2^n. This formula is derived from the fact that each perfect covering can be represented as a permutation of n dominoes on a 2-by-2 grid, and the number of possible permutations is given by (2n)!.

4. How is combinatorics used in finding perfect coverings of 2-by-2n chessboards?

Combinatorics is the branch of mathematics that deals with counting and arranging objects. In the context of finding perfect coverings for 2-by-2n chessboards, combinatorics is used to determine the number of possible ways to arrange the dominoes on the board and to identify any patterns or symmetries that may exist in the coverings.

5. Are there any real-world applications for perfect coverings of 2-by-2n chessboards?

While perfect coverings of 2-by-2n chessboards may seem like a purely theoretical concept, it has real-world applications in the field of computer science. The problem of finding a perfect covering can be used to model and solve more complex problems, such as scheduling and resource allocation, in which objects need to be arranged in a certain way without any overlaps or gaps.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
5K
  • Calculus and Beyond Homework Help
Replies
3
Views
845
  • Calculus and Beyond Homework Help
Replies
17
Views
7K
  • Calculus and Beyond Homework Help
Replies
5
Views
4K
  • Calculus and Beyond Homework Help
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
10
Views
3K
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
Back
Top