Skip to main content
added 276 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Here is a simple recursion that you can use to compute the value. Let $T(n)$ denote the number of tilings of a $2 \times n$ rectangle, using rectangles with integer sides. If no rectangles of height $2$ are used, then we reduce to two independent instances of the $1 \times n$ case, and so there are $2^{2n-2}$ ways to do this. Otherwise, we condition on the rightmost rectangle of height $2$. This yields, $$ T(n)=2^{2n-2}+\sum_{k=0}^{n-1} T(k)+\sum_{0\leq k < \ell \leq n-1}T(k)2^{2(n-\ell-1)}, $$ with the initial conditions $T(0)=1$ and $T(1)=2$. Note that the formula $2^{n-1}$ for the $1 \times n$ case is not correct if $n=0$, so the middle term in the recursion corresponds to the case that the rightmost rectangle of height $2$ is actually the rightmost rectangle in the tiling.

Here is a simple recursion that you can use to compute the value. Let $T(n)$ denote the number of tilings of a $2 \times n$ rectangle, using rectangles with integer sides. If no rectangles of height $2$ are used, then we reduce to the $1 \times n$, so there are $2^{2n-2}$ ways to do this. Otherwise, we condition on the rightmost rectangle of height $2$. This yields, $$ T(n)=2^{2n-2}+\sum_{k=0}^{n-1} T(k)+\sum_{0\leq k < \ell \leq n-1}T(k)2^{2(n-\ell-1)}, $$ with the initial conditions $T(0)=1$ and $T(1)=2$.

Here is a simple recursion that you can use to compute the value. Let $T(n)$ denote the number of tilings of a $2 \times n$ rectangle, using rectangles with integer sides. If no rectangles of height $2$ are used, then we reduce to two independent instances of the $1 \times n$ case, and so there are $2^{2n-2}$ ways to do this. Otherwise, we condition on the rightmost rectangle of height $2$. This yields, $$ T(n)=2^{2n-2}+\sum_{k=0}^{n-1} T(k)+\sum_{0\leq k < \ell \leq n-1}T(k)2^{2(n-\ell-1)}, $$ with the initial conditions $T(0)=1$ and $T(1)=2$. Note that the formula $2^{n-1}$ for the $1 \times n$ case is not correct if $n=0$, so the middle term in the recursion corresponds to the case that the rightmost rectangle of height $2$ is actually the rightmost rectangle in the tiling.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Here is a simple recursion that you can use to compute the value. Let $T(n)$ denote the number of tilings of a $2 \times n$ rectangle, using rectangles with integer sides. If no rectangles of height $2$ are used, then we reduce to the $1 \times n$, so there are $2^{2n-2}$ ways to do this. Otherwise, we condition on the rightmost rectangle of height $2$. This yields, $$ T(n)=2^{2n-2}+\sum_{k=0}^{n-1} T(k)+\sum_{0\leq k < \ell \leq n-1}T(k)2^{2(n-\ell-1)}, $$ with the initial conditions $T(0)=1$ and $T(1)=2$.