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.

  • 1
    $\begingroup$ Where does 17 come from? $\endgroup$ – user10354138 Jun 17 at 8:33
  • $\begingroup$ 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). $\endgroup$ – Arthur Jun 17 at 8:35
  • $\begingroup$ 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... $\endgroup$ – Victor Galeano Jun 17 at 8:52
  • $\begingroup$ 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? $\endgroup$ – Eric Towers Jun 17 at 9:11

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 $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.