# number of ways to tile a $n\times n$ grid with $k<n^2$ $1\times 1$ tiles?

So, there are alot of questions about tiling in this forum but I could not find this exact question.

I am trying to find out the number of possible "tile configurations" in an $$n\times n$$ grid where the tiles are $$1\times 1$$ and there are k less than or equal to $$n^2$$ of them. I have link down below with the "tile configurations" for a $$2\times 2$$ grid.

I don't know, but I feel like I am missing some simple way of approaching the problem. I've been trying to frame it in the context of the combination formula, but I feel like my intuition is lacking... Anyway, if someone could give me a hint that would be much appreciated.

• Where does 17 come from? – user10354138 Jun 17 at 8:33
• You missed one for $k = 2$ (all black ones on top), and you haven't counted $k = 0$ (the answer becomes much nicer if you do). – Arthur Jun 17 at 8:35
• Hmm, for some reason the picture doesnt show ll configurations. There's supposed to be one more for k=1, k=2, and k=3, to left of the picture... – Victor Galeano Jun 17 at 8:52
• Is this not "$k$ choices for the first tile, $k$ choices for the second tile, ..., $k$ choices for the $n \times n^\text{th}$ tile, so $k^{n^2}$ tilings"? If not, why not? – Eric Towers Jun 17 at 9:11

## 1 Answer

For any integer $$k \le n^2$$ there are $$\binom{n^2}{k}$$ ways to pick $$k$$ tiles from the $$n \times n$$ grid. If you want to count all but $$k \in \{0,n^2\}$$, you will receive $$\sum_{k=1}^{n^2-1}\binom{n^2}{k} = 2^{n^2} - \binom{n^2}{0} - \binom{n^2}{n^2} = 2^{n^2} - 2$$ In your drawing, you missed "2 on top". Summing up the numbers for $$k \in \{1,2,3\}$$ you receive $$4 + 6 + 4 = 14 = 16 - 2 = 2^{2^2} - 2$$