The number of tilings of a grid

Question

Setup: A block is any rectangular array of squares, specified by its dimensions \$(w,h)\$. A grid is any finite ordered list of blocks. For example, \$\lambda = ((3,2),(3,1),(1,2))\$ defines a grid.

Let \$\lambda\$ and \$\mu\$ be two grids with equal area.

A tiling of \$\lambda\$ by \$\mu\$ is any rearrangement of the squares of \$\mu\$ into the shape of \$\lambda\$ satisfying two properties:

1. horizontally adjacent squares of \$\mu\$ remain horizontally adjacent in \$\lambda\$, and
2. vertically adjacent squares of \$\lambda\$ come from vertically adjacent squares of \$\mu\$.

In other words, while rearranging one is allowed to make horizontal cuts to the blocks of \$\mu\$ but not vertical cuts, and one is allowed to place blocks into \$\lambda\$ side-by-side, but not on top of one another.

Two tilings of \$\lambda\$ by \$\mu\$ are considered equivalent if they can be rearranged into one another by any combination of either permuting squares within a column or reordering the columns of a block.

Problem: Write a function \$T(\mu,\lambda)\$ which computes the number of inequivalent tilings of a grid \$\lambda\$ by another grid \$\mu\$ of equal area.

Specifications: You may use any data type you would like to specify a grid.

Examples:

1. The grid \$\lambda=((1,2),(1,2),(1,1),(2,1))\$ admits a tiling by \$\mu=((1,3),(1,2),(2,1))\$ given by

There is exactly one other inequivalent tiling given by

(Since the two differently colored columns of height \$2\$ are not part of the same block, they cannot be permuted.)

2. The three displayed tilings of \$\lambda=((3,1))\$ by \$\mu=((1,2),(1,1))\$ are equivalent:

3. Let \$\lambda\$ be an arbitrary grid of area \$n\$ and let \$\lambda[(w,h)]\$ denote the number of blocks of \$\lambda\$ of dimension \$w \times h\$. Then \$T(\lambda,\lambda) = \prod_{w,h\geq 1} \lambda[(w,h)]!\$ and \$T(\lambda,((n,1))) = 1\$.

4. The matrix of values of \$T(\mu,\lambda)\$ for all pairs of grids of area \$3\$ (row is \$\mu\$, column is \$\lambda\$):

	((1,3))	((1,2),(1,1))	((1,1),(1,1),(1,1))	((2,1),(1,1))	((3,1))
((1,3))	1	1	1	1	1
((1,2),(1,1))	0	1	3	2	1
((1,1),(1,1),(1,1))	0	0	6	3	1
((2,1),(1,1))	0	0	0	1	1
((3,1))	0	0	0	0	1

Answer 1

Haskell, ^255…247 242 bytes

• -2 bytes thanks to xnor, for suggesting a better partitioning function q.
• -8 bytes thanks to ovs, for suggesting [a!!i|i:_<-u] and removing an unnecessary map.

(a#b)c d=sum[1|g<-nub$(permutations(zipWith replicate b[0..]>>=id)>>=q)>>=mapM(q.sort),l g==l c,and[l x==h&&all(==x!!0)x&&sum[a!!i|i:_<-u]==w|(u,w,h)<-zip3 g c d,x<-u]]
q=foldr(\h t->map([h]:)t++[(h:y):z|y:z<-t])[[]]
l=length
import Data.List

Try it online!

A grid \$\mu\$ is represented as a pair \$(W_\mu,H_\mu)\$ where \$W_\mu\$, \$H_\mu\$ are lists containing, respectively, the widths and the heights of the blocks in \$\mu\$.

The relevant function is (#), which takes as input four lists: a\$=W_\mu\$, b\$=H_\mu\$, c\$=W_\lambda\$, d\$=H_\lambda\$. It returns the integer \$T(\mu,\lambda)\$.