Problem

Source: Bulgaria EGMO TST 2020 Day 2 Problem 1

Tags: combinatorics, counting, recursion, bijection, geometry, rectangle



Let $n$ and $t$ be positive integers. What is the number of ways to place $t$ dominoes $(1\times 2$ or $2\times 1$ rectangles) in a $2\times n$ table so that there is no $2\times 2$ square formed by $2$ dominoes and each $2\times 3$ rectangle either does not have a horizontal domino in the middle and last cell in the first row or does not have a horizontal domino in the first and middle cell in the second row (or both)?