help

Let's call a \(2 \times 2\) square a 'block' and a \(2 \times 1\) rectangle consisting of a column of two \(1 \times 1\) squares a 'blank'. So a \(2\times 10\) grid, for instance, consists of 10 consecutive blanks, numbered 1 to 10 from left to right, and a block occupies two consecutive blanks, say blanks 1 and 2, which I will denote by (1, 2). The max number of blocks that can be arranged on our \(2 \times 10\)grid is, of course 5, and the places they would occupy  would be denoted as (1, 2), (3, 4), (5, 6), (7,8), and (9,10). We will first look at the number of arrangements on the \(2 \times 10\) grid and then extend the results to a \(2 \times 50\) grid.

First note that a block can occupy a \(2 \times k\) blan grid in k - 1 different ways. For instance, on a \(2 \times 10\) blank grid, the block can be placed on (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), or (9, 10).

The following table shows that the number of arrangements for a \(2 \times 10\) grid is

\({10 \choose 0 } + {9\choose 1} +{8\choose 2}+{7\choose3}+{6\choose 4}+{5\choose5}=89\)

Thiscan be generalized to a \(2 \times 50 \) Grid. see below

Sorry,I posted an EXCEL chart without explanation. For the \(2 \times 50\) grid, the number of arrangements is

\({50 \choose 0}+{49 \choose 1} + {48 \choose 2} + ...+{26 \choose 24} +{25 \choose 25}= 20,365,011,074\) arrangements. EXCEL was the only tool I could use to calculate such an enormous sum.

I am looking for a more elegant way to count this giant number of arrangement. I am certain there is one somewhere on the web!

There are 8 ways that 1 x 1 and 2 x 2 squares can be arranged in a 2 x 5 grid:

Find the number of ways that 1 x 1 and 2 x 2 squares can be arranged in a 2 x 50 grid.

\(\begin{array}{|c|c|c|c|} \hline & \text{Starts with} & \text{Starts with} \\ \text{grid:} & 2\times 1 & 2\times 2 & \text{sum} \\ \hline 2 \times 1 & 1 & 0 & 1 = F_{2} \\ \hline 2 \times 2 & 1 & 1 & 2 = F_{3} \\ \hline 2 \times 3 & 2 & 1 & 3 = F_{4} \\ \hline 2 \times 4 & 3 & 2 & 5 = F_{5} \\ \hline 2 \times 5 & 5 & 3 & 8 = F_{6} \\ \hline 2 \times 6 & 8 & 5 & 13 = F_{7} \\ \hline 2 \times 7 & 13 & 8 & 21 = F_{8} \\ \hline \ldots & \ldots \\ 2 \times 10 & 55 & 34 & 89 = F_{11} \\ \hline \ldots & \ldots \\ \hline 2 \times k & F_k & F_{k-1} & F_{k+1} \\ \hline 2\times 50 & F_{50} & F_{49} & 20365011074= F_{51} \\ \hline \end{array}\)

\(\begin{array}{|lrcll|} \hline \mathbf{ F_k \text{ is the } k^{th} \text{ Fibonacci Number:}} \\ F_1 = 1,\ F_2 = 1,\ F_3 = 2,\ F_4 = 3,\ F_5 = 5, \\ F_6 = 8,\ F_7 = 13,\ F_8 = 21,\ F_9 = 34,\ F_{10} = 55,\ldots , \\ F_{49} = 7778742049,\ F_{50} =12586269025,\ F_{51} = 20365011074 \\ \hline \end{array}\)

hint:

Fibonacci Number as Sum of Binomial Coefficients:

\(\begin{array}{rcll} \displaystyle F_n &=& \displaystyle \sum_{k \mathop = 0}^{\Big\lfloor {\dfrac {n - 1} 2}\Big\rfloor } \dbinom {n - k - 1} k \\ &=&\displaystyle \binom {n - 1} 0 + \binom {n - 2} 1 + \binom {n - 3} 2 + \dotsb + \binom {n - j} {j - 1} + \binom {n - j - 1} j \quad \text{ where } \quad j = \Big\lfloor {\dfrac {n - 1} 2} \Big\rfloor \\ \end{array}\)

source: https://proofwiki.org/wiki/Fibonacci_Number_as_Sum_of_Binomial_Coefficients